Omówienie zadania Podział na anagramy (II etap XXXII OI)

Wstęp

W zadaniu mamy dane \(n\)-literowe słowo \(S\), w którym pojawiają się jedynie małe litery alfabetu angielskiego. Naszym zadaniem jest, dla danego słowa \(s\) na wejściu, wskazać największą wartość \(k\) taką, że możemy pociąć \(s\) na kawałki będące anagramami palindromów o długości co najmniej \(k\). Dodatkowo chcemy wypisać konstrukcję takiego podziału. Pewne słowo \(s\) nazwiemy anagramem słowa \(t\), wtedy, gdy każda litera w alfabecie występuje tyle samo razy zarówno w \(t\), jak i w \(s\). Powiemy, że pewne słowo \(s\) jest palindromem, gdy czytane od początku jest takie samo jak czytane od końca.

Ważne spostrzeżenie

Przeanalizujmy, czym cechują się słowa będące anagramami palindromów. Zauważmy, że jeśli pewne słowo \(s\) jest palindromem, to jeżeli jego długość jest większa bądź równa \(2\), możemy "odciąć" obydwa końce naszego słowa i nadal pozostanie ono palindromem. Powtarzając ten proces rekurencyjnie, otrzymamy:

słowo jednoliterowe, jeśli długość \(s\) jest nieparzysta,
słowo puste, jeśli długość \(s\) jest parzysta.

Kolejnym ważnym spostrzeżeniem jest fakt, że parzystość liczby wystąpień każdej litery nie zmienia się po operacji, którą wykonywaliśmy.

Łącząc to z poprzednim zauważeniem, otrzymujemy wniosek, że w palindromie o parzystej długości każda litera występuje parzystą liczbę razy, zaś w palindromie o nieparzystej długości dokładnie jedna litera występuje nieparzystą liczbę razy. Zauważmy, że to samo dotyczy anagramów palindromów, ponieważ mają one ten sam multizbiór liter.

Rozwiązanie brutalne

Skoro mamy prosty sposób na sprawdzenie, czy słowo jest anagramem palindromu, pora go wykorzystać w praktyce. Spróbujmy rozwiązać zadanie programowaniem dynamicznym. Niech \(dp_i\) oznacza wynik dla prefiksu słowa wejściowego o długości \(i\). Jeśli mamy skonstruowane poprawne pocięcie na prefiksie o długości \(j < i\), to jeżeli słowo utworzone z liter słowa \(S\) na pozycjach \(j+1, j+2, \dots, i\) jest anagramem palindromu, to istnieje też poprawne pocięcie słowa \(S\) na pozycjach \(1, 2, \dots, i\) i możemy zaktualizować \(dp_i\) na wartość \(max(dp_i, min(dp_j, i-j))\).

Co prawda, to wyznacza tylko wartość wyniku, a nie podział, ale możemy temu zaradzić, utrzymując tablicę pomocniczą przechowującą dla każdego prefiksu informację o miejscu ostatniego cięcia. Na końcu możemy z tej tablicy odzyskać poprawny podział całego słowa.

Jeśli sprawdzenie, czy dane podsłowo jest anagramem palindromu, wykonamy w czasie \(O(\)długość podsłowa\()\), to nasza sumaryczna złożoność czasowa wyniesie \(O(n^3)\). Możemy jednak przyspieszyć to rozwiązanie, zamiast brutalnie przechodzić po każdym podsłowie, licząc sumy prefiksowe (a dokładniej parzystości) dla każdej litery w słowie. Dzięki temu możemy zredukować złożoność do \(O(\alpha \cdot n^2)\), gdzie \(\alpha\) to rozmiar alfabetu, czyli 26. Dzieje się tak, ponieważ sprawdzenie, czy dana litera występuje parzystą liczbę razy w podsłowie od \(j+1\) do \(i\), sprowadza się do porównania parzystości jej wystąpień na prefiksie o długości \(j\) oraz \(i\).

Możemy jeszcze bardziej przyspieszyć nasze rozwiązanie, korzystając z faktu, że dla każdej litery na ustalonym prefiksie potrzebujemy tylko jednego bitu informacji:

\(0\) - występuje parzystą liczbę razy,
\(1\) - występuje nieparzystą liczbę razy.

Możemy więc skompresować nasze 26 tablic parzystości prefiksowych do jednej tablicy, w której trzymamy tę samą informację zakodowaną w jednej liczbie całkowitej. Typ \(\texttt{int}\) w języku \(\texttt{C++}\) ma 32 bity do dyspozycji, co pozwala zakodować nasze 26 tablic booli w jednej tablicy intów. Taką liczbę całkowitą, w której bitach kodujemy pewną informację, nazywamy maską bitową.

Aby sprawdzić, czy dana litera występuje nieparzystą liczbę razy, możemy skorzystać z operacji na maskach bitowych. Wystarczy sprawdzić, czy AND bitowy z potęgą dwójki przypisaną do naszej litery jest niezerowy. Załóżmy, że literze \(a\) przypiszemy liczbę \(2^0\), literze \(b\) liczbę \(2^1\), itd. Używając tej metody, możemy w \(O(1)\) sprawdzić, czy dane słowo jest anagramem palindromu, uzyskując złożoność \(O(n^2)\) w rozwiązaniu brutalnym.

Rozwiązanie wzorcowe

Czy potrafilibyśmy szybko znaleźć poprawne pocięcie słowa, gdyby długość najkrótszego dopuszczalnego fragmentu była nam z góry znana (nazwijmy ją \(k\)), lub stwierdzić, że wynik nie istnieje?

