KMP – wyszukiwanie wzorca w tekście


Gdy chcemy wyszukać w tekście jakiś wzorzec, możemy użyć najprostszego rozwiązania brutalnego: iteruję się po wszystkich literach tekstu, jeśli dana litera pokrywa się ze wzorcem, to sprawdzam czy reszta również się pokrywa. Jeżeli tak, oznacza to, że znalazłem wystąpienie wzorca, w przeciwnym wypadku: nie. Niestety takie rozwiązanie jest nieoptymalne i przy danych wejściowych o dużym rozmiarze, np. tekst o długości 10^6 + wzorzec o długości 10^4 , możemy nie doczekać się naszego wyniku. Na szczęście istnieje algorytm działający w złożoności liniowej, jednak zanim do niego przejdziemy musimy nauczyć się tworzenia tablicy prefikso-sufiksów.

Czym są prefikso-sufiksy?

Aby wytłumaczyć czym są prefikso-sufiksy, posłużę się przykładem tekstu:
S = „ababxabab”
Prefikso-sufiksem nazywamy prefiks tekstu, który jest jednocześnie jego sufiksem. W przykładzie prefikso-sufiksami są: „ab”, „abab” oraz „ababxabab”.
Właściwym prefikso-sufiksem jest prefikso-sufiks, który nie jest całym tekstem. W przykładzie: „ab” oraz „abab”.
Maksymalny prefikso-sufiks to najdłuższy prefikso-sufiks. W przykładzie: „ababxabab”.
Maksymalnym właściwym prefikso-sufiksem nazywamy najdłuższy prefikso-sufiks właściwy. W przykładzie: „abab”.

Uwaga!
W dalszej części artykułu, gdy będę posługiwał się pojęciem prefikso-sufiksu, to będę mieć na myśli prefikso-sufiks właściwy.

Tablica prefikso-sufiksów

Jak już wspomniałem, do algorytmu KMP potrzebujemy tablicy prefikso-sufiksów – dla każdego indeksu i od 0 do S.size() – 1 będziemy przechowywać następującą informację: jaka jest długość maksymalnego prefikso-sufiksu, gdzie tekstem jest fragment od 0 do i. Aby utworzyć taką tablicę w liniowej złożoności, musimy poznać dwa lematy.

Lemat 1.

Prefikso-sufiks mojego prefikso-sufiksu jest moim prefikso-sufiksem.

Innymi słowy: mam tekst, znajduję w nim prefikso-sufiks, to jego prefikso-sufiks będzie prefikso-sufiksem dla całego tekstu. Poza tym, zauważmy że jeżeli mamy wyliczoną tablicę prefikso-sufiksów ps, to zbiorem wszystkich prefisko-sufiksów tekstu S jest zbiór: {ps [S.size()-1], ps [ ps [S.size()-1 ] ], …}, gdzie każdy element zbioru jest >= 1.

Żółty i niebieski prefikso-sufiks są prefisko-sufiksami dla całego tekstu.

Lemat 2.

Niech t będzie długością najdłuższego prefikso-sufiksu słowa S[0…i-1], takiego że S[i]==S[t]. Wtedy maksymalny prefikso-sufiks słowa S[0…i] będzie mieć długość t + 1.

Skoro poznaliśmy już dwa lematy, to możemy przejść do naszego algorytmu na znalezienie tablicy prefikso-sufiksów:

KMP

Aby wyszukać wzorzec w tekście wystarczy wykonać powyższy algorytm dla następującego tekstu: wzorzec + znak, który nie występuje ani we wzorcu ani w tekście, np. „#” + tekst do przeszukania. Tam, gdzie ps [ i ] jest równe długości wzorca, oznacza to, że w miejscu i kończy się wzorzec wyszukany w tekście. Dzięki temu jesteśmy w stanie stwierdzić, w których miejscach i ile razy wystąpił wzorzec.

Karen and Coffee – omówienie

Treść zadania

https://codeforces.com/problemset/problem/816/B

O co chodzi w zadaniu?

Dostajemy liczbę n, k i q oznaczające liczbę recept, minimalną liczbę recept żeby temperatura była zarekomendowana, oraz liczbę zapytań. Po wczytaniu tych trzech liczb otrzymujemy n recept i q par przedziałów temperatur. Naszym zadaniem jest wypisanie dla każdego przedziału liczby temperatur których ilość w receptach jest >= k.

Jak się za to zabrać?

