Synteza wirusa

Kolej na zadanie o palindromach z ACM ICPC CERC 2014. Palindromy są fajne. W tym konkretnym dostajemy dość długi napis, który należy skonstruować zaczynając z napisu pustego za pomocą jak najkrótszego ciągu operacji. Każda operacja to doklejenie nowej litery na początku, doklejenie litery na końcu, lub doklejenie odwróconej kopii całego aktualnego napisu (na początku lub na końcu). Docelowy napis może składać się z nawet 10^5 liter, więc ewidentnie celujemy w rozwiązanie o złożoności bliskiej liniowej. Czyli fajnie.

Oryginalną treść można zobaczyć tutaj. Warto zwrócić w niej uwagę na to, że wejście składa się z wielu testów. Nie ma podanego limitu na ich liczbę, ale wiemy, że każdy napis składa się z nie więcej niż 10^5 liter. Spróbujmy więc skonstruować rozwiązanie o złożoności \mathcal{O}(n\log n). Na tym etapie nie jest jasne, czy jest to oczekiwana złożoność, ale… zaryzykujmy.

Zacznijmy od lekkiego przeformułowania zadania. Odwracając czas dostajemy, że należy zredukować podany s[1..n] do pustego napisu przy użyciu jak najmniejszej liczby operacji, z których każda to usunięcie pierwszej lub ostatniej litery lub ucięcie pierwszej połówki aktualnego napisu, o ile jest on parzystym palindromem. Automatycznie daje nam to naiwne rozwiązanie bazujące na programowaniu dynamicznym, które działa w czasie \mathcal{O}(n^2) (prawie automatycznie: trzeba umieć szybko sprawdzać, czy dane s[i..j] jest palindromem; jest to trywialne gdy dopuszczamy kwadratowy preprocessing). Możemy więc napisać sobie bruta, z którym będziemy porównywali odpowiedzi sprytniejszych i niekoniecznie poprawnych rozwiązań.

Po chwili refleksji nad opisanym powyżej rozwiązaniem brutalnym zauważamy, że rozwiązywane w nim podproblemy są w zasadzie postaci „jak najszybciej zredukować s[i..(i+\ell-1)] do napisu pustego, gdzie s[i..(i+2\ell-1)] jest parzystym palindromem”. Takiej postaci nie są tylko podproblemy odpowiadające samemu początkowi wykonywanego ciągu operacji, w którym tylko i wyłącznie usuwamy litery z początku i końca aktualnego napisu. Wystarczy jednak wyznaczyć odpowiedź dla wszystkich podproblemów palindromicznych, a następnie dla każdego z nich dodać koszt usunięcia wszystkich litera poza danym s[i..(i+2\ell-1)] i porównać wynik z aktualnym najlepszym. Nasuwa się więc oczywiste pytanie: ile (w najgorszym przypadku) może być takich podproblemów palindromicznych?

Noo.. dużo. Choćby dla s[1..n]=\texttt{a}^n jest ich kwadratowo wiele. Ale.. wiele z nich jest tak naprawdę identycznych! Właściwe pytanie powinno więc brzmieć: ile jest różnych słów s[i..(i+2\ell-1)], które w dodatku są parzystymi palindromami?

Lemat 1. W dowolnym słowie długości n można znaleźć co najwyżej n różnych podsłów, które są palindromami.

