Ewolucja

Dzisiaj obiecane w poprzednim odcinku całkiem świeże zadanie z finałów ACM ICPC 2015. Co prawda nie jest ono najtrudniejsze w całym zestawie (bo tego najtrudniejszego nie umiem), ale mimo zgrabnej treści nie jest też takie całkiem proste. A co najważniejsze, jest z algorytmów tekstowych!

Treść zadania można zobaczyć tutaj. Po lekkim przekształceniu i wywaleniu niepotrzebnych ozdobników brzmi ona jakoś tak: dostajemy n napisów, każdy o długości co najwyżej n. Czy da się podzielić je na dwa łańcuchy, gdzie łancuchem nazywamy sekwencję napisów, z których każdy kolejny jest nadciągiem poprzedniego? Na przykład, takim poprawnym łańcuchem jest A, AA, ACA, ACMAA, bo A jest podciągiem AA, które z kolei jest podciągiem ACA, które jest podciągiem ACMAA. Zwrócmy uwagę na to, że podciąg oznacza tutaj niekoniecznie spójny podciąg!

Zanim zabierzemy się za rozwiązywanie właściwej części zadania, zastanówmy się przez minutę nad tym, jak sprawdzić czy jeden napis jest podciągiem drugiego. Oznaczmy napisy przez A[1..m] i B[1..n], gdzie m\leq n. Jeśli A[1]=B[1], wystarczy sprawdzić czy A[2..m] jest podciągiem B[2..n], nie ma bowiem żadnego powodu, by „dopasować” literę A[1] do jakiejkolwiek dalszej niż B[1]. Jeśli zaś A[1]\neq B[1], należy sprawdzić czy A[1..m] jest podciągiem B[2..n], bo litera B[1] jest dla nas, niestety, bezużyteczna. Rozsądna implementacja takiego rozumowania działa w czasie \mathcal{O}(n).

Teraz możemy już skonstruować pierwsze rozwiązanie (standardowo, zbyt wolne) oparte na programowaniu dynamicznym. Oznaczmy kolejne napisy przez s_1,s_2,\ldots,s_n (posortowane tak, aby ich długości były niemalejące). Każdy łańcuch jest teraz postaci s_{i_1},s_{i_2},\ldots,s_{i_k} dla pewnych i_1 < i_2 < \ldots < i_k, gdzie s_{i_1} jest podciągiem s_{i_2}, s_{i_2} jest podciągiem s_{i_3}, i tak dalej. Przypomnijmy, że chcemy podzielić wszystkie s_1,s_2,\ldots,s_n na dwa łańcuchy. Naturalne jest więc podzielenie s_1,s_2,\ldots,s_{n-1} na dwa łańcuchy, a następnie doklejenie s_n na końcu jednego z tych łańcuchów. Uogólniając ten pomysł, dla każdego i=1,2,3,\ldots,n chcemy wyznaczyć podział s_1,s_2,\ldots,s_n na dwa łańcuchy. Takich podziałów może być wiele, jednak istotne są dla nas tylko ich ostatnie elementy: jeden z nich to na pewno s_i, a drugi… nie wiadomo. Dla każdego i mamy więc i możliwych końców tego drugiego łańcucha (tak naprawdę tylko i-1 plus specjalny przypadek, w którym drugi łańcuch jest całkiem pusty), co daje w sumie \mathcal{O}(n^2) stanów. Odpowiedź dla każdego z nich wyznaczamy zauważając, że mając dany podział s_1,s_2,\ldots,s_{i-1} na dwa łańcuchy, jeden kończący się na s_{i-1} a drugi na s_j (dla jakiegoś j<i), możemy skonstruować podział s_1,s_2,\ldots,s_i na jeden z dwóch sposobów:

  1. doklejając s_i do pierwszego łańcucha tuż za s_{i-1}, lub
  2. doklejajac s_i do drugiego łańcucha tuż za s_j.

Po chwili zastanowienia pozwala nam to wyznaczyć odpowiedź dla każdego stanu używając stałej liczby operacji. Stanów jest \mathcal{O}(n^2) czyli koniec.

