Ale historia!

Dzisiaj rozwiążemy sobie zadanie E z finału Google Code Jam 2013. Zadanie, trzeba przyznać, dość konkretne, bo za aż 50 punktów! Czyli, chyba, bardzo dużo punktów. Choć wymaga raczej cierpliwości niż sprytu, jest dobrą okazją, żeby przećwiczyć sobie pewną sztuczkę związaną z drzewami licznikowymi, która być może nie jest jeszcze całkiem standardowa, no i napisać \mathcal{O}(n\sqrt{\log n}), a to zawsze cieszy.

Treść jest tutaj. W skrócie, rozważamy grę polegającą na wykreślaniu liczb z ciągu. Na samym początku mamy a_1, a_2, \ldots, a_n. Tak długo, jak aktualny ciąg nie jest nierosnący, czyli tak długo, jak a_i < a_{i+1} dla pewnego i, w każdym kroku usuwamy z ciągu dokładnie jedną (dowolnie wybraną) liczbę. W najgorszym wypadku rozgrywka skończy się wtedy, gdy został nam już tylko jeden element, jednak w zależności od tego, które liczby będziemy wykreślać, cała zabawa może trwać dłużej lub krócej. Naszym celem jest zliczenie wszystkich możliwych rozgrywek, czyli różnych sposobów, na jakie można wykreślać liczby tak długo, jak ciąg nie jest nierosnący. Jak to zwykle bywa, liczba ta może być dość spora, należy więc podać ją modulo 10007. W wersji easy n\leq 100, a w wersji n\leq 8000, przy czym w treści jest jakieś dziwne zdanie, które ogranicza liczbę takich maksymalnych testów do 4. Do tego ograniczenia wrócimy dopiero za chwilę, na razie skoncentrujmy się na wersji easy.

Spróbujmy wyobrazić sobie całą rozgrywkę. Zaczynamy od a_1, a_2, \ldots, a_n i powolutku usuwamy kolejne elementy. W pewnym momencie z oryginalnego ciągu zostanie nam tylko (jakiś) podciąg nierosnący, co kończy całą zabawę. Popatrzmy na sytuację tuż przed usunięciem ostatniego elementu (może się zdarzyć, że takiej sytuacji nie ma, bo już oryginalny ciąg jest nierosnący; rozpatrzmy sobie taki przypadek zupełnie osobno; stać nas!). Mamy wtedy podciąg a_{i_1}, a_{i_2}, \ldots, a_{i_k} o takiej własności, że potrzeba i wystarczy usunąć z niego dokładnie jeden element a_{i_j}, aby uzyskać podciąg nierosnący. Taki podciąg z wyróżnionym elementem będziemy dalej nazywać podciągiem prawienierosnącym długości k. Teraz trik jest następujący: jest jasne, że każdej rozgrywce odpowiada jakiś podciąg prawienierosnący. Patrząc na całą kwestię od drugiej strony, każdemu podciągowi prawienierosnącemu odpowiada być może tylko jedna, a być może więcej niż jedna rozgrywka. No, to może umielibyśmy policzyć ile dokładnie rozgrywek odpowiada ustalonemu podciągowi prawienierosnącemu (z wyróżnionym elementem) o długości k? Pewnie, że tak: jest ich dokładnie (n-k)! (wykrzyknik tym razem oznacza silnię). Jest tak dlatego, że po prostu musimy ustalić kolejność usuwania pozostałych elementów. Tak długo, jak nasz wybrany podciąg prawienierosnący jest podciągiem aktualnego podciągu, aktualny podciąg nie może być nierosnący, czyli możemy kontynuować rozgrywkę.

Całe zadanie redukuje się więc do zliczenia podciągów prawienierosnących różnych długości. Wypadałoby więc podać (najlepiej efektywną) charakteryzację ciągów prawienierosnących, co też uczynimy poniżej.

Obserwacja. b_1, b_2, \ldots, b_k z wyróżnionym elementem b_i jest ciągiem prawienierosnącym dokładnie wtedy, gdy b_1 \geq b_2 \geq \ldots \geq b_{i-1} \geq b_{i+1} \geq \ldots \geq b_k oraz (i) i>1 i b_{i-1} < b_i lub (ii) i<k i b_i < b_{i+1}.

historia

