Ocal drzewa!

Dzisiaj przyjrzymy się zadaniu z UVa Online Judge. Co prawda sporo z setek (a może już nawet tysięcy?) problemów, które można tam zobaczyć, nie jest (delikatnie mówiąc) super interesująca, a interfejs serwisu może wywołać lekki ból głowy, warto zajrzeć na trochę świeższe zadania, które pochodzą z organizowanych co jakiś czas zawodów. Można znaleźć wśród nich kilka prawdziwych perełek. Zadanie, o którym chciałbym Wam opowiedzieć, co prawda ciężko uznać za naprawdę trudne, a więc pewnie równie ciężko uznać je za naprawdę interesujące :), ale jest świetną okazją, aby przedstawić pewną zaskakującą sztuczkę, która pozwoli nam na zbicie złożoności do liniowej.

Naszym zadaniem jest podzielenie ciągu n drzew 1,2,3,\ldots,n na spójne kawałki. Każde drzewo i ma swój typ t_i oraz ustaloną wysokość h_i. Chcemy zminimalizować sumaryczny koszt wynikający z wybranego podziału, przy czym cena związana z każdym kawałkiem to po prostu wysokość najwyższego ze znajdujących się tam drzew. Dodatkowo wymagamy, aby typy drzew w poszczególnych kawałkach nie powtarzały się. Limity na n wydają się sugerować, że potrzebujemy rozwiązania o czasie działania \mathcal{O}(n\log n). No, lub lepszym.

Sformułowanie zadania w dość naturalny sposób sugeruje rozwiązanie oparte na programowaniu dynamicznym. Dla każdego prefiksu 1,2,\ldots,i ciągu wejściowego moglibyśmy wyznaczać koszt najlepszego możliwego podziału c(i). Jak? Na przykład zgadując, że ostatni kawałek to j,j+1,\ldots,i i porównując c(j-1)+\max_{j\leq k\leq i} h(k) z aktualną wartością c(i). Oczywiście zamiast zgadywać musimy tak naprawdę sprawdzić wszystkie możliwości. Zauważmy, że rozważając je w kolejności j=i,i-1,i-2,\ldots,1 pozbędziemy się (potencjalnego) problemu z wyliczaniem kolejnych \max_{j\leq k\leq i} h(k) i sprawdzaniem, czy wszystkie t(j),t(j+1),\ldots,t(i) są rzeczywiście różne. Faktycznie, kolejne maksimum możemy wyznaczyć w stałym czasie na podstawie poprzedniego, a trzymając wszystkie t(k) w jakiejś strukturze danych będziemy mogli sprawdzić ich unikalność. W treści zadania mamy t(k) \leq 20 000, więc tą strukturą może być po prostu tablica indeksowana liczbami od 1 do 20 000. Złożoność takiego rozwiązania to \mathcal{O}(n^2), co jakby nie daje nam nawet najmniejszej szansy na uzyskanie upragnionego Accepted.

Trzeba więc trochę bardziej się wysilić. Przeglądanie wszystkich j było, przyznajmy to wprost, dość naiwne. O wiele lepiej byłoby przechowywać je w jakiejś strukturze danych, która umożliwi wyłuskanie tego najlepszego w rozsądnym czasie.

Przechowywanie w strukturze wszystkich j okazuje się niestety dość kłopotliwe. Spróbujmy trochę inaczej: załóżmy, że znamy H=\max_{j\leq k\leq i} h(k), które odpowiada najlepszemu możliwemu wyborowi j (dla aktualnego i). Łatwo zauważyć, że bez straty ogólności opłaca się przedłużyć ostatni kawałek jak najdalej w lewo, co w tym konkretnym przypadku oznacza, że interesuje nas minimalne j takie, że \max_{j\leq k\leq i} h(k) \leq H oraz wszystkie t(j),t(j+1),\ldots,t(i) są różne. Inaczej mówiąc, wystarczy rozważać tylko następujące j:

  1. jednoznacznie wyznaczone j=b(i), dla którego t(j-1) występuje gdzieś w t(j),t(j+1),\ldots,t(i), lecz wszystkie t(j),t(j+1),\ldots,t(i) są różne,
  2. wszystkie j>b(i), dla których h(j-1)>\max_{j\leq k\leq i} h(j).