Dowód. Jeśli s[i..j] jest palindromem, który nie występuje w s[1..(j-1)], obciążamy jego kosztem j-tą pozycję w słowie. Teraz wystarczy uzasadnić, że żadna pozycja nie zostanie obciążona dwukrotnie. Załóżmy więc przeciwnie, czyli mamy dwa różne palindromy s[i..j] oraz s[i'..j], które nie występują w s[1..(j-1)]. Bez straty ogólności i<i'. Ale wtedy możemy symetrycznie odbić s[i'..j] korzystając z tego, że jest on całkowicie zawarty w dłuższym palindromie s[i..j], czyli s[i'..j] występuje w s[1..(j-1)], sprzeczność.∎

Daje to pewną nadzieję na skonstruowanie rozwiązania opartego na programowaniu dynamicznym, w którym rozważamy tylko \leq n stanów odpowiadających różnych podsłowom palindromicznym. Nie jest jeszcze jasne, jak szybko wyliczyć odpowiedź dla konkretnego takiego podsłowa, a w dodatku powyższe rozumowanie nie daje jeszcze efektywnego sposobu na wygenerowanie wszystkich stanów. Jednak doświadczony zawodnik na pewno od razu przypomni sobie, że dla danego słowa s[1..n] można w czasie liniowym wyznaczyć tablicę promieni palindromicznych R[1..n], gdzie R[i] jest największym \ell o takiej własności, że s[i..(i+\ell-1)]=(s[(i-1)..(i-\ell)])^R (w^R oznacza tutaj odwrócenie słowa w) za pomocą algorytmu Manachera. Okazuje się, że ten algorytm (czy też jego lekka modyfikacja) może być wykorzystany także do wygenerowanie wszystkich podsłów palindromicznych. Spróbujmy.

Algorytm Manachera można rozumieć w następujący sposób: wyliczamy kolejno R[1],R[2],\ldots,R[n] w zamortyzowanym czasie \mathcal{O}(1) na każdy. Jednocześnie utrzymujemy sobie m \leq i, gdzie R[1..i] jest już wyliczonym prefiksem, o takiej własności, że m+R[m] jest największe możliwe ze wszystkich 1+R[1],2+R[2],\ldots,i+R[i]. Teraz mamy dwie możliwości.

  1. m+R[m] < i, wtedy wyliczamy R[i] w sposób naiwny i zmieniamy m na i.
  2. m+R[m] \geq i, wtedy odbijamy i symetrycznie względem m otrzymując i'=2m-i-1 i uważnie przyglądamy się R[i'].
    synteza
    Jeśli palindrom odpowiadający R[i'] mieści się z zapasem w palindromie odpowiadającym R[m], to R[i]=R[i']. Jeśli zaś palindrom odpowiadający R[i'] wystaje poza palindrom odpowiadający R[m], to R[i]=R[m]-m+i' zgodnie z poniższą ilustracją.
    synteza1
    Jedna sytuacja, w której nie jesteśmy w stanie wyznaczyć w czasie \mathcal{O}(1) kolejnego R[i], to taka, w której palindrom odpowiadający R[i'] kończy się dokładnie tam, gdzie palindrom odpowiadający R[m]. Wtedy wiemy, że R[i] \geq R[m]-m+i', ale być może R[i] jest istotnie większe. Sprawdzamy więc o ile naiwnie. Zauważmy, że wymaga to wykonania \mathcal{O}(R[i]-(R[m]-m-i')+1) operacji (czyli być może dużo!), ale jednocześnie pozwala podmienić m na i. Widać więc, że jesteśmy w stanie zamortyzować potencjalnie kosztowne naiwne sprawdzanie wzrostem m+R[m]. Wartość ta nigdy nie maleje i nie przekracza n, więc sumaryczny koszt wszystkich naiwnych sprawdzeń to tylko \mathcal{O}(n).

Teraz można zauważyć, że powyższy algorytm może zostać ulepszony tak, aby generował co najwyżej n palindromicznych podsłów, wśród których znajdują się wszystkie możliwe palindromiczne podsłowa całego s[1..n]. Wystarczy wypisywać kolejne palindromiczne podsłowo s[(i-R[i])..(i+R[i]-1)] po każdym zwiększeniu R[i] o jeden. Zauważmy (jest to istotne!), że niekoniecznie wszystkie wygenerowane w ten sposób podsłowa są różne. Ale na pewno jest ich nie więcej niż n, zgodnie z powyższym rozumowaniem. Każdemu wygenerowanemu w taki sposób podsłowu palindromicznemu nadajemy unikalną nazwę i zakładamy, że dla danego i oraz r\in [1,R[i]] potrafimy szybko dostać się do nazwy podsłowa palindromicznego identycznego z s[(i-r)..(i+r-1)]. To drugie nie jest do końca trywialne i przysporzy nam trochę kłopotu, ale będzie to tak zwany kłopot techniczny, który można na razie zignorować.

Jesteśmy gotowi, aby wykonać pierwszą przymiarkę do efektywnego rozwiązania opartego na programowaniu dynamicznym. Chcemy wyznaczyć odpowiedź dla każdego wygenerowanego podsłowa palindromicznego s[(i-\ell)..(i+\ell-1)]. Konkretniej, przez odpowiedź rozumiemy minimalną liczbę operacji potrzebą do zredukowania s[i..(i+r-1)] (czyli prawej połówki) do słowa pustego. Jeśli ten ciągu operacji zaczyna się od usunięcia ostatniej litery s[i+r-1], to tak naprawdę wystarczy dobrać się do odpowiedzi wyznaczonej dla s[(i-\ell+1)..(i+\ell-2)] i dodać do niej jeden. W przeciwnym wypadku bez straty ogólności możemy założyć, że ciąg operacji wygląda w następujący sposób wybieramy pewne j\in [i+\frac{\ell}{2},i+\ell-1] o takiej własności, że s[(2j-i-\ell)..(i+\ell-1)] jest palindromem, usuwamy litery s[i], s[i+1], \ldots, s[2j-i-\ell-1] (oznaczone na szaro na poniższej ilustracji), a następnie redukujemy otrzymane słowo do s[j..(j+\ell-1)].

synteza2

Niby fajnie, ale pojawia się pewien kłopot: takich j może być przecież dużo. Na szczęście okazuje się, że opłaca się być zachłannym, to znaczy wybierać najmniejsze możliwe j (czyli najdłuższy palindromiczny sufiks aktualnego s[i..(i+\ell-1)]. Dlaczego? Wyobraźmy sobie, że mamy dwa możliwe palindromiczne sufiksy s[(2j'-i-\ell)..(i+\ell-1)] i s[(2j-i-\ell)..(i+\ell-1)], gdzie j<j', i ciąg operacji, który zaczyna się od dobrania się do s[(2j'-i-\ell)..(i+\ell-1)] i ucięcia jego lewej połówki tak, aby otrzymać s[j'..(i+\ell-1)]. Wtedy nie gorszym sposobem na uzyskanie takiego samego s[j'..(i+\ell-1)] jest dobranie się do s[(2j-i-\ell)..(i+\ell-1)], ucięcie jego lewej połówki tak, aby otrzymać s[j..(i+\ell-1)], a następnie dobranie się do s[j'..(i+\ell-1)]. Czyli najlepszym możliwym wyborem jest wybranie najmniejszego j\in [i+\frac{\ell}{2},i+\ell-1], dla którego R[j] jest na tyle duże, że odpowiadający mu palindrom sięga aż do s[i+\ell-1]. Ale jak szybko wybrać takie j?

Tutaj z pomocą przychodzi nam zauważenie, że wcale nie musimy wyznaczać tych j jedno po drugim. Można najpierw wyznaczyć wszystkie j, a potem wyliczyć wszystkie wszystkie odpowiedzi w programowaniu dynamicznym. Czyli tak naprawdę zredukowaliśmy cały problem do szybkiego przetworzenia zbioru pytań postaci "znajdź najmniejsze j\in[\ell,r], dla którego j+R[j] \geq i". Naturalne jest przetwarzanie takich pytań w kolejności niemalejących wartości r. Jednocześnie możemy utrzymywać zbiór tych j, dla których j+R[j]\geq i, na przykład w strukturze typu set. Wtedy odpowiedź na jedno pytanie sprowadza się do znalezienia następnika \ell w aktualnym zbiorze! Czyli dokładnie tego, na co pozwala nam set. Potrafimy więc odpowiedzieć na n pytań takiej postaci w sumarycznym czasie \mathcal{O}(n\log n). Czyli koniec?

Niestety, jeszcze nie koniec. Co prawda umiemy znaleźć najlepsze możliwe j, ale przecież tak naprawdę interesuje nas dobranie się do nazwy s[(2j-i-\ell)..(i+\ell-1)], aby odczytać wyliczony wcześniej wynik. Nie jest to do końca trywialne. Analogicznie, musimy umiec szybko dobrać się do nazwy s[(i-\ell+1)..(i+\ell-2)]. Wracamy więc do wspomnianej na samym początku operacji szybkiego wyznaczenia nazwy podsłowa palindromicznego identycznego z s[(i-r)..(i+r-1)] dla danego i oraz r\in [1,R[i]]. Okazuje się to nietrywialne, ale też nie kosmicznie trudne. Możemy bowiem wygodnie myśleć o wszystkich palindromicznych podsłowach jako o drzewie. Każdy wierzchołek drzewa odpowiada jakiemuś palindromicznemu podsłowu, tych wierzchołków jest w sumie nie więcej niż n. Jeśli wierzchołek v odpowiada s[(i-r)..(i+r-1)], gdzie r\geq 2, to jego ojciec w drzewie odpowiada podsłowu identycznemu z s[(i-r+1)..(i+r-2)] (być może dokładnie s[(i-r+1)..(i+r-2)], a być może innemu wystąpieniu tego samego fragmentu). Teraz widać, że opisana na samym początku modyfikacja algorytm Manachera może być łatwo wykorzystana do skonstruowania takiego drzewa, i co więcej do znalezienia dla każdego i wierzchołka, który odpowiada s[(i-R[i])..(i+R[i]-1)]. No, prawie widać: jeśli R[i]=R[m], to po prostu podpinamy i pod ojca m w drzewie. Jsśli R[i]>R[m], to tworzymy ścieżkę złożoną z R[i]-R[m] unarnych wierzchołków. Może być jednak też i tak, że należy dobrać się do przodka wierzchołka odpowiadającego s[(m-R[m])..(m+R[m]-1)], który reprezentuje palindrom o promieniu R[m]-m+i'. Jest to pytanie dokładnie tej samej postaci, co te pojawiające się później w programowaniu dynamicznym.

Po chwili zastanowienia widać, że brakującym elementem całej układanki jest efektywny sposób na utrzymywanie drzewa, do którego podpinamy nowe liście, i w którym chcemy umieć dobrać się k-tego przodka danego wierzchołka v. W tym momencie możemy zapomnieć o palindromach (ufff) i skupić się na drewach. Które też są fajne.

Brakujący element brzmi klasycznie i rzeczywiście taki jest. Jeśli drzewo jest dane na samym początku i nie ulega żadnym zmianom, łatwo odpowiadać na pytania w czasie \mathcal{O}(\log n) po dołożeniu do każdego wierzchołka \log n wskaźników. i-ty wskażnik prowadzi do przodka odległego o 2^i krawędzi (numerujemy od zera, czyli pierwszy wskaźnik to po prostu wskaźnik do ojca). Dodatkowo w każdym wierzchołku v przechowujemy jego głębokość d[v]. Teraz aby przejść z v do przodka na głębokości d[v]-k (a o to nam właściwie chodzi), próbujemy użyć i-tego wskaźnika dla i=\log n,\ldots,1,0. Jeśli prowadzi on do wierzchołka na głębokości przynajmniej d[v]-k, zastępujemy v przez ten wierzchołek. A jeśli nie to nie. Łatwo zauważyć, że w każdym kroku wartość i maleje o jeden, stąd odpowiedź na dowolne pytanie wymaga tylko czasu \mathcal{O}(\log n).

Dobrze, ale przecież nasze drzewo rośnie. Czy nie jest to kłopotliwe? Trochę jest, ale nietrudno wyliczyć wskaźniki nowo utworzonego liścia w czasie \mathcal{O}(\log n), co daje rozwiązanie całego zadania w czasie \mathcal{O}(n\log n).

Opisane rozwiązanie jest dość skomplikowane. Zarówno koncepcyjnie, jak i implementacyjnie. Jego „wduszenie” na zawodach wydaje mi się dość kłopotliwe, ale być może da się jakoś istotnie prościej? (Nie wiem.) Można jednak zapytać, czy możliwe jest rozwiązanie liniowe.

Jest możliwe. Zauważmy bowiem, że nieliniowość powyższej metody wynikała z dwóch czynników: wyszukiwania następnika w dynamicznie zmieniającym się zbiorze, oraz szukania k-tego przodka w rosnącym drzewie. To drugie może być wykonane w czasie stałym (na pytanie i na aktualizacje, choć to drugie wymaga amortyzacji). To pierwsza w zasadzie też, o ile odrobinę skorzystamy ze struktury problemu. Można bowiem zaobserwować, że tak naprawdę utrzymujemy partycję [1,n] na spójne kawałki. Zaczynamy od podziału na n singletonów, a potem czasami sklejamy ze sobą dwa sąsiednie kawałki (odpowiada to wyrzucaniu elementu ze zbioru), a czasami pytamy o ostatni element w kawałku, do którego należy dany x (w właściwie to element tuż za nim). Teraz można zauważyć, że zamiast struktury typu set w zupełności wystarczy nam tutaj union-find. Co jeszcze lepsze, jest to tak zwany interval union-find, który można zaimplementować w zamortyzowanym czasie stałym na operację. Daje to absolutnie niepraktycznie rozwiązanie o liniowym czasie działania.

Advertisements

10 myśli nt. „Synteza wirusa

  1. Ciekawe sformułowanie „budzi niepokój, a przynajmniej zdziwienie”. Mnie zabrzmiało jak ” autorzy chcieli zrobić jakiś przekręt, a co najmniej nie wiedzieli, co robią”.

    Jak się podaje liczbę testów, to albo jest mała (i wtedy się dość mocno ogranicza), albo jest duża (a to już całkiem myli). Jak się podaje sumę długości, to myli kompletnie przy jakichkolwiek złożonościach nieliniowych (a przy wykładniczych to zupełna katastrofa). Są takie zestawy zadań, gdzie można wszędzie zrobić mało testów, albo wszystkie złożoności są normalnie. A są i takie, gdzie lepiej zrezygnować z podawania liczby, żeby nie szkodzić uczestnikom.

    • Nie posądzam nikogo ani o przekręt, ani o niewiedzę 🙂 Ale wydaje mi się, że w tym konkretnym zadaniu podanie limitu na sumę długości nie zaszkodziłoby uczestnikom.

  2. Mam taką cichą nadzieje, że sporo uprościć może następująca intuicja: w Twoim rozwiązaniu chodzi o znalezienie pewnego zbioru zstępującego (tj. zagnieżdżonych w sobie) palindromów. Upraszczasz sobie zakładając, że odrzucasz zawsze lewą połówkę i wchodzisz do prawej, tj. że mniejszy palindrom musi się w całości zawierać w prawej połówce dużego. Ale ceną za to uproszczenie jest to, że kolejny palindrom może nie być już „w pełnej okazałości najdłuższym możliwym palindromem dla zadanego środka” tylko już niestety takim przyciętym do rozmiarów tej prawej połówki (co zwiększa liczbę rozpatrywanych stanów?). Nadzieję mam jednak taką, że gdyby w takiej sytuacji popatrzeć jednak przychylniej na tę lewą połówkę, to widzimy, że na lewo od niej stoi inna litera (niż na prawo od prawej połówki) więc lustrzane odbicie tego „nienaturalnie przyciętego palindromu” (względem środka dużego palindromu) tym razem jest w sposób naturalny przycięte, bo trafia na niepasującą literkę – tj. tego palindromu po lewej nie da się już przedłużyć. Rodzi się więc pytanie, czy dałoby się spacerować tylko po tych stanach które odpowiadają maksymalnie długim palindromom? Mi się wydaje, że nie, bo dochodzi inny problem: ten wewnętrzny palindrom może być ograniczony nie tylko dlatego, że dochodzi do krańca dużego palindromu, ale też dlatego że dochodzi do jego środka symetrii – tego też nam nie wolno przekroczyć. U Ciebie to się nazywa chyba „odcinaniem najbardziej prawej literki” i chyba to coś nam będzie zawsze generowało stany, które nie są „maksymalne”.

    • Wydaje mi się, że tak czy inaczej trzeba wygenerować _jakieś_ stany, które nie są maksymalne. Ale być może rzeczywiście prawa połówka nie jest najlepszym wyborem.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s