Warto zwrócić uwagę na to, że (i) i (ii) nie mogą zachodzić jednocześnie, możemy więc mówić o ciągach prawienierosnących typu (i) i typu (ii). Powyższa charakteryzacja jest o tyle wygodna, że pozwala na stopniowe konstruowanie coraz dłuższych ciągów prawienierosnących. Jeśli bowiem a_{i_1}, a_{i_2}, \ldots, a_{i_k} jest podciągiem prawienierosnącym z wyróżnionym elementem a_{i_j}, mamy bowiem dwie możliwości:

  1. j<k i a_{i_1}, a_{i_2}, \ldots, a_{i_{k-1}} jest podciągiem prawienierosnącym z wyróżnionym elementem a_{i_j},
  2. j=k i a_{i_1}, a_{i_2}, \ldots, a_{i_{k-1}} jest podciągiem nierosnącym.

W dość jednoznaczny sposób sugeruje to rozwiązanie oparte na programowaniu dynamicznym. Widać, że tak naprawdę istotny dla nas jest tylko ostatni element, czyli pewnie dla każdego prefiksu a_1, a_2, \ldots, a_i ciągu wejściowego i każdej możliwej długości k trzeba zliczyć podciągi prawienierosnące długości k, które kończą się na a_i. Wygodne okazuje się rozpatrywanie tylko takich podciągów, w których wyróżniony element nie jest tym ostatnim. Nazwijmy tę liczbę P_{i,k}. Podobnie, niech Q_{i,k} zlicza podciągi nierosnące (też długości k i kończące się na a_i). Teraz chwila na złapanie oddechu.

Wyznaczenie wszystkich Q_{i,k} jest dość łatwe. Oczywiście Q_{i,1}=1. Równie oczywiście Q_{i,k+1} jest sumą tych Q_{j,k}, dla których j<i i a_j \geq i. Powiedzmy, że na razie nie będziemy się wysilać (bo i po co), i policzymy wszystkie Q_{i,k} w czasie \mathcal{O}(n^3).

Wyznaczenie wszystkich P_{i,k} jest już odrobinę trudniejsze. P_{i,k+1} jest pewnie dużą sumą, w której znajdują się wszystkie P_{j,k}, dla których j<i i a_j \geq a_i, jednak musimy także uwzględnić sytuację, w której to a_i jest tym wyróżnionym elementem. W tym celu wystarczy tylko dorzucić Q_{j,k-1} (dla wygody powiedzmy, że zawsze Q_{j,0}=1), dla których j<i i a_j \geq a_i. Jednak każde takie Q_{j,k-1} należy przemnożyć przez liczbę możliwych wyróżnionych elementów, czyli tak naprawdę takich z\in\{j+1,j+2,\ldots,i-1\}, że a_j < a_z lub a_z < a_i. Daje to dość prosta metodę, która pozwala na policzenie wszystkich P_{i,k} w czasie \mathcal{O}(n^4). Dlaczego właśnie tyle? Mamy n^2 wartości do wyznaczenia, każda jest sumą 2n składników, lecz musimy dodatkowo zliczyć "dobre" z. Powiedzmy, że zrobimy to naiwnie.

W zasadzie udało nam się już rozwiązać wersję easy (uważny Czytelnik pewnie przypomni sobie, że nie policzyliśmy wszystkich prawienierosnących podciągów, jednak mając w ręce wszystkie P_{i,k} jest to już jednak łatwe). Dość łatwo jest przyspieszyć ją do \mathcal{O}(n^3) spamiętując wcześniej liczbę "dobrych" z dla każdego możliwego wyboru j i i. Jeśli ktoś woli, można także chytrze wybrać kolejność obliczeń, i wyznaczać tę liczbę naiwnie, lecz tylko raz na jakiś czas. Ale jak zabrać się za rozwiązanie wersji hard?

Wróćmy do limitów z treści zadania. Autorzy wydają się sugerować, że wśród 20 testów 16 ma n\leq 2000, natomiast w co najwyżej 4 może być n=8000. Tak czy inaczej, pierwszym krokiem powinno być przyjrzenie się złożoności pamięciowej naszego rozwiązania. Przechowywanie wszystkich P_{i,k} jest pewnie dość głupie, można jednak wyznaczać je dla coraz większych wartości k, co pozwala na zmniejszenie używanej pamięci do \mathcal{O}(n). No i fantastycznie, lecz ten sześcienny czas działania wydaje się lekko deprymujący. Jak żyć?

Spróbujemy zbić tenże czas do \mathcal{O}(n^2\log n). Co prawda naturalną złożonością (patrząc na n=8000) byłoby \mathcal{O}(n^2), ale… cóż.