Ten drugi warunek najlepiej wyobrażać sobie tak jak na poniższym rysunku.

ocal

W strukturze przechowujemy wszystkie j zaznaczone na szaro, każdemu z nich przyporządkowując wagę c(j-1)+\max_{j\leq k\leq i} h(j). Wyznaczenie c(i) sprowadza się więc do wybrania elementu o największej wadze z naszej struktury i ewentualnego sprawdzenia, czy przypadkiem j=b(i) nie byłoby lepsze. Pozostaje się więc zastanowić jak zmienia się struktura po przejściu z i do i+1. Przede wszystkim musimy wyrzucić z niej wszystkie j\leq b(i+1). Nie jest to niestety wszystko: może się zdarzyć, że i+1 zasłoni niektóre ze znajdujących się tam j. Można jednak zauważyć, że te zasłonięte elementy to zawsze kilka ostatnich spośród aktualnie przechowywanych. Czyli nasza struktura musi umożliwiać przechowywanie listy ważonych elementów, na której umiemy wykonywać następujące operacje:

  1. usuwanie pierwszego elementu,
  2. usuwanie ostatniego elementu,
  3. dodawanie nowego elementu na końcu,
  4. wyznaczanie minimum z wag aktualnie przechowywanych elementów.

Zakładając, że potrafimy zaimplementować taką strukturę, mamy już w zasadzie całe rozwiązanie. Wystarczy tylko zauważyć, że wyznaczenie wszystkich b(i) może być wykonane, tak jak w rozwiązaniu naiwnym, przez przechowywanie w tablicy ostatniego wystąpienia każdego możliwego typu.

Czyli w zasadzie możemy zapomnieć już o oryginalnym sformułowaniu zadania i skupić się na implementacji wyspecyfikowanej wyżej struktury (która wygląda na tyle naturalnie, że.. na pewno jest to właściwe podejście; chyba). Dość łatwo jest uzyskać czas \mathcal{O}(\log n) na każdą operację przechowując elementy używając, na przykład, kopca. Lub jakiegokolwiek zrównoważonego BST. Szanujący się zawodnik powinien jednak zadać sobie pytanie, czy możliwe jest rozwiązanie liniowe.

Rozważmy na początek prostszą wersję, w której nie potrzebujemy usuwać pierwszego elementu. Mówiąc trochę inaczej, chcemy zaimplementować stos, który dodatkowo umożliwi szybkie wyznaczanie minimum ze wszystkich przechowywanych elementów. Cóż. Jest to dość proste. Jeśli aktualna zawartość stosu to [a_1,a_2,\ldots,a_k], konstruujemy stos, na którym przechowujemy wartości \min_{1\leq j\leq i} a_j dla kolejnych j=1,2,\ldots,k. Czyli na przykład dla stosu [4,6,5,3,1,2] konstruujemy [4,4,4,3,1,1]. Wyznaczenie minimum to prostu popatrzenie na ostatni element M, usunięcie ostatniego elementu to usunięcie ostatniego elementu, a dodanie nowego elementu x na końcu to dodanie elementu \min (x,M). Jednak w naszym przypadku konieczne jest także usuwanie pierwszego elementu, co wydaje się istotnie utrudniać życie.

A może jednak wcale nie utrudnia? Zapomnijmy na chwilę o wyznaczaniu minimum. Jednym z prostszych pomysłów na zaimplementowanie dwustronnej kolejki jest przechowywanie jej na dwóch stosach. A dokładniej, jeśli zawartość kolejki to [a_1,a_2,\ldots,a_k], na jednym stosie trzymamy [a_\ell,a_{\ell-1},\ldots,a_1], a na drugim [a_{\ell+1},a_{\ell+2},\ldots,a_k], gdzie \ell jest (jak na razie) bliżej nieokreślonym miejscem podziału. Teraz bez żadnych problemów możemy dorzucić nowy element na początku lub na końcu kolejki odkładając go na odpowiednim stosie. Trochę gorzej wygląda kwestia usuwania elementów. Jeśli chcemy usunąć element z początku i \ell \geq 1, lub jeśli chcemy usunąć element z końca i \ell \leq k-1, nie ma żadnego problemu, po prostu zdejmujemy element z wierzchołka odpowiedniego stosu. Co jednak zrobić, gdy wszystkie elementy leżą na jednym stosie?

