Zamiana

Na rozgrzewkę przed zbliżającymi się finałami ACM ICPC proponuję przyjemne zadanie o „zepsutej” procedurze heapify z Baltic Olympiad in Informatics 2016. Zadania nie jest kosmicznie trudne, więc skomplikujemy sobie życie próbując skonstruować rozwiązanie, które działa w czasie liniowym.

W zadaniu dostajemy permutację p(1),p(2),\ldots,p(n). Dla kolejnych i=2,3,\ldots,n mamy możliwość zamienienia p(i) z p(\lfloor i/2\rfloor ). Chcemy umiejętnie wybrać wykonywane zamiany tak, aby otrzymana na samym końcu permutacja była jak najmniejsza leksykograficznie. Nieco przypomina to znaną procedurę heapify, która konstruuje kopiec zawierający podane n liczb. W tejże procedurze idziemy jednak od drugiej strony, to znaczy przeglądamy i=n,n-1,\ldots,2 i zamieniamy p(i) z p(\lfloor i/2\rfloor) jeśli p(i)>p(\lfloor i/2\rfloor). Pozwala to na skonstruowanie całego kopca w czasie \mathcal{O}(n) zamiast \mathcal{O}(n\log n), które otrzymalibyśmy wstawiając każdą liczbę osobno. Co prawda nie wiem, czy ta procedura była inspiracją dla autora, ale wygodnie będzie myśleć o naszych liczbach w kategoriach drzewa, w którym wierzchołek \lfloor i/2\rfloor jest ojcem wierzchołka i. Wykonywane zamiany będziemy opisywać właśnie w takim języku.

Zacznijmy od początku, czyli pomyślmy o pierwszym elemencie końcowej permutacji. Nie mamy w tej kwestii wielkiego wyboru: może to być tylko i wyłącznie p(1), p(2) lub p(3). Skoro interesuje nas zminimalizowanie końcowej permutacji, wystarczy rozważyć trzy przypadki:

  1. jeśli p(1) < p(2), p(3) nie możemy zamienić korzenia z żadnym z jego dzieci,
  2. jeśli p(2) < p(1), p(3) musimy zamienić korzeń z jego lewym dzieckiem oraz nie możemy zamienić korzenia z jego prawym dzieckiem,
  3. jesli p(3) < p(1), p(2) musimy zamienić korzeń z jego prawym dzieckiem. W tym przypadku mamy jednak pewien wybór: możemy najpierw zamienić korzeń z lewym dzieckiem, a następnie z prawym, lub od razu zamienić korzeń z prawym dzieckiem.

W dwóch pierwszych przypadkach nie mamy więc żadnej dowolności. Zauważmy, że po wykonaniu wszystkich zamian dotyczących korzenia interesuje nas niezależne zminimalizowanie permutacji otrzymanej przez wypisanie liczb w lewym poddrzewie i permutacji otrzymanej przez wypisanie liczb w prawym poddrzewie (wypisujemy w kolejności od góry do dołu i od lewej do prawej). Możemy więc po prostu odpalić się rekurencyjnie dla obydwu dzieci. (Trzeba także pamiętać o przypadku, w którym jest tylko jedno dziecko lub nie ma żadnego.) Ale co zrobić w tym trzecim?

Odpowiednio wykonując zamiany dotyczące korzenia możemy doprowadzić do jednej z dwóch przedstawionych niżej sytuacji.

zamian

Najfajniej byłoby od razu zdecydować, która z nich jest bardziej korzystna, i odpalić się rekurencyjnie. Niestety, nie jest to takie proste! Nie wiadomo gdzie ostatecznie trafią liczby p(1) oraz p(2), więc ciężko ocenić co pozwoli na uzyskanie mniejszej końcowej permutacji. Widać jednak, że wystarczyłoby sprawdzić obie możliwości, to znaczy:

  1. wstawić p(1) w wierzchołek 2 i rekurencyjnie rozwiązać problem dla lewego poddrzewa oraz wstawić p(2) w wierzchołek 3 i rekurencyjnie rozwiązać problem dla prawego poddrzewa,
  2. wstawić p(2) w wierzchołek 2 i rekurencyjnie rozwiązać problem dla lewego poddrzewa oraz wstawić p(1) w wierzchołek 3 i rekurencyjnie rozwiązać problem dla prawego poddrzewa.