Załóżmy, że mamy dostęp w czasie stałym do liczby poprawnych recept w danym przedziale, wtedy nasz problem problem stałby się prosty, gdyż wczytując przedziały wystarczyłoby wypisać naszą liczbę w czasie stałym.

Jednak jak stworzyć taką strukturę danych z wcześniej podanych liczb?

Otóż mamy dwa potężne narzędzia, które pomogą nam w rozwiązaniu tego problemu, są to sumy prefiksowe i zliczanie elementów.

Tak więc najpierw analizujemy wszystkie recepty, na przykład dla recepty o sugerującej temperatury na przedziale:  [2, 5] musimy zwiększyć tab[2] o jeden i zmniejszyć tab[6] o jeden, gdyż dzięki tak zainicjowanej tablicy możemy uzupełnić ją liniowo dodając do każdej komórki poprzednią wartość. Dla wartości:

1 3

4 5

5 6

3 9

Otrzymamy:

0 1 0  0 1 1 -1 -1 0 0  -1 0 – Wartość

0 1 2  3 4 5 6  7 8 9 10 11 – Indeks

A po policzeniu sum prefiksowych:

0 1 1 1 2 3 2 1 1 1   0 0 – Wartość

0 1 2 3 4 5 6 7 8 9 10 11 – Indeks

Gdy już to zrobimy nasze rozwiązanie jest prawie gotowe, gdyż w czasie liniowym potrafimy znaleźć odpowiedź dla dowolnego przedziału.

Jednak nie jest to czas stały więc dla wielu przedziałów wciąż będziemy mieli złożoność kwadratową. Dlatego też musimy stworzyć tablice sum prefiksowych, dzięki której wyznaczenie wartości w dowolnym przedziale będzie się odbywało w czasie stałym, a całe rozwiązanie w liniowym.

Tak więc mając powyższą tablicę tworzymy nową tablicę (bądź zapełniamy tą) zerami i jedynkami, w następujący sposób:

Jeśli wartość w tablicy o indeksie i jest >= k to zapisujemy w nowej tablicy jeden, w przeciwnym wypadku zero.

Dla takiego przykładu:

4 2 2

1 3

4 5

5 6

3 9

4 6

8 10

Nasza tablica będzie zmieniać się następująco:

0 0 0 0 0 0 0 0 0 0   0 0 – Wartość

0 1 2 3 4 5 6 7 8 9 10 11 – Indeks

Uzupełnianie tablicy jedynkami i minus jedynkami:

0 1 0  0 1 1 -1 -1  0 0 -1 0 – Wartość

0 1 2  3 4 5 6  7 8 9 10 11 – Indeks

Liczenie sum prefiksowych:

0 1 1 1 2 3 2 1 1 1  0 0 – Wartość

0 1 2 3 4 5 6 7 8 9 10 11 – Indeks

k = 2, więc dla każdej liczby >= 2  zapisujemy 1, a dla niższych 0

0 0 0 0 1 1 1 0 0 0  0 0 – Wartość

0 1 2 3 4 5 6 7 8 9 10 11 – Indeks

Liczenie sum prefiksowych:

0 0 0 0 1 2 3 3 3 3  3 3 – Wartość

0 1 2 3 4 5 6 7 8 9 10 11 – Indeks

Więc naszym wynikiem będzie:

3

0

Gdyż dla przedziału 4 6 tab[6] – tab[4-1] = tab[6] – tab[3] = 3 – 0 = 3,

oraz dla przedziału 8 10 tab[10] – tab[8-1] = tab[10] – tab[7] = 3 – 3 = 0

Link do kodu

https://ideone.com/jT7Oku

Autor: Michał Woźniak

Różnorodność – opis rozwiązania

Zadanie

Na wejściu dostajemy słowo o długości do 10^6. Naszym zadaniem jest znalezienie takiego podsłowa (spójnego fragmentu), w którym różnica liczb wystąpień najczęściej i najrzadziej spotykanej litery była jak najmniejsza.

Pierwsze pomysły

OK, patrzymy na zadanie i żaden pomysł nie przychodzi do głowy. Co należy robić w takich przypadkach? Dobrą strategią zazwyczaj jest uproszczenie zadania, w taki sposób, by nie straciło swojej pierwotnej treści, ale za to było dużo prostsze do napisania jakiegokolwiek działającego rozwiązania, np. pominięcie limitów czasowych lub sprowadzenie do szczególnego przypadku.