Zawsze możemy po prostu wybrać inne \ell. Wymaga to jednak przebudowania całej struktury, mogłoby się więc wydawać, że nie zawsze nas na coś takiego stać. Okazuje się jednak, że staranny wybór nowego \ell może zagwarantować, że choć raz na jakiś czas będziemy musieli wykonać kosztowną przebudowę, to jednak sumeryczny czas działania całej implementacji będzie ograniczony. Naturalne wydaje się wybranie \ell=\left\lfloor \frac{k}{2}\right\rfloor (zakładamy w tym momencie, że k>1), gdyż w pewnym sensie najbardziej oddala on nas od smutnej sytuacji, w której wszystkie elementy znajdują się na tym samym stosie. No dobrze, czyli gdy tylko \ell=0 lub \ell=k, przebudowywujemy całą strukturę w czasie \mathcal{O}(k). Pozostaje oszacować całkowity czas działania takiej implementacji.

Pokażemy, że sumaryczny czas wykonania dowolnych m operacji nigdy nie przekroczy \mathcal{O}(m). Inaczej mówiąc, zamortyzowany czas działania każdej operacji jest stały. W tym celu zdefiniujemy potencjał struktury jako \Phi=|\ell - (k-\ell)|. Jest to w pewnym (dość bliskim rzeczywistości) sensie miara tego, jak smutna jest nasza aktualna sytuacja. Będziemy zakładać, że dysponujemy zapasem \Phi bonusowych jednostek czasu, których możemy użyć na wykonanie kosztownej operacji przebudowy, przy czym jest to tylko i wyłącznie zmiana sposobu myślenia o analizie złożoności: zarówno \Phi jak i wspomniane bonusowe jednostki czasu nijak nie pojawiają się w samej implementacji. Popatrzmy na sytuację z \ell=0 lub \ell=k. Wtedy \Phi=k, czyli możemy wykorzystać część z tych k jednostek czasu na przebudowę struktury. Potencjał po przebudowie to 0 lub 1, czyli w zasadzie możemy wykorzystać nawet nie tyle ich część, co wszystkie. Należy jeszcze uważnie przyjrzeć się operacji usuwania i dodawania elementów (zarówno na początku, jak i na końcu). Potencjał \Phi' struktury po takiej operacji nie może być większy niż \Phi+1, czyli w najgorszym przypadku potrzebujemy odłożyć jeszcze jedną jednostkę czasu. Nie przysparza to większych problemów, gdyż możemy po prostu udawać, że czas działania tych operacji jest o jeden większy.

Czyli umiemy już zaimplementować dwustronną kolejkę za pomocą dwóch stosów. Teraz wystarczy już tylko zauważyć, że daje nam to szybką implementację takiej kolejki, która dodatkowo pozwala na wyznaczanie minimum. Wystarczy tylko zaaplikować do obydwu stosów sztuczkę z przechowywaniem \min_{1\leq j\leq i} a_j (przy czym teraz powinniśmy tak naprawdę odkładać pary (a_i,\min_{1\leq j\leq i} a_j), gdyż informacja o oryginalnej wartośc a_i może być nam potrzebna podczas przebudowy). Co daje implementację o stałym czasie działania wszystkich operacji, choć w przypadku aktualizacji czas ten jest zamortyzowany.

Można by się zastanawiać, czy amortyzacja, z której tak chętnie skorzystaliśmy, faktycznie jest konieczna. W końcu w pewnych (naciąganych) zastosowaniach konieczność długiego oczekiwania na przetworzenie jednego żądania może być wysoce irytująca, nawet jeśli zdarza się to tylko raz na jakiś czas. Okazuje się, że można skonstruować strukturę danych o takich samych czasach działania, ale w najgorszym przypadku. Jest to jednak trochę bardziej skomplikowane.

Można by się także zastanawiać, jak szybko dałoby się rozwiązać wersję zadania, w której koszt fragmentu to nie maksimum, a mediana…

Reklamy

Jedna myśl nt. „Ocal drzewa!

  1. Pingback: Lepsza produktywność | Fajne zadania

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