Superkomputer

Co prawda w poprzednim odcinku obiecywałem tekstówkę, ale w międzyczasie wpadło mi w oko ciekawe zadanko dotyczące szeregowania programów na superkomputerze. Zadanko pojawiło się na drugim etapie XXI Olimpiady Informatycznej i, jak pewnie zwykle przy szeregowaniu, sprowadza się do udowodnienia poprawności prostej strategii zachłannej, jednak w tym przypadku efektywne zaimplementowanie tej strategii wcale nie jest takie oczywiste. Co nawet lepsze, w rozwiązaniu pojawi się (jak zwykle) odrobina geometrii.

Treść można sobie zobaczyć tutaj. Dostajemy n programów, z których każdy (poza tym z numerem 1) ma określonego rodzica. Program może być wykonany, jeśli wcześniej wykonany został jego rodzic (lub jego numer to 1). W jednej jednostce czasu możemy jednocześnie wykonać aż do k programów. Teraz naszym zadaniem jest wyznaczanie, ile jednostek czasu potrzeba na wykonanie wszystkich programów. Żeby było trudniej, należy odpowiedzieć na to pytanie dla wielu wartości k=k_1,k_2,\ldots,k_q. Limity n\leq 10^6 i q\leq 10^6 sugerują, że autor pewnie oczekuje rozwiązania liniowego, choć z drugiej strony był na tyle miły, że częściowe punkty można dostać już za rozwiązanie, które działa w czasie \mathcal{O}(nq).

Wygodniej będzie patrzeć na sytuację od drugiej strony, czyli tak, że program może być wykonany, jeśli wykonane zostały już wszystkie jego dzieci. Tak naprawdę mamy więc drzewo opisujące relacje między poszczególnymi programami, i w kolejnych krokach odcinamy z niego po (co najwyżej) k liści.

Zacznijmy od trywialnej obserwacji: jeśli aktualne drzewo ma mniej niż k liści, jedynym sensownym wyborem jest odcięcie ich wszystkich, jeśli zaś ma ich przynajmniej k … no, to na pewno nie warto odciąć ich mniej niż k. Ale co zrobić jeśli jest ich więcej niż k? Które liście wybrać? Okazuje się, że działa prosta strategia zachłanna: wybieramy te liście, które są najbardziej odległe od korzenia. W tym momencie proponuję przerwać na chwilę lekturę, żeby zaimplementować opisaną strategię i przekonać się, że dostaje ona 35 punktów.

OK, ale dlaczego taka strategia działa? I, co pewnie bardziej istotne, jak zaimplementować ją tak, aby całe rozwiązanie działało w czasie \mathcal{O}(n) zamiast \mathcal{O}(nq)?

Zauważmy, że liczba liści w aktualnym drzewie na pewno nie rośnie. Oznacza to, że przez ileś początkowych tur (być może 0) jest ona równa przynajmniej k, a potem aż do samego końca jest mniejsza niż k. Nazwijmy tę wielkość szerokością drzewa.

Lemat 1. Jeśli szerokość aktualnego drzewa nie przekracza k, to liczba tur potrzebnych i wystarczających na wykonanie wszystkich programów jest równa wysokości drzewa.

Dowód. Liczba tur nie może być mniejsza, gdyż w każdej z nich możemy zmniejszyć wysokość o co najwyżej jeden. Nie musi być większa, bo skoro szerokość nie przekracza k, w każdym kroku możemy usuwać wszystkie liście, czyli zmniejszać wysokość o jeden.