Przyjmiemy strategię numer dwa: Co by było, gdyby słowo na wejściu składało się tylko z liter a i b? (Do podobnego pytania można dojść analizując test przykładowy). W tym scenariuszu zadanie rzeczywiście jest dużo prostsze: Wystarczy znaleźć taki fragment słowa, w którym liczba wystąpień litery a minus liczba wystąpień litery b była jak najmniejsza (lub na odwrót – możemy rozważyć oba przypadki i wziąć minimum).

Rozwiązanie podzadania

Rozwiązując to uproszczone zadanie szybko można wpaść na pierwsze rozwiązanie: Sprawdźmy wszystkie przedziały i wybierzmy najlepszy. To rozwiązanie w najwolniejszej wersji działałoby w czasie O(n^3) – podobnie jak szukanie przedziału o największej sumie. Szybko można je przyspieszyć tak, by działało w O(n^2) – analizując przedziały w takiej kolejności, by powiększać je o jeden w prawo:

Optymalne rozwiązanie podzadania

No dobrze, ale czy da się szybciej? Zauważmy, że gdybyśmy każde a zamienili na 1 i każde b zamienili na -1, to powyższe zadanie sprowadzałoby się, że do znalezienia przedziału o największej sumie (takiego z co najmniej jedną literą a i b). (Można dojść do tego pomysłu mając na uwadze, że konkurs dotyczy sum prefiksowych). Zapiszmy rozwiązanie w tej wersji:

Czyli okazuje się, że szukamy takiego przedziału, który minimalizuje

suma_pref[j] – suma_pref[i-1]

Aby przyspieszyć powyższe rozwiązanie, zamiast przeglądać wszystkie przedziały, dla każdego j znajdziemy takie i, by

suma_pref[j] – suma_pref[i-1]

była jak najmniejsza. Jeśli uda nam się to zrobić w O(1) dla każdego j, to uzyskamy rozwiązanie w czasie O(n). Będzie ono wyglądać jakoś tak:

Należy zatem odpowiedzieć na pytanie: jakie i będzie najlepsze dla danego j? Ano takie, dla którego suma_pref[i-1] będzie największe (bo wchodzi do naszego wzoru z minusem, a j mamy ustalone). Aby takie i znaleźć, nie musimy za każdym razem przeszukiwać tablicy – wystarczy, że zapiszemy najlepsze dotychczasowe takie i.

Mamy tylko jedną pętlę, więc całość działa w czasie O(n).

Rozwiązanie

I… to już prawie wszystko. Powróćmy teraz do oryginalnego zadania. Aby je rozwiązać wystarczy zauważyć, że któraś taka para składa się na szukany, optymalny fragment. Więc może… rozważmy wszystkie pary takich liter? Uzyskalibyśmy wówczas złożoność O(A^2 * n), gdzie A jest wielkością alfabetu (=26). Łącznie około 600 milionów operacji (26*26 * milion). Możemy sobie pozwolić na sprawdzenie każdej pary – taka złożoność była wystarczająca, by przejść limity czasowe.

Zadanie domowe

W ostatnim rozwiązaniu nie sprawdzamy, czy liczba liter a i b jest niezerowa (może się zdarzyć tak, że najlepszym – wg programu powyżej – będzie przedział złożony tylko z a lub b). Zmodyfikuj rozwiązanie, by obsłużyć ten przypadek. Wskazówka: mamy dwa przypadki – albo dotychczas nie widzieliśmy jeden z liter, wówczas nie aktualizujemy najmniejszej różnicy albo ta druga litera poza najlepszym przedziałem stoi obok niego (w przeciwnym wypadku najlepszym przedziałem byłby ten o jeden dłuższy).

Karty – omówienie rozwiązania

O co chodzi w zadaniu?

Dostajemy liczbę n i pewną permutację, czyli po prostu ciąg różnych liczb od 1 do n. Naszym zadaniem jest wygenerowanie następnej permutacji w porządku leksykograficznym (czyli takim jak alfabetyczny) lub wypisanie słowa „BRAK”, gdy otrzymany ciąg jest ostatnią z nich.

Jak się za to zabrać?

Spójrzmy na kilka przykładowych par kolejnych permutacji:

           1 4 2 8 7 6 5 3               ->                       1 4 3 2 5 6 7 8

           2 3 1 4                             ->                       2 3 4 1

           5 4 3 2 1                          ->                       BRAK

Zauważmy, że permutacja jest ostatnią, jeśli jej kolejne liczby układają się w ciąg malejący. Więc jeśli rozpatrywana permutacja nie jest ostatnia, musi być liczba która łamie tę zasadę. Spójrzmy jeszcze raz na pierwszy przykład:

1 4 2 8 7 6 5 3