Wrócmy do wyznaczania Q_{i,k+1}. Interesuje nas suma tych Q_{j,k}, dla których j<i i a_j \geq a_i, czyli zamiast robić to naiwnie, przydałaby się nam struktura danych, za pomocą której można wyznaczyć taką sumę w czasie \mathcal{O}(\log n). Nic nie przeszkadza nam rozpatrywać kolejno i=1,2,\ldots,n oraz przenumerować na samym początku wszytkie a_i tak, aby pochodziły z zakresu \{1,2,\ldots,n\}, czyli tak naprawdę wystarczyłaby nam magiczna skrzynka, która przechowuje liczby x_1, x_2, \ldots, x_n i umożliwia wykonywanie dwóch operacji:

  1. modyfikacja dowolnej x_i,
  2. wyznaczenie dowolnej sumy x_i + x_{i+1} + \ldots + x_n.

Co oznacza, że w zupełności wystarczy nam zwykłe drzewo licznikowe. No to może równie proste okaże się wyznaczenie P_{i,k+1}?

Nie do końca. Przypomnijmy sobie, że P_{i,k+1} jest sumą pewnych P_{j,k} (ten składnik można wyznaczyć tak jak powyżej korzystając z drzewa licznikowego) oraz pewnych Q_{j,k-1}, lecz przemnożonych przez być może różne współczynniki. Współczynnik przy Q_{j,k-1} to liczba takich z\in\{j+1,j+2,\ldots,i-1\}, że a_j < a_z lub a_z < a_i. Dość problematyczne jest jednak to, że każdy współczynnik zależy zarówno od j jak i od i. Jest na to jednak prosta rada: zliczmy tylko te z\in\{j+1,j+2,\ldots,i-1\}, dla których a_j < a_z. Okazuje się, że pozwala to na policzenie podciągów prawienierosnących typu (i). Jak policzyć te drugie? Wystarczy odwrócić ciąg wejściowy i zanegować każdy element! (nie, nie jest to słynny zwrot o 360 stopni)

Dysponując tym prostym spostrzeżeniem możemy znów rozpatrywać kolejno i=1,2,\ldots,n oraz przenumerować wszystkie a_i. Tym razem potrzebujemy strukturę danych, która przechowuje liczby x_1, x_2, \ldots, x_n oraz aktualne współczynniki c_1, c_2, \ldots, c_n, i umożliwia wykonywanie następujących operacji:

  1. modyfikacja dowolnej x_i,
  2. zwiększenie wszystkich c_1, c_2, \ldots, c_i o jeden,
  3. wyznaczenie dowolnej sumy x_i c_i + x_{i+1}c_{i+1} + \ldots + x_n c_n.

Znów okazuje się, że wystarcza do tego drzewo licznikowe, jednak tym razem trochę mniej standardowe. Jak zwykle, budujemy pełne drzewo binarne na n liściach, które odpowiadają liczbom x_i. W każdym wierzchołku v przechowujemy trzy wartości: sumę wszystkich x_i w całym poddrzewie, aktualną sumę wszystkich x_i c_i w całym poddrzewie, oraz dodatkową wartość \Delta_v, która mówi, o ile należy jeszcze zwiększyć wszystkie c_i w całym poddrzewie. Aktualną sumę wszystkich x_i c_i należy rozumieć tak, że być może nie jest to jeszcze cała prawidłowa suma, jednak do uzyskanie takiej wystarczy dodać sumę x_i w poddrzewie przemnożoną przez sumę \Delta_u po wszystkich u będących przodkami v. Taka sztuczka wystarcza do zaimplementowania każdej z operacji w czasie \mathcal{O}(\log n).

Tyle w kwestii rozwiązania o złożoności \mathcal{O}(n^2\log n). Oczywiście wypadałoby się zastanowić, czy da się lepiej!

Tego co prawda nie wiem, ale nie wydaje mi się, żeby było to łatwe. W szczególności, drobną częścią powyższego rozwiązania było policzenie sumy po wszystkich większych elementach na lewo. Wydaje się to być bardzo blisko związane ze zliczaniem inwersji w permutacji: dla danej permutacji a_1, a_2, \ldots, a_n chcemy policzyć pary i < j, dla których a_i >  a_j. Co prawda uzyskanie dla takiego problemu złożoności poniżej \mathcal{O}(n\log n) nie jest proste, ale okazuje się możliwe. Chan i Pătraşcu skonstruowali rozwiązanie, które wymaga tylko czasu \mathcal{O}(n\sqrt{\log n})! Kuszące wydawałoby się spróbowanie uzyskania złożoności \mathcal{O}(n^2\sqrt{\log n}) dla naszego problemu po prostu stosując ich metodę. Chyba nie jest to jednak tak proste: problematyczny wydaje się już pierwszy krok, którym powinno być uogólnienie rozwiązania tak, aby elementy miały (być może różne) wagi.

Reklamy

Skomentuj

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

Logo WordPress.com

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

Zdjęcie z Twittera

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

Zdjęcie na Facebooku

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

Zdjęcie na Google+

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

Connecting to %s