Zauważmy, że jeśli pewien wynik istnieje dla danej wartości \(k\), to takie samo pocięcie jest poprawne również dla \(k-1\). W takim razie, jeśli moglibyśmy sprawdzić, czy istnieje pocięcie dla wartości \(k\), to aby odzyskać optymalne pocięcie, możemy użyć wyszukiwania binarnego po wyniku. Jeśli procedura wyniku szukania dla konkretnego \(k\) zwróci, że istnieje taki podział, to będziemy rozpatrywać już tylko liczby nie mniejsze niż obecnie wyszukana, a w przeciwnym wypadku ograniczymy się jedynie do liczb mniejszych. Po \(\log n\) krokach wyszukiwania binarnego poznamy wynik.

Spróbujmy rozważyć tę sytuację dla konkretnego \(k\). Podczas obliczania \(dp_i\) wolno nam teraz rozważać jedynie przejścia odpowiadające prefiksom do pozycji \(j\), spełniające \(j \le i - k\), ponieważ anagram na pozycjach \(j+1, j+2, \dots, i\) musi mieć wtedy długość większą bądź równą \(k\). Na pierwszy rzut oka nie daje to nam zbyt wiele, ale pozwala szybciej stwierdzić, czy istnieje pocięcie, niż wyznaczyć pocięcie o najlepszym wyniku.

Na początku zmodyfikujmy naszą tablicę \(dp\), aby informowała nas jedynie o tym, czy da się uzyskać pocięcie na danym prefiksie przy powyższych założeniach. Niech \(par_i\) oznacza maskę bitową parzystości wystąpień liter na prefiksie o długości \(i\). Zauważmy, że podczas obliczania \(dp_i\) rozpatrujemy takie prefiksy o długości \(j\), że \(par_j\) różni się od \(par_i\) na maksymalnie jednym bicie. Możemy więc trzymać mapę (unordered_map w \(\texttt{C++}\), dictionary w Pythonie) dostępnych prefiksów, która dla danej maski przechowuje informację o istnieniu odpowiedniego pocięcia. Ściślej, nazwijmy naszą mapę \(mp\) i dla pewnej maski bitowej \(m\), niech \(mp_m\) przechowuje informację, czy da się osiągnąć prefiks o długości nie większej niż \(i-k\), którego maska bitowa w \(par\) jest równa \(m\).

Jeśli spośród wszystkich masek bitowych \(m\), różniących się co najwyżej jednym bitem od \(par_i\), znajdzie się taka, że \(mp_m == true\), to możemy osiągnąć również prefiks o długości \(i\). Po takim sprawdzeniu, jeśli \(k \leq i\), możemy "włączyć do rozważenia" prefiks o długości \(i-k+1\), ustawiając \(mp_{par_{i-k+1}} = true\), o ile \(dp_{i-k+1} == true\). Jeśli ostatecznie \(dp_n == true\), to takie pocięcie istnieje, a w przeciwnym razie musimy użyć fragmentu krótszego niż \(k\). Takie sprawdzenie dla ustalonej wartości \(k\) wykonujemy w czasie \(O(n \cdot \alpha)\).

Ostatecznie osiągamy złożoność czasową \(O(\alpha n\log{n})\) oraz pamięciową \(O(n)\), co jest wystarczające, aby uzyskać 100 punktów.

Rozwiązanie bonusowe (w złożoności \(O(\alpha n)\))

Co powstrzymuje nas przed zaimplementowaniem powyższej metody bez użycia wyszukiwania binarnego? Znając wartość \(k\), znamy moment, w którym należy "włączyć" każdy z prefiksów. Musimy więc znaleźć sposób, by sobie z tym poradzić. Wyobraźmy sobie następującą sytuację: obliczyliśmy właśnie w jakiś sposób wynik dla pewnego prefiksu o długości \(i\) (oznaczmy ten wynik przez \(k\)).

Jeśli chcemy przedłużyć ten prefiks do pewnego innego, uzyskując dalej poprawne rozwiązanie, możemy napotkać dwie sytuacje. Pierwsza pojawia się, gdy przedłużymy nasz prefiks o fragment o długości mniejszej niż \(k\) (nazwijmy ją \(l\)). Wtedy wynik dla tego przedłużonego prefiksu będzie równy \(l\) (ponieważ nowy fragment jest najkrótszym z dostawianych). Jeśli zaś \(l > k\), to wynik dla nowego prefiksu będzie równy \(k\).

Spotykamy się więc z sytuacją, w której przez jakiś czas będziemy "proponować" nasz wynik jako swego rodzaju funkcję liniową, a po pewnym czasie stanie się on już stałą \(k\). Musimy to rozgraniczyć. Oprócz naszej pierwotnej mapy \(mp\), z której odzyskujemy najlepszy wynik z drugiej sytuacji, będziemy trzymać również mapę kolejek. Dla ustalonej maski parzystości będziemy trzymać w kolejce indeksy tych prefiksów, dla których dostawiany przedział jest jeszcze krótszy niż którykolwiek w pocięciu i wyciągać z jej końca informację o najdłuższym z nich. Dzięki temu będziemy mogli łatwo odzyskiwać najdłuższy spośród tych prefiksów oraz usuwać te, które nie są nam potrzebne (gdy nastąpi druga sytuacja). Warto także przechowywać informację o tym, kiedy dla danego prefiksu zachodzi druga sytuacja, by odpowiednio ustawić wynik w \(mp\). Dzięki temu uzyskujemy złożoność czasową \(O(n\cdot\alpha)\).