Jak można zauważyć, pierwsza liczba od prawej, której prawy sąsiad jest większy to 2. następnie znajdujemy pierwszą liczbę, która jest od niej większa (bo chcemy “zwiększyć” tę permutację o najmniejszą wartość) i zamieniamy je miejscami. Otrzymujemy coś takiego:

1 4 3 8 7 6 5 2

Liczby znajdujące się za zamienioną (wyżej wytłuszczone) tworzą ciąg malejący. Dzieje się tak, ponieważ wcześniej nie znaleźliśmy tam liczby, która łamię zasadę ciągu malejącego, a „nowa” liczba jest mniejsza niż wyjściowa. Żeby otrzymać odpowiedź wystarczy go obrócić:

1 4 3 2 5 6 7 8

Link do kodu

https://ideone.com/Xv1xys

Autor: Daniel Wujkowski

Nawiasy – omówienie rozwiązania

O co chodzi w zadaniu?

Dostajemy n nawiasów, zamykających “)” lub otwierających “(“. Nasze zadanie polega na sprawdzeniu czy ich ciąg jest poprawny, tj. Czy każdy nawias otwierający jest poprawnie zamknięty, np “( ( ) )“ lub “( ) ( )”.

Obserwacje

Kluczem do rozwiązania zadania jest zauważenie dwóch własności:

  1. W chwili gdy liczba nawiasów zamkniętych przekracza ilość nawiasów otwartych ciąg na pewno nie jest poprawny [np. “( ) )” ],
  2. Liczba nawiasów otwierających i zamykających musi być równa  [ciąg “ ( ( ) ) ” jest poprawny, natomiast “ ( ( ( ) ) “ już nie].

Rozwiązanie

Chcemy więc zliczać oba typy nawiasów. Przyda nam się do tego zmienna k. Przechodząc po każdym elemencie ciągu będziemy ją odpowiednio zwiększać (k++) przy napotkaniu nawiasu otwartego, lub zmniejszać (k–) kiedy nawias jest zamknięty – przechowuje informację o niezamkniętych jeszcze nawiasach. Pozwoli to nam sprawdzić wcześniej przedstawione warunki:

  1. Jeżeli ciąg jest niepoprawny, k w trakcie sprawdzania nawiasów stanie się liczbą ujemną,
  2. Jeżeli ciąg jest niepoprawny, k po sprawdzeniu całego ciągu nie będzie równe 0.

Jeżeli żadna z tych sytuacji nie zachodzi możemy stwierdzić, że ciąg jest poprawny – wypisać “TAK”, a w przeciwnym wypadku wypisać “NIE”.

Link do kodu

https://ideone.com/b9lGF4

Autor: Maciej Świetlik

Codeforces – komunikaty błędów

Compilation error

Kod nie kompiluje się — trzeba skompilować u siebie lokalnie i poprawić błędy. A może jest tak, że po prostu wybrałeś zły kompilator (wybierz GNU G++14 lub G++17 dla języka C++).
Jeśli dalej nie wiesz, co jest nie tak, po kliknięciu w Compilation error powinieneś zobaczyć dokładny komunikat błędu, który wypisuje kompilator.

Na przykład:

Stąd wiemy, że nie istnieje funkcja upper().

Wrong answer on test #X

Program zwraca zły wynik na x-tym teście, tzn. że istnieją dane wejściowe, po wpisaniu których Twój program zwraca złą odpowiedź (złą liczbę lub dodatkowe, niepotrzebne znaki). Jeśli jest to błąd na jednych z testów przykładowych, pamiętaj, że Twój program musi wypisać na ekran dokładnie to, co znajduje się w polu Output!

Czasami możliwe jest zobaczenie testu, na którym Twój program działa niepoprawnie. Jest on dostępny po kliknięciu na Wrong answer on test #X na liście Twoich submitów.

Legenda do obrazka

Input – dane wejściowe
Output – to co wypisuje Twój program
Answer – poprawna odpowiedź dla tego testu
Checker log – dodatkowe informacje, co dokładnie jest nie tak.

Time limit exceeded on test #X

Program działa za wolno. Program musi działać na każdym teście najwyżej kilka sekund (konkretne limity podane są w opisie zadania). Spróbuj przetestować go na największych możliwych danych wejściowych (możesz skonstruować duży test za pomocą… innego programu i przekierować jego wyjście do pliku).

Runtime error on test #X

Program nie kończy się poprawnie — podczas jego działania pojawia się błąd, na który system nie mógł pozwolić (np. dostęp do komórki poza tablicą lub podzielenie przez zero). Spróbuj przetestować swój kod na różnych, złośliwych testach. Przeanalizuj test, na którym program nie działa (patrz sekcja: Wrong answer on test #X)

Accepted

Brawo!

„Bilet” – omówienie (spójny podciąg o maksymalnej sumie)

O co chodzi w zadaniu?

Jest n miast. Przez wszystkie miasta prowadzi piaszczysta droga jednokierunkowa; na odcinkach tej drogi pomiędzy miastami, Bajtazar sprzedaje swoje towary, na których zyskuje bądź traci. Bajtazar chce się dostać z pierwszego do ostatniego miasta. Ma on również możliwość wsiąść raz w pociąg, który zabierze go do dowolnego innego miasta (również do poprzedniego). Chcemy obliczyć maksymalny zysk Bajtazara.

Jak się do tego zabrać?

Gdyby Bajtazar nie miał możliwości jednokrotnego użycia pociągu, to musiałby przejść przez wszystkie miasta piaszczystą drogą. Co z kolei oznacza, że wynikiem byłaby suma wszystkich zysków i strat. Oznaczmy zbiór odcinków piaszczystej drogi, jako zbiór liter:

a  b  c  d  e  f  g

Do czego sprowadza się użycie pociągu? Do wzięcia jakiegoś podciągu piaszczystej drogi, np. [a  b],    [d  e  f],    [b  c  d  e] i wykonania jednej z dwóch operacji:

  1. Przedłużenia piaszczystej drogi o ten odcinek (cofnięcie się).
  2. Skrócenia piaszczystej drogi o ten odcinek (pojechanie dalej).

Naszym zadaniem jest znalezienie dwóch podciągów: jednego o maksymalnej sumie, drugiego o minimalnej sumie. Ten o maksymalnej sumie będzie oznaczać dodatkową drogę, którą chcemy jeszcze pokonać. Ten o minimalnej, będzie oznaczać drogę, którą chcemy pominąć. Wynikiem końcowym będzie większa wartość z dwóch wariantów:

  1. Suma całej piaszczystej drogi pomniejszona o minimalny podciąg.
  2. Suma całej piaszczystej drogi powiększona o maksymalny maksymalny podciąg.

Spójny podciąg o maksymalnej sumie

Problem

Dostajesz ciąg n liczb całkowitych: a[1], a[2], a[3] … a[n], gdzie:
1 <= n <= 3*10^6
-10^9 <= t[i] <= 10^9
Musisz wypisać sumę ze spójnego podciągu o maksymalnej sumie.

Rozwiązanie

Czym jest spójny podciąg o maksymalnej sumie? Jest to taki fragment ciągu, którego suma jest największa. Jaki jest pierwszy rzucający się w oczy sposób na wyliczenie sumy ze spójnego podciągu o maksymalnej sumie? Rozważyć wszystkie możliwe podciągi i z każdego z nich policzyć sumę, a największą wziąć do wyniku. Jednak jest to rozwiązanie o złożoności O(n^2). Przy tak wysokim n-ie, czekalibyśmy bardzo długo na wykonanie programu. Musi więc istnieć jakieś inne rozwiązanie naszego problemu.

Algorytm będzie wyglądać następująco:

 

Jak działa ten algorytm? Będziemy szukać podciągu o maksymalnej sumie. Na początku nie dysponujemy takim (tzn. dysponujemy jedynie podciągiem o liczbie elementów 0, stąd początkowa suma też wynosi 0). Jeżeli będzie się nam opłacać przyłączyć nowy element do podciągu, tzn. po przyłączeniu rozważanego elementu do podciągu jego suma nie spadnie poniżej 0, to przyłączamy go, w przeciwnym wypadku usuwamy z podciągu wszystkie elementy, otrzymując pusty podciąg. Można pomyśleć: „ale po co przyłączać element, który zmniejszy sumę podciągu”? Sens takiego działania zostanie pokazany przez następujący przykład:

6  -1  3 // dotychczasowy podciąg; suma: 8
-3  8 // kolejne elementy

Jeżeli do dotychczasowego podciągu przyłączymy liczbę -3, to nie ma znaczenia, że suma się zmniejszyła, dlatego że być może później napotkamy na liczbę dodatnią, która w ostatecznym rozrachunku zwiększy sumę podciągu, w tym przypadku jest to liczba 8. Po każdym takim działaniu wyczyszczenia podciągu lub przyłączenia nowego podciągu, aktualizujemy nasz wynik.. Zauważ, że nie musimy tego podciągu  fizycznie przechowywać. Wystarczy, że będziemy mieć jedynie sumę jego elementów.

Przykład

10
-3 4 -1 2 -7 2 -1 5 -2 1

Wynik powinien wyjść 6. Jest to suma z następującego podciągu: 2 -1 5.

 

„Zbiór pierwszych” – omówienie (Algorytm Euklidesa)

O co chodzi w zadaniu?

Mamy z zestawów danych. Przy każdym zestawie na wejście dostajemy dwie liczby całkowite a oraz b. Musimy odpowiedzieć na następujące pytanie: „czy zbiór dzielników pierwszych liczby a jest podzbiorem dzielników pierwszych liczby b”.

Jak się zabrać za zadanie?

Pierwszym skojarzeniem po przeczytaniu pary słów: „liczby pierwsze” jest najprawdopodobniej sito Eratostenesa. Zauważ jednak, że każda z liczba a oraz mieści się w przedziale od 1 do 10^9. Oznacza to, że po użyciu sita, które ma złożoność O(n log log n) nasze rozwiązanie nie będzie w stanie przejść testów na sprawdzarce, gdyż ma nieefektywną złożoność. Jak się zapewne domyślasz, istnieje rozwiązanie, które nie będzie wymagać od nas użycia sita. Wyobraźmy sobie zbiór, który zawiera dzielniki pierwsze danej liczby x. Będzie on nieco inny, niż ten o którym mowa w zadaniu, gdyż dany dzielnik pierwszy d będzie w nim występować tyle razy, ile razy możemy dzielić daną liczbę x przez dzielnik d, np.

x = 1960
x-zbiór:
2  2  2
brak
5
7  7

W ten sposób będziemy reprezentować liczby a oraz b. W jaki sposób możemy wykorzystać taką reprezentację? Rozważmy na następnym przykładzie:

a-zbiór:
2  2  2  2
3
5  5  5
7  7  7  7  7
brak

b-zbiór:
2  2
brak
5
7  7
11  11  11

Z tych zbiorów wyciągnijmy część wspólną:

część_wspólna_a_b-zbiór:
2  2
brak
5
7  7

Zauważmy, że jeżeli „zbiór dzielników pierwszych liczby a jest podzbiorem dzielników pierwszych liczby b”, to część wspólna zbiorów a-zbiór oraz b-zbiór będzie zawierać wszystkie dzielniki liczby a. W naszym przypadku część wspólna nie zawiera liczby 3 – dzielnika pierwszego liczby a, z czego wynika że zbiór dzielników pierwszych liczby a NIE jest podzbiorem dzielników pierwszych liczby b. Skąd zatem możemy wiedzieć, czy część wspólna zawiera wszystkie dzielniki liczby a?  Jeżeli udałoby się nam usunąć ze zbioru a-zbiór wszystkie elementy o wartości występującej w części wspólnej, będziemy w stanie stwierdzić czy spełniony został warunek, o którym mowa w zadaniu. W przypadku gdy a-zbiór jest pusty, warunek został spełniony, w przeciwnym wypadku nie został spełniony.

Algorytm na przykładzie

Mamy już ogólny zarys tego, jak będziemy postępować. Wprowadźmy następującą operację usuwania: ze zbioru X usuń elementy ze zbioru Y, np.

X = {2, 2, 2, 2, 2, 5, 7, 7, 11}
Y = {2, 2, 7}

X po 1. usunięciu:
X = {2, 2, 2, 5, 7, 11}

X po 2. usunięciu:
X = {2, 5, 11}

Ustalmy, że nie możemy wykonać operacji usuwania, jeżeli brakuje elementów, tzn. usunąć ze zbioru X elementów: 2, 2, 7, gdyż te nie występują w odpowiedniej liczbie: elementy o wartości 2 musiałyby wystąpić w zbiorze X co najmniej 2 razy, element o wartości 7 musiałby wystąpić w zbiorze X co najmniej raz.

Powróćmy teraz do naszego pierwszego przykładu:

a-zbiór:
2  2  2  2
3
5  5  5
7  7  7  7  7
brak

b-zbiór:
2  2
brak
5
7  7
11  11  11

część_wspólna_a_b-zbiór:
2  2
brak
5
7  7

Ze zbioru a-zbiór usuwajmy część wspólną, dopóki jest to możliwe (zgodnie z tym, co zostało zapisane powyżej). Przed usunięciem:

a-zbiór:
2  2  2  2
3
5  5  5
7  7  7  7  7
brak

Po 1. usunięciu:

a-zbiór:
2  2
3
5  5
7  7  7
brak

Po 2. usunięciu:

a-zbiór:
brak
3
5
7
brak

W tej chwili nie możemy już wykonywać operacji usuwania. Stwórzmy więc nową część wspólną: z obecnego zbioru a-zbiór oraz ze zbioru b-zbiór:

część_wspólna_a_b-zbiór:
brak
brak
5
7

Ze zbioru a-zbiór usuńmy teraz nową część wspólną:

a-zbiór:
brak
3
brak
brak
brak

Zbiór nie jest pusty, a więc warunek z zadania nie został spełniony. Algorytm, którego celem jest usunięcie ze zbioru a-zbiór wszystkich elementów, których wartości występują również w początkowej części wspólnej, wygląda następująco:

utwórz część_wspólna_a_b-zbiór
dopóki część_wspólna_a_b-zbiór nie jest pusty, wykonuj:
dopóki od a-zbiór można odjąć część_wspólna_a_b-zbiór, wykonuj:
                    od a-zbiór odejmij część_wspólna_a_b-zbiór
utwórz część_wspólna_a_b-zbiór
jeżeli a-zbiór jest pusty
napisz TAK
w przeciwnym wypadku
napisz NIE

Implementacja

Każdą liczbę naturalną dodatnią da się przedstawić, jako iloczyn kolejnych liczb pierwszych podniesionych do odpowiednich potęg, np.

1960 = 2^3 * 3^0 * 5^1 * 7^2

Takie zapisanie liczby, odzwierciedla bardzo dobrze zbiór, który omawialiśmy. Potęga przy liczbie pierwszej informuje nas, ile elementów o danej wartości występuje w zbiorze. Co do implementacji, należy zadać następujące pytania:

  1. Jak przedstawić a-zbiór, b-zbiór?
    Odp: a-zbiór, to po prostu a, zaś b-zbiór to b.
  2. Jak przedstawić część wspólną?
    Odp: Cześć wspólna zbiorów to NWD(a, b).
  3. Jak sprawdzić czy część_wspólna_a_b-zbiór jest pusty?
    Odp: Jeżeli jest pusty, to NWD(a, b).
  4. Jak sprawdzić czy od a-zbiór można odjąć część_wspólna_a_b-zbiór?
    Odp: Jeżeli NWD(a, b) liczysz na bieżąco (przy sprawdzaniu jest używana funkcja wyliczająca NWD), to zawsze możesz to zrobić, gdyż wyliczone w tej chwili NWD musi być dzielnikiem liczby a.
  5. Jak od a-zbiór odjąć część_wspólna_a_b-zbiór?
    Odp: a = a/NWD(a,b).

UWAGA!
Przy liczeniu na bieżąco NWD(a, b), czyli nieprzechowywaniu go w żadnej zmiennej, Twój algorytm powinien skrócić się do tej postaci:

dopóki teraz_wyliczona_część_wspólna_a_b-zbiór nie jest pusta, wykonuj:
od a-zbiór odejmij teraz_wyliczona_część_wspólna_a_b-zbiór
jeżeli a-zbiór jest pusty
napisz TAK
w przeciwnym wypadku
napisz NIE

Zakodowanie zadania pozostawiam w Waszej gestii 🙂

Testowanie programów IV: „brut” i „wzorcówka”

Potrafimy już generować losowe testy dla naszych programów. Wykorzystajmy zdobytą dotychczas wiedzę do przetestowania naszego rozwiązania wzorcowego. Jednakże zanim zabierzemy się do pracy, zadajmy sobie następujące pytanie: czy kod rozwiązania brutalnego jest prostszy od kodu rozwiązania wzorcowego? Odpowiedź brzmi: tak.

Aby stworzyć rozwiązanie optymalne, musimy posługiwać się wieloma różnymi algorytmami, przy których zaklepywaniu możemy popełnić rozmaite błędy. Przy wyszukiwaniu binarnym możemy zapętlić się w nieskończoność; przy używaniu dodatkowej tablicy do zliczania elementów, możemy wyjść poza tę tablicę (zliczanie elementów o wartości wyższej niż rozmiar tablicy do zliczania), itd. Skoro przekonaliśmy się, że rozwiązanie brutalne jest na ogół prostsze, to czy można to jakoś wykorzystać?

Do testowania wzorcówki (rozwiązania wzorcowego) wykorzystajmy bruta (rozwiązanie brutalne). W jaki sposób? Uruchommy bruta oraz wzorcówkę na tych samych testach. Testy generujemy losowo tak, jak wcześniej się nauczyliśmy. Postępując w ten sposób otrzymamy wyniki osobno dla rozwiązania brutalnego i osobno dla rozwiązania. Otrzymane wyniki porównujemy ze sobą. Jeżeli dla któregoś testu wyniki się różnią, to na pewno co najmniej jedno z naszych rozwiązań jest błędne. Istnieje duża szansa, że błędnym rozwiązaniem jest tylko wzorcówka (dlatego, że jest trudniejsza do zaklepania). Analizujemy, dlaczego dla danego testu otrzymaliśmy dwa różne wyniki i staramy się znaleźć błąd w naszym programie. Jeśli wiemy już na czym polega testowanie wzorcówki za pomocą bruta, to przetestujmy wzorcówkę do poniższego ćwiczenia.

Ćwiczenie

Na kartce zapisano n liczb: t[1], t[2]…t[n]. Otrzymujesz q pytań. Każde pytanie to para liczb: a, b (a <= b), co oznacza: jaka jest suma liczb od elementu o numerze a do elementu o numerze b.

Wejście

n – ilość liczb zapisanych na kartce
t[1], t[2],…,t[n] – liczby zapisane na kartce
q- liczba pytań
a, b- pytanie: suma liczb od elementu o numerze a do elementu o numerze b

Wyjście

res[1], res[2], …,res[q] – odpowiedzi na pytania

Wyjście

1 <= n, q, a, b <= 1 000 000
1 <= t[1], t[2],…,t[n] <= 1 000 000 000

 

Testowanie rozwiązań

Aby przetestować wzorcówkę przy użyciu bruta, potrzebujemy:

  1. testowanej wzrocówki
  2. bruta do testowania
  3. programu generującego testy
  4. skryptu obsługującego trzy powyższe programy (skrypt testujący)

UWAGA!!!!!
1) Wszystkie cztery pliki muszą znajdować się w jednym folderze.
2) Skrypt obsługujący programy piszemy w bashu, więc aby sprawdzić testowanie rozwiązań na swoim komputerze, potrzebujesz Linuxa.

