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).

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

*