No nie, nie koniec. Milcząco założyliśmy, że każda operacja zajmuje czas stały. Ale przecież zanim dokleimy s_i do któregokolwiek łańcucha wypada sprawdzić, czy poprzedni koniec (czyli s_{i-1} lub s_j) jest podciągiem s_i. Więc tak naprawdę sumaryczna złożoność to \mathcal{O}(n^3). Trzeba jakoś sprytniej.

Wyobraźmy sobie wszystkie możliwe podziały s_1,s_2,\ldots,s_i na dwa łańcuchy. Niech j_1 < j_2 < \ldots j_k będą możliwymi końcami drugiego łańcucha w tych podziałach (pierwszy łańcuch kończy się zawsze w s_i). Wiemy, że wszystkie s_{j_1+1},s_{j_1+2},\ldots,s_{i-1} są podciągami s_i, gdyż należą do tego samego łańcucha w pewnym rozwiązaniu. To oznacza, że nie ma sensu zapamiętywać podziałów, w których koniec drugiego łańcucha to s_{j_3},s_{j_4},\ldots,s_{j_k}. Wszystkie one są bowiem "gorsze" od tego, w którym koniec drugiego łańcucha to s_{j_2} (w tym sensie, że jeśli można przedłużyć dowolny z nich, to równie dobrze można by przedłużyć ten kończący się w s_{j_2}). Więc zamiast rozważać wszystkie możliwe drugie końce, wystarczy zapamiętać tylko te dwa najwcześniejsze (to jest o najmniejszych indeksach)!

Bardziej szczegółowo, dla kolejnych i=1,2,3,\ldots,n konstruujemy listę poprawnych końców drugiego łańcucha. Gdy tylko okaże się, że ta lista jest pusta dla pewnego i, kończymy pracę. Mając listę dla pewnego i próbujemy przedłużyć każdy z podziałów odpowiadających jej elementom doklejając s_{i+1} do jednego lub drugiego łańcucha. Następnie "przycinamy" listę rozwiązań wyliczoną dla i+1 zachowując tylko jej dwa najmniejsze elementy. Zmniejsza to liczbę rozważanych stanów do \mathcal{O}(n) i co za tym idzie daje proste rozwiązanie działające w sumarycznym czasie \mathcal{O}(n^2).

Advertisements

3 myśli nt. „Ewolucja

  1. Ja wymyśliłem takie coś: najpierw próbujemy „na rozgrzewkę” sprawdzić wszystkie sąsiednie pary, tj. czy s[i] <= s[i+1]. To możemy zrobić w liniowym czasie i tworzy nam takie "łatwe kawałki". Jeśli jakieś dwa kolejne s[i] oraz s[i+1] nie tworzą dobrej pary, to na pewno są w dwóch różnych ciągach. Jedno podejście (którego nie będę analizował) to w tym miejscu podzielić problem rekurencyjnie na dwa mniejsze, itd. Tak czy owak doprowadzi to do tego samego pomysłu: musimy nauczyć się rozwiązywać sytuację w której mamy "łatwy kawałek" (być może długości 0) otoczony z obu stron niepokornymi parami. Czyli s[0] nie zawiera się w s[1], s[1]<=s[2]<=…<=s[k], s[k] nie zawiera się w s[k+1]. Wiemy, że s[0] i s[1] będą różnych barw, oraz s[k] i s[k+1] będą różnych. Jak sobie to rozrysujemy to widać, że są tylko dwie (nie wykluczające się) opcje:
    1. s[0] <= s[k+1]. Wtedy rozwiązaniem jest połaczyć s[0] z s[k] w jeden ciąg, a drugim będzie "łatwy kawałek".
    2. s[0] <= s[i] AND s[i-1] <= s[k+1] dla pewnego i. Wtedy rozwiązaniem są dwa ciągi: s[0]<=s[i]<=s[i+1]…<=s[k] oraz s[1]<=…<s[i-1]<=s[k+1].
    Pierwszy przypadek wykrywamy jednym testem.
    Do drugiego potrzebuję niestety binary searcha, na całym "łatwym kawałku".
    Suma łatwych kawałków jest mniejsza niż n, więc łącznie te binarysearche wymagają nlgn testów.

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