Mamy więc pierwszy pomysł na rozwiązanie. Dla każdego wierzchołka u definiujemy podproblem T(u,x) jako znalezienie najmniejszej leksykograficznie permutacji, którą można otrzymać z poddrzewa zaczepionego w wierzchołku u, przy czym zamiast p(u) wpisujemy tam x (w pozostałych wierzchołkach poddrzewa zostawiamy pierwotne wartości). Rozważając opisane powyżej trzy przypadki możemy rozwiązać T(u,x) odwołując się do mniejszych podproblemów. W trzecim z nich musimy wybrać mniejszą z otrzymanych dwóch permutacji (każdą z tych permutacji trzeba zaś skonstruować odpowiednio splatając permutacje otrzymane z wywołań rekurencyjnych). Ale czy tych podproblemów nie będzie zbyt wiele?

Nie będzie. Zauważmy bowiem, że w każdym T(u,x) liczba x pierwotnie znajdowała się albo w jednym z przodków u (w szczególności, być może w samym u) albo w bracie jednego z tych przodków. Czyli w sumie mamy tylko \mathcal{O}(n\log n) podproblemów. Całkowita złożoność czasowa będzie jednak odrobinę gorsza, w każdym podproblemie musimy bowiem wygenerować szukaną permutację. Czyli jeśli poddrzewo zaczepione w u ma rozmiar s, płacimy \mathcal{O}(s). Sumując po wszystkich wierzchołkach dostajemy:

\sum_{i=0}^{\log n} 2^i \cdot i \cdot \frac{n}{2^i} = \mathcal{O}(n\log^2n).

Czyli nie tragicznie, ale też nie ma się z czego cieszyć. Próbujemy dalej.

Odrobinę smutne w powyższym rozwiązaniu wydaje się jawne konstruowanie każdej permutacji. Może dałoby zapisać informację o optymalnym rozwiązaniu w bardziej zwięzły sposób?

Wyobraźmy sobie permutację wyznaczone przez T(u,x) dla coraz większych wartości x (zaczynając od, powiedzmy, x=0). Niech q(1),q(2),\ldots,q(i-1),x,\ldots będzie rozwiązaniem dla aktualnego x. Zauważmy, że po zwiększeniu x aktualne rozwiązanie na pewno wciąż będzie się zaczynało od q(1),q(2),\ldots,q(i-1). Być może jednak zdarzy się tak, że teraz opłaca się „przepchać” x trochę dalej w prawo, a na i-tej pozycji pojawi się liczba mniejsza niż aktualne (czyli to zwiększone) x. Twierdzimy, że zamiast całej permutacji wystarczy wyliczać i, a dokładniej głębokość w drzewie wierzchołka, który odpowiada tej pozycji w permutacji.

