Liście

Co prawda nie miałem nic wspólnego z układaniem tego zadania, ale… dzięki temu mogę przynajmniej bez zbędnych wyrzutów sumienia powiedzieć, że jest bardzo ładne. Pojawiło się prawie 10 lat temu na VIII Akademickich Mistrzostwach Polski w Programowaniu Zespołowym, które były wtedy organizowane przez Insytut Informatyki Uniwersytetu Wrocławskiego, a niektórzy z Was być może widzieli całkiem niedawno jego odgrzewaną wersję. Oryginalną treść możecie przeczytać tutaj, ale pewnie szybciej po prostu popatrzeć przez chwilę na poniższy rysunek.

liscie-grid

Mamy daną tabelkę składającą się z n\times n pól. W każdym z nich znajduje się liczba z zakresu \{0,1,2\}. Chcemy podzielić naszą tabelkę na dwie części zaczynając w lewym górnym rogu i poruszając się wyłącznie w prawo lub w dół tak długo, jak nie dotrzemy do prawego dolnego rogu. Podział nazywamy dobrym, gdy suma liczb w obydwu otrzymanych kawałkach jest taka sama. W zadaniu jesteśmy proszeni o znalezienie takiego dobrego podziału lub stwierdzenie, że nie jest to możliwe.

Zamiast myśleć o podziale tabelki na dwie części lepiej myśleć, że szukamy poprawnej ścieżki z (0,0) do (n,n) (gdzie poprawna oznacza tylko tyle, że w każdym kroku idziemy w prawo lub w dół), na prawo której (czyli w szarej części) mamy liście o sumarycznej wadze X. X to po prostu połowa sumy wszystkich liczb, przy czym jeśli ta suma jest nieparzysta, możemy z czystym sumieniem wypisać NIE i zakończyć pracę. Co prawda jesteśmy zainteresowani głównie poprawnymi ścieżkami z (0,0) do (n,n), ale (jak to zwykle bywa) możemy trochę uogólnić problem i przyglądać się poprawnym ścieżkom z (0,0) do dowolnego (i,j). Waga takiej niedokończonej ścieżki to po prostu suma wszystkich liczb, które znajdują się na prawo. Powiedzmy, że S(i,j) to zbiór wag wszystkich cześciowych (ale poprawnych) ścieżek z (0,0) do (i,j).

Na dobry początek zauważmy, że wyznaczenie wszystkich S(i,j) jest dość łatwe, o ile tylko nigdzie nam się nie śpieszy. Wystarczy wyliczać zbiory dla kolejnych i oraz j w następujący sposób: S(i,j) zawiera wszystkie liczby z S(i,j-1) oraz wszystkie liczby z S(i-1,j) powiększone o sumę liczb w polach (i,j), (i,j+1), \ldots, (i,n-1) (wiersze i kolumny numerujemy oczywiście od 0 do n-1, no bo czemu nie?). S(0,0) zawiera zaś tylko 0. Daje to dość łatwe do zaimplementowanie rozwiązanie o złożoności… no właśnie, jakiej? Mamy O(n^2) zbiorów, przy odrobinie staranności każdy może być wyliczony w czasie O(X), czyli cała złożoność to O(n^2 X). Niestety, X może być rzędu n^2 (i, jeśli autorzy testów zachowali choć minimum rozsądku, pewnie rzeczywiście takie jest, przynajmniej w niektórych testach). Musimy więc poszukać lepszego pomysłu.

Przyjrzyjmy się bliżej elementom S(i,j). Nie ma sensu przechowywać tam liczb, które są zbyt duże, czyli większe niż X. Podobnie, nie ma sensu przechowywać tam liczb, które są za małe, czyli mniejsze niż X-m(i,j), gdzie m(i,j) jest największą możliwą wagą poprawnej ścieżki z (i,j) do (n,n). Możemy mieć nadzieję, że takie przycięcie wszystkich S'(i,j) = S(i,j) \cap [X-m(i,j),X] znacząco zmniejszy ich sumaryczny rozmiar, ale niestety jest to dość dalekie od prawdy. Na szczęście okazuje się, że zbiory S'(i,j) są zadziwiająco regularne!

Załóżmy, że jakiś S'(i,j) zawiera zarówno t jak i t+1. Oznacza to, że możemy bez większych problemów skonstruować ścieżkę o wadze X używając następującej zachłannej metody: zaczynając od ścieżki z (i,j) do (n,n) o wadze 0 zastępuj aktualną ścieżkę przez taką, której waga jest większa 1 lub 2 tak długo, jak waga aktualnej ścieżki jest ściśle mniejsza niż X-t-1. Następnie doklej aktualną ścieżkę do tej łączącej (0,0) z (i,j) o wadze t lub t+1, w zależności od tego czy końcowa waga to X-t-1 czy też X-t. Poprawność tej zachłannej metody wymaga kilku prostych obserwacji:

  1. jeśli waga aktualnej ścieżki jest ściśle mniejsza niż m(i,j), możemy łatwo zastąpić ją ścieżką, której waga jest większa o 1 lub 2 powtarzając (być może wiele razy) operację przedstawioną na poniższym rysunku:

    liscie-replace

  2. skoro t<X-m(i,j), waga aktualnej ścieżki nigdy nie przekroczy m(i,j).
  3. skoro za każdym razem zwiększamy wagę o co najwyżej 2, prędzej lub później zakończymy pracę z wagą równą X-t-1 lub X-t.


Przy odrobinie staranności cała procedura zastępowania może być zaimplementowana w sumarycznym czasie O(n^2). Od tego momentu możemy założyć, że wszystkie S'(i,j) są postaci \{a,a+2,a+4,\ldots,a+2b\}, a więc możemy je przechowywać w skompresowanej postaci: zamiast pamiętać wszystkie elementy, zapisujemy tylko a i b! Oczywiście trzeba uważać, i gdy tylko zauważymy, że jakiś S'(i,j) jednak zawiera dwie sąsiednie liczby, przerywamy pracę i wypisujemy rozwiązanie.

W zasadzie kończy to całą zabawę. Przeglądamy kolejne (i,j) w sensownej kolejności i wyznaczamy skompresowane opisy kolejnych S'(i,j). W tym celu wystarczy (tak jak w prostych rozwiązaniu, od którego zaczęliśmy) popatrzeć na zbiór S'(i-1,j) przesunięty o sumę liczb w polach (i,j), \ldots, (i,n-1) i oryginalny zbiór S'(i,j-1). Czyli, mówiąc inaczej, bierzemy dwa skompresowany zbiory i tworzymy skompresowany opis ich sumy. Lub stwierdzamy, że zawiera on dwie sąsiednie liczby, i należy zakończyć pracę. Ze względu na to, jak zdefiniowaliśmy S'(i,j), nie jest możliwa sytuacja, że suma nie zawiera dwóch takich liczb, ale jednocześnie nie jest postaci \{a,a+2,\ldots,a+2b\}.

Całe rozwiązanie działa w czasie O(n^2), czyli liniowym od rozmiaru wejścia. Ale można zastanowić się nad trochę trudniejszą wersją, w której dostajemy na wejściu tylko listę niezerowych pól…

Advertisements

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