Wzorcówka

Rozwiązanie wzorcowe korzysta z sum prefiksowych, dzięki czemu możemy osiągnąć złożoność liniową.

 

Brut

Program dla każdego zapytania iteruje się maksymalnie przez całą tablicę, więc działa w czasie kwadratowym.

 

 

Program generujący testy

Zastanówmy się nad tym, w jaki sposób ma działać ten program?

  1. W konsoli muszę mieć możliwość podania wartości dla trzech zmiennych: n, min_t, max_t, q czyli: ilość w liczb w generowanej tablicy,  zakres losowanych wartości generowanej tablicy oraz liczba zapytań.
  2. Wypisuję liczbę n.
  3. Dla komórek tablicy t od 1. do n. elementu losuję wartość od min_t do max_t.
  4. Wypisuję zawartość tablicy t.
  5. Wypisuję q.
  6. Wykonaj kroki 7,  8. oraz 9. q razy.
  7. Losuję dla zmiennej a wartość od 1 do n.
  8. Losuję dla zmiennej b wartość od a do n.
  9. Wypisz a oraz b.

Oto nasz program:

UWAGA!!!
Jeżeli nie rozumiesz któreś linijki kodu, koniecznie zajrzyj tu.

 

Skrypt testujący

Skrypt napisany jest w bashu (języku Linuxa; rozszerznie:  .sh). Działa w następujący sposób:

  1. Wygeneruj plik tekstowy z testem (inputem).
  2. Odpal test na brucie i zapisz jako wynik dla bruta.
  3. Odpal test na wzorcówce i zapisz jako wynik dla wzorcówki.
  4. Porównaj oba wynik, jeśli te się różnią, to wypisz je w konsoli (za pomocą diff).
  5. Powyższe operacje wykonaj łącznie c razy.

Oto skrypt:

Jeżeli skompilowałeś wszystkie trzy programy, możesz wpisać do konsoli:

Jeżeli nie masz uprawnień, wpisz jeszcze do konsoli:

Twoim oczom powinno się w konsoli ukazać coś takiego:

W pierwszej linijce każdego testu widzisz wynik dla bruta, a w drugiej linijce dla wzorcówki. W przypadku, gdy wyniki są identyczne, nie są one wyświetlane (w ten sposób działa diff). Teraz postaraj się już samodzielnie odnaleźć błąd we wzorcówce 🙂