Wystarczy pokazać, że faktycznie tak jest gdy p(2u+1) < x, p(2u). Oznaczmy m = \min(x,p(2u) i M = \max(x,p(2u)) oraz niech d i d' będą głębokościami, na które trafi m w optymalnym rozwiązaniu dla T(2u,m) i T(2u+1,m). Wyobraźmy sobie, że d \leq d' i porównajmy rozwiązania otrzymane z przeplecenia rozwiązań dla T(2u,m) i T(2u+1,M) oraz przeplecenia rozwiązań dla T(2u,M) i T(2u+1,m). Po chwili zastanowienia widac, że skoro d\leq d' to te przeplecenia różnią się w miejscu odpowiadającym wierzchołkowi, w który ostatecznie trafia m w T(2u,m), a dokładniej w pierwszym przepleceniu mamy tam m, a w tym drugim jakąś większą liczbę. Czyli to pierwsze jest na pewno lepsze! Analogiczne rozumowanie pokazuje, że dla d > d' lepsze jest to drugie.

No fajnie, czyli teraz dla każdego T(u,x) wyznaczamy tylko jedną liczbę, co zmniejsza całkowity czas działania do \mathcal{O}(n\log n). Czy można szybciej?

Spróbujmy. Konieczne wydaje się zmniejszenie liczby rozwiązywanych podproblemów, których w tej chwili jest z grubsza n\log n (a przynajmniej tyle daje nasze oszacowanie). Jednak ostatecznie dla danego x interesuje nas tylko wyznaczenie głębokości wierzchołka, w którym znajdzie się x w optymalnym rozwiązaniu. Jak już wcześniej zauważyliśmy, te głębokości się niemalejące. Równie dobrze można by więc wyznaczyć dla każdej możliwej głębokości d najmniejsze x, które znajdzie się na głębokości d w optymalnym rozwiązanie. Ale dlaczego miałoby to być lepszym pomysłem?

Jeśli wysokość poddrzewa zaczepionego w u jest równa h to interesuje nas teraz wyznaczenie tylko h+1 liczb (zamiast 2(\log n-h+1) tak jak wcześniej). Sumując po wszystkich wierzchołkach otrzymujemy:

\sum_{h=0}^{\log n} \frac{n}{2^h} (h+1) = \mathcal{O}(n)

gdzie skorzystaliśmy ze zbieżności szeregu \sum_{i=0}^{\infty}\frac{i}{2^i}. Czyli teraz musimy wyznaczyć tylko liniowo wiele liczb!

Pozostaje jednak upewnić się, że wyznaczenie każdej z nich nie będzie zbyt kosztowne. Jest to odrobinę żmudne, ale niezbyt trudne (obliczeniowo). Najbardziej skomplikowany jest znów przypadek, w którym mamy do wyboru dwie możliwości, czyli p(2u+1) < p(2u). Przypomnijmy, że interesuje nas wyznaczenie "granicznych" wartości x, które odpowiadają kolejnym głębokościom w drzewie. Należy rozpatrzeć trzy możliwości:

  1. x \leq p(2u+1), wtedy x na pewno zostanie w wierzchołku u,
  2. p(2u+1) < x \leq p(2u), wtedy należy dokonać wyboru na podstawie głębokości, na której znajdzie się x w lewym i prawym dziecku. Trzeba więc rozważyć graniczne wartości x wyznaczone wcześniej w obydwu dzieciach (ale tylko te spełniające obydwie nierówności!),
  3. p(2u) < x, wtedy wybór jest wykonywany na podstawie głębokości, na której znajdzie się p(2u). Wiedząc, do którego dziecka trafia x, możemy skopiować graniczne wartości, które wcześniej w nim wyznaczyliśmy (pamiętając o warunku p(2u) < x.

Przy zachowaniu pewnej staranności możemy wyznaczyć wszystkie graniczne wartości w czasie proporcjonalnym do liczby granicznych wartości wyznaczonych wcześniej w obydwu dzieciach, czyli w sumarycznym czasie liniowym.

Ale chwila. Przecież w zadaniu jesteśmy proszeni o wypisanie permutacji, a już drugie z opisanych rozwiązań skupiało się tylko i wyłącznie na wyznaczeniu głębokości x w optymalnej permutacji! Nietrudno jednak napisać osobną procedurę, która na podstawie tych głębokości (które można odtworzyć na żądanie także w tym szybszym rozwiązaniu) zrekonstruuje permutację. Chcąc wyznaczyć optymalną permutację dla poddrzewa zaczepionego w u musimy tylko umieć zdecydować, która z dwóch możliwości jest lepsza i uruchomić się rekurencyjnie. Taką decyzję trzeba podjąć tylko gdy p(2u+1)<p(u),p(2u). Wtedy zamieniamy p(2u+1) z p(u), a następnie porównujemy głębokości m=\min(p(2u),p(2u+1)) w optymalnych rozwiązaniach dla T(2u,m) i T(2u+1,m), być może zamieniamy p(2u) i p(2u+1), a następnie wywołujemy się rekurencyjnie dla 2u i 2u+1. Nawet jeśli dobranie się do jednej z tych głębokości wymaga czasu h, gdzie h jest wysokością poddrzewa zaczepionego w u, całkowity czas potrzebny na odtworzenie permutacji nie przekroczy liniowego.

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