Czyli drzewa o szerokości mniejszej (a nawet równej) k mamy już załatwione. Wcześniej, czyli tak długo, jak szerokość jest przynajmniej k, w każdej turze będziemy usuwać dokładnie k liści. Sytuacja nie jest jednak w pełni deterministyczna, gdyż w zależności od tego, które liście będziemy usuwać, wysokość otrzymanego drzewa o szerokości mniejszej niż k może być mniejsza lub większa. Powiedzmy jednak, że dostaliśmy życzliwą podpowiedź: wysokość pierwszego otrzymanego drzewa o szerokości mniejszej niż k to dokładnie h. Czyli wcześniej pozbyliśmy się wszystkich wierzchołków na głębokości h+1,h+2,\ldots w oryginalnym drzewie, i to w taki sposób, że w każdej turze usuwaliśmy k liści (zauważmy jednak, że niby niekoniecznie były to liście na głębokości przynajmniej h+1, ale tak naprawdę nie opłaca się usuwać wcześniej tych o mniejszej głębokości). Jeśli więc oznaczamy przez c_i liczbę wierzchołków na głębokości i, to sumaryczna liczba tur jest równa przynajmniej h+\left\lceil \frac{c_{h+1}+c_{h+2}+\ldots}{k} \right\rceil. Teraz zauważmy, że jest to prawdą niezależnie od wyboru h! (Tak długo, jak c_h \geq 1.)

Doszliśmy więc do wniosku, że wynik to przynajmniej \max_{h: c_h \geq 1} h+\left\lceil \frac{c_{h+1}+c_{h+2}+\ldots}{k} \right\rceil. Teraz okazuje się, że te dwie liczby są tak naprawdę równe.

Lemat 2. Na wykonanie wszystkich programów wystarczy H=\max_{h: c_h \geq 1} h+\left\lceil \frac{c_{h+1}+c_{h+2}+\ldots}{k} \right\rceil tur.

Dowód. Jeżeli szerokość aktualnego drzewa nie przekracza k, liczba potrzebnych tur to dokładnie jego wysokość, czyli maksymalne h, dla którego c_h \geq 1 (dla wygody nazwijmy je h_{\max}). A więc co najwyżej H. Załóżmy więc, że szerokość aktualnego drzewa przekracza k. Wybierzmy k jego liści, które mają jak największe głębokości d_1 \geq d_2 \geq\ldots\geq d_k.

superkomputer1

Teraz widać, że jeśli h < d_k, to po usunięciu wybranych liści h+\left\lceil \frac{c_{h+1}+c_{h+2}+\ldots}{k} \right\rceil zmniejszy się o dokładnie 1. Aby przeanalizować sytuację dla h \geq d_k należy zauważyć, że skoro użyliśmy jakiegoś liścia na głębokości d_k, to liczby wierzchołków na głębokości d_k+1,d_k+2,\ldots muszą być mniejsze niż k. To oznacza, że \max_{h: d_k \leq h \leq h_{\max}} h+\left\lceil \frac{c_{h+1}+c_{h+2}+\ldots}{k} \right\rceil jest po prostu równe wysokości drzewa. Jest to prawdą zarówno przed jak i po usunięciu liści. Jeśli tylko d_1 > d_k to ta wysokość zmniejsza się o dokładnie 1, więc tak samo spada \max_{h: d_k \leq h \leq h_{\max}} h+\left\lceil \frac{c_{h+1}+c_{h+2}+\ldots}{k} \right\rceil. Jeśli zaś wszystkie d_i są równe i wysokość drzewa nie zmienia się, to c_{d_k} \geq k+1, czyli przed usunięciem liści wartość h+\left\lceil \frac{c_{h+1}+c_{h+2}+\ldots}{k} \right\rceil była ściśle większa dla h=d_k-1 niż dla h=d_k, czyli wartość \max_{h: d_h\geq 1} h+\left\lceil \frac{c_{h+1}+c_{h+2}+\ldots}{k} \right\rceil zawsze spada dokładnie o 1.
Stosując indukcję ze względu na rozmiar drzewa dostajemy, że zawsze wystarczy nam tyle tur.

Załatwia to kwestię policzenia najmniejszej możliwej liczby tur dla ustalonego k. Ale przecież musimy w miarę szybko przetworzyć wiele różnych k! Spróbujmy więc pomyśleć, jak szybko wyliczać \max_{h: c_h \geq 1} h+\left\lceil \frac{c_{h+1}+c_{h+2}+\ldots}{k}\right\rceil. Zacznijmy od prostej obserwacji: równie dobrze można myśleć o wyznaczaniu \max_{h : c_h \geq 1} h\cdot k+c_{h+1}+c_{h+2}+\ldots. Teraz zdefiniujmy sobie f_h(x)=h\cdot x+c_{h+1}+c_{h+2}+\ldots. Każda f_h(x) jest funkcją liniową, chcemy więc szybko wyznaczać maksimum funkcji liniowych w kolejnych x=1,2,3,\ldots,n. Brzmi znajomo?

superkomputer2

Interesuje nas skonstruowanie górnej otoczki podanego zbioru funkcji liniowych. Mając taką górną otoczkę, dla każdego x znamy funkcję, która maksymalizuje f_h(x). O samym wyznaczaniu górnej otoczki już chyba myśleliśmy: trzeba posortować funkcje według współczynników a i dokładać je utrzymując górną otoczkę już rozpatrzonego prefiksu. W tym konkretnym przypadku jest trochę prościej, bo współczynniki a są liczbami z zakresu [1,n], więc w zasadzie nie trzeba ich sortować. Co jest o tyle fajne, że daje złożoność \mathcal{O}(n).

Pewnie można to jakoś trochę uprościć, ale ja lubię maksymalizować funkcje liniowe 🙂

Reklamy

4 myśli nt. „Superkomputer

  1. No, fajnie, że nie tylko ja tu zauważyłem kryjącą się geometrię :D. Robiłem tak samo z dokładnością do tego, że nie chciało mi się konkretniej dowodzić lematu 2. powołując się na swoją matematyczno-informatyczną intuicję :D. Ale no w zasadzie wiedziałem, że to pewnie wyniknie z zastosowania zachłana. Całe rozwiązanie wydało mi się bardzo naturalne, a niestety panuje dość powszechna opinia, że rozwiązanie tego zadania jest całkowicie z … kapelusza. Może to dlatego, że niektórzy nie zauważyli, że patrzenie na ten cały proces od tyłu jest w zasadzie kluczowe do jakiegoś zrozumienia zadania.

      • Można obejść całkowicie geometrię. Wystarczy zauważyć, że nieistotny jest wygląd drzewa. Ważne jest to, ile wierzchołków jest na poszczególnych głębokościach (w poszczególnych odległościach od korzenia). Tworzy się tablicę zawierającą te informacje. Graf jest dawany w taki sposób, że jest to łatwe. Potem dla konkretnego k jest dość łatwo policzyć ile zajmie wykonanie wszystkich instrukcji. Tworzy się „worek” (w tym przypadku to zwykły unsigned, inicjalizowany zerem) i iteruje się od korzenia. Zgodnie ze spostrzeżeniem z powyższego tekstu, zawsze idzie się w dół. Zatem jeśli na pewnej głębokości jest ponad k wierzchołków, nieprzerobione są wrzucane do worka. Natomiast jeśli jest ich mniej a worek nie jest pusty, wykonywane są wszystkie procesy na danej głębokości i tyle, ile się da z worka. Po dojściu do liści wykonuje się już wszystkie procesy z worka w czasie O(1). Zatem takie sprawdzenie wykonywane jest w czasie O(h). Oczywiście korzystać trzeba ze spostrzeżenia, że dla k większego od największej szerokości drzewa, odpowiedź można udzielić natychmiast. Warto też zapisywać wyniki, aby w przypadku dwóch takich samych pytań można było odpowiadać w czasie stałym. Rozwiązanie ma małą złożoność przez to, że albo drzewo jest wysokie, ale nie szerokie (więc na mało pytań nie można odpowiedzieć w czasie stałym), albo jest szerokie, ale nie wysokie (więc liczenie odpowiedzi jest bardzo szybkie). Rozwiązanie to uzyskiwało maksymalną liczbę punktów i posiadało duży zapas czasowy.

        Rozwiązanie wzorcowe traktowało problem, jako zagadnienie programowania dynamicznego i korzystając z podobnych spostrzeżeń rozwiązywało go metodą… chyba zstępującą, ale nie dam sobie za to ręki uciąć. Potem oczywiście odpowiadać na pytania można było w czasie stałym.

      • Nie jestem pewien czy rozumiem 🙂 Co dokładnie rozumiesz przez szerokość drzewa? Maksymalną liczbę wierzchołków o takiej samej głębokości? Jeśli tak, to przecież można skonstruowac drzewo o szerokości n/2 i wysokości (czyli maksymalnej głębokości) n/2…

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