Omówienie zadania Dostawca pizzy (III etap XXIV OI)

Sieć dróg w Bajtogrodzie tworzy drzewo, które będziemy oznaczać przez \(T\). Drzewo \(T\) ma \(n\) wierzchołków \(\{1, \ldots, n\}\). Wygodnie będzie przyjąć nam, że \(T\) jest ukorzenione w wierzchołku 1, który reprezentuje skrzyżowanie, przy którym znajduje się pizzeria Bajtazara. Każda krawędź \(T\) ma dodatnią wagę oznaczającą czas potrzebny Bajtazarowi na przejechanie pomiędzy wierzchołkami (skrzyżowaniami) połączonymi przez tę krawędź.

Oznaczmy przez \(d(T)\) łączną wagę krawędzi drzewa \(T\). Gdyby Bajtazar w ogóle nie wyłączał podgrzewacza, podgrzewacz pracowałby co najmniej \(2d(T)\) minut. Bajtazar musi bowiem dostać się do każdego poddrzewa \(T\) i z niego wrócić. Łatwo przekonać się, że istnieje trasa Bajtazara, która zajmuje łącznie dokładnie \(2d(T)\) minut.

Uzasadnienie: każdą krawędź \(T\) możemy zamienić na dwie krawędzie skierowane: jedną w górę i jedną w dół drzewa. Dostajemy graf skierowany i silnie spójny, w którym dla każdego wierzchołka liczba krawędzi wchodzących jest równa liczbie krawędzi wychodzących. A zatem w grafie tym możemy znaleźć cykl Eulera.

Zastanówmy się teraz, ile może zaoszczędzić Bajtazar na wyłączaniu podgrzewacza. Jeśli Bajtazar wykonuje tylko jeden kurs, to po dostarczeniu ostatniej pizzy wraca prosto do wierzchołka 1 po pewnej ścieżce \(P_1\). Jak się okazuje, Bajtazar może tak zaplanować trasę, by oszczędzić dokładnie \(d(P_1)\) minut pracy podgrzewacza, gdzie \(d(P_1)\) oznacza długość ścieżki \(P_1\). Niezależnie od wyboru \(P_1\) istnieje bowiem taka trasa długości \(2d(T)\), która obchodzi całe drzewo i kończy się właśnie ścieżką \(P_1\). Można się o tym prosto przekonać, patrząc na odpowiednio narysowane drzewo \(T\). W celu zilustrowania tego faktu rozważmy graf skierowany odpowiadający drzewu z testu przykładowego i niech \(P_1\) będzie ścieżką \(3 \leadsto 1\). Na poniższym rysunku łatwo znaleźć trasę, która prowadzi od wierzchołka \(1\) do wierzchołka \(3\) i po każdej krawędzi grafu przechodzi dokładnie raz.

W tym momencie powinno być jasne, jak rozwiązać zadanie, gdy Bajtazar ma wykonać tylko jeden kurs: wystarczy wybrać jak najdłuższą ścieżkę \(P_1\), po której Bajtazar będzie wracać do pizzerii z wyłączonym podgrzewaczem. Taka ścieżka oczywiście łączy pewien liść drzewa \(T\) z korzeniem.

Sytuacja komplikuje się nieco, gdy Bajtazar wykonuje \(k\) kursów. Niech \(P_i\) oznacza ścieżkę, po której Bajtazar wraca z wyłączonym podgrzewaczem na końcu \(i\)-tego kursu. Rozważmy jedną krawędź \(e\) drzewa \(T\). Możemy tak zaplanować trasę Bajtazara, by przejechał z włączonym podgrzewaczem po krawędzi \(e\):

dwa razy (w górę i w dół drzewa \(T\)), jeśli \(e\) nie należy do żadnej ze ścieżek \(P_1, \ldots, P_k\);
\(l\) razy (za każdym razem w dół drzewa), jeśli \(e\) należy do \(l\) spośród ścieżek \(P_1, \ldots, P_k\).

Podana powyżej liczba kursów jest z całą pewnością konieczna. Aby wykazać, że jest również wystarczająca, zacznijmy od planu rozwożenia pizz, w którym w \(i\)-tym kursie Bajtazar jedzie wprost do początku ścieżki \(P_i\), a następnie wraca po ścieżce \(P_i\) do pizzerii. W ten sposób Bajtazar odwiedzi wszystkie skrzyżowania leżące na ścieżkach \(P_1, \ldots, P_k\). Kursy Bajtazara musimy teraz rozszerzyć o poddrzewa, w których nie ma krawędzi ze ścieżek \(P_1, \ldots, P_k\). Do każdego poddrzewa Bajtazar może wjechać, gdy jedzie z włączonym podgrzewaczem, a następnie objechać je tak, by każdą z krawędzi przejechać dwa razy.

A zatem optymalny koszt rozwiązania, w którym Bajtazar wykonuje \(k\) kursów i wraca po ścieżkach \(P_1, \ldots, P_k\), to \[2d(T) - 2d(T_P) + \sum_{i=1}^k d(P_i),\] gdzie \(T_P\) to suma ścieżek \(P_1, \ldots, P_k\), czyli poddrzewo drzewa \(T\) składające się z krawędzi wchodzących w skład ścieżek \(P_1, \ldots, P_k\).

Przykładowo na poniższym rysunku przedstawiono drzewo z przykładu wraz z optymalnym rozwiązaniem zawierającym \(k=3\) ścieżki:

Mamy: \(d(P_1)=16\), \(d(P_2)=11\), \(d(P_3)=1\), \(d(T_P)=23\) i \(d(T)=26\). Tak więc koszt rozwiązania to \(2\cdot(26-23)+16+11+1=34\).

Zauważmy, że zysk z wykonania wielu kursów i wyłączenia podgrzewacza to \[2d(T_P) - \sum_{i=1}^k d(P_i).\] Przy okazji podaliśmy przepis na budowę optymalnego rozwiązania, jeśli dane mamy jedynie ścieżki, po których Bajtazar wraca do pizzerii — tym samym zadanie sprowadziliśmy do znalezienia odpowiedniego zbioru ścieżek. W celu uproszczenia będziemy dalej mówić, że rozwiązaniem zadania jest po prostu pewien zbiór ścieżek w drzewie \(T\). Odtąd rozwiązywać będziemy problem maksymalizacyjny, gdyż szukamy zbioru ścieżek o maksymalnej wadze, tj. maksymalizującego zdefiniowany powyżej zysk.

Algorytm

Czas zastanowić się, jak skonstruować optymalne rozwiązanie. Rozważmy rozwiązanie składające się ze ścieżek \(P_1, \ldots, P_j\), których suma to \(T_P\). Przy dołożeniu do tego rozwiązania nowej ścieżki \(P'\):

zyskujemy wagę każdej krawędzi \(P'\), która nie należy do \(T_P\);
tracimy wagę każdej krawędzi \(P'\), która należy do \(T_P\).

Łączny zysk (tj. zysk minus strata) z dodania ścieżki \(P'\) nazwiemy wagą ścieżki \(P'\) względem istniejącego rozwiązania \(P_1,\ldots,P_j\). W naszym rozwiązaniu zaczynamy od pustego zbioru ścieżek, a następnie dokładamy do niego kolejno nowe ścieżki. Wagą rozwiązania będzie suma wag kolejno dodawanych ścieżek. Musimy teraz odpowiednio dobrać strategię wyboru kolejnych ścieżek, które będziemy dodawać do rozwiązania.

Dane wejściowe są dość duże, a nasz graf ma prostą konstrukcję (jest drzewem), więc może dobrym pomysłem będzie strategia zachłanna? W przypadku zadania Dostawca pizzy ten pomysł okazuje się strzałem w dziesiątkę. Udowodnimy następujący fakt: jeśli w każdym kroku będziemy dodawać ścieżkę o największej wadze, otrzymamy optymalne rozwiązanie. Ścieżki dodajemy oczywiście tak długo, aż uzyskamy rozwiązanie składające się z \(k\) ścieżek lub dodanie jakiejkolwiek nowej ścieżki przyniesie nam stratę.

Sprawdźmy, jak działa ta strategia dla przykładowych danych wejściowych z treści zadania. W pierwszym kroku wybieramy po prostu najdłuższą ścieżkę o końcu w korzeniu (wierzchołku numer \(1\)). Jest to ścieżka \(3 \leadsto 1\) o wadze 16. W drugim kroku mamy trzy równie dobre wybory. Wybierając ścieżkę \(5 \leadsto 1\), tracimy 5 minut na krawędzi między 2 a 1, ale zyskujemy 6 minut na krawędzi między 5 a 2, co daje wagę 1. Każda ze ścieżek \(6 \leadsto 1\), \(7 \leadsto 1\) również ma wagę 1. W drugim kroku możemy więc wybrać ścieżkę \(5 \leadsto 1\) a w trzecim ścieżkę \(7 \leadsto 1\). Łączny zysk to \(16 + 1 + 1 = 18\) minut. Teraz wystarczy od sumy podwojonych kosztów krawędzi odjąć 18 by otrzymać ostateczny wynik: \(2\cdot(1 + 1 + 5 + 11 + 2 + 6) - 18 = 2\cdot 26 - 18 = 34\).

Dowód poprawności działa podobnie do wielu dowodów tego typu własności. Spośród rozwiązań optymalnych wybieramy to rozwiązanie \(\mathcal{P}_{OPT}\), które jest najbardziej podobne (według odpowiednio dobranej definicji) do rozwiązania znalezionego przez algorytm zachłanny. Następnie przyjmujemy, że \(\mathcal{P}_{OPT}\) różni się od rozwiązania zachłannego, i przy tym założeniu pokazujemy, jak znaleźć rozwiązanie lepsze od \(\mathcal{P}_{OPT}\). Przeczy to optymalności \(\mathcal{P}_{OPT}\) i tym samym dowodzi, że \(\mathcal{P}_{OPT}\) nie może różnić się od rozwiązania zachłannego. Szczegóły są dosyć techniczne — można je znaleźć w dowodzie poniższego twierdzenia.

Twierdzenie. Strategia zachłanna, która w każdym kroku dodaje do rozwiązania ścieżkę o maksymalnej wadze, znajduje rozwiązanie optymalne.

Dowód. Dla wygody opisu wszystkie rozwiązania będziemy traktować jako zbiory ścieżek. Niech \(\mathcal{P}_Z\) będzie pewnym rozwiązaniem zachłannym składającym się ze ścieżek \(P_1, \ldots, P_l\). Dla dowolnego rozwiązania \(\mathcal{P}\) przez \(m(\mathcal{P})\) oznaczamy maksymalny indeks \(i\), taki że rozwiązanie \(\mathcal{P}\) zawiera ścieżki \(P_1, \ldots, P_i\). Spośród wszystkich rozwiązań o maksymalnej wadze, niech \(\mathcal{P}_{OPT}\) będzie rozwiązaniem, które maksymalizuje \(m(\mathcal{P}_{OPT})\). W dalszej części dowodu zakładamy, że \(\mathcal{P}_{OPT} \neq \mathcal{P}_Z\), czyli że w szczególności \(\mathcal{P}_Z\) nie jest jednym z rozwiązań optymalnych.

Wykluczmy najpierw najprostsze przypadki. Niech \(m(\mathcal{P}_{OPT}) = l\). Wtedy \(\mathcal{P}_Z\) zawiera się w \(\mathcal{P}_{OPT}\) i \(\mathcal{P}_Z\) składa się z mniejszej liczby ścieżek niż \(\mathcal{P}_{OPT}\). Skoro algorytm zachłanny się zatrzymał, dodanie każdej kolejnej ścieżki przynosi nam stratę. Tym bardziej dodanie wielu ścieżek jest nieopłacalne: dla każdej ścieżki w drzewie powiększenie rozwiązania może jedynie obniżyć jej wagę, czyli potencjalny zysk z dodania jej do rozwiązania. Stąd wniosek, że \(\mathcal{P}_{OPT}\) to rozwiązanie gorsze niż \(\mathcal{P}_Z\), czyli dostaliśmy sprzeczność. Dalej możemy więc przyjąć, że \(m(\mathcal{P}_{OPT}) < l\).

Niech \(\mathcal{P}_{OPT}\) składa się jedynie z \(m(\mathcal{P}_{OPT}) < l\) ścieżek \(P_1, \ldots, P_{m(\mathcal{P}_{OPT})}\). Tu od razu dostajemy sprzeczność, bo w tej sytuacji algorytm zachłanny kontynuowałby rozbudowywanie rozwiązania, w każdym kroku poprawiając jego wagę (ewentualnie nie zmieniając jej).

Pozostał nam przypadek, w którym \(m(\mathcal{P}_{OPT}) < l\) i \(\mathcal{P}_{OPT}\) składa się z więcej niż \(m(\mathcal{P}_{OPT})\) ścieżek. A zatem zbiór \(\mathcal{P}_{OPT} \setminus \{P_1, \ldots, P_{m(\mathcal{P}_{OPT})}\}\) jest niepusty. Rozważmy ścieżkę \(P = P_{m(\mathcal{P}_{OPT})+1}\). Została ona dodana w kroku \(m(\mathcal{P}_{OPT})+1\) do rozwiązania zachłannego. Mamy oczywiście \(P \in \mathcal{P}_Z\) i \(P \notin \mathcal{P}_{OPT}\). Niech \(P' \in \mathcal{P}_{OPT}\) będzie taką ścieżką należącą do zbioru \(\mathcal{P}_{OPT} \setminus \{P_1, \ldots, P_{m(\mathcal{P}_{OPT})}\}\), która ma największą część wspólną ze ścieżką \(P\). Wykażemy, że w rozwiązaniu \(\mathcal{P}_{OPT}\) możemy zamienić \(P'\) na \(P\) bez pogorszenia łącznej wagi.

Zauważmy, że kolejność dodawania ścieżek do rozwiązania nie ma znaczenia z punktu widzenia całkowitej wagi rozwiązania, dlatego na potrzeby analizy możemy ją dowolnie zmieniać. Załóżmy zatem, że rozwiązanie \(\mathcal{P}_{OPT}\) powstało przez dodanie kolejno ścieżek \(P_1, \ldots, P_{m(\mathcal{P}_{OPT})}\), następnie \(P'\), a na końcu całej reszty (w dowolnej kolejności). Jeśli w kroku \(m(\mathcal{P}_{OPT})+1\) zamiast \(P'\) do rozwiązania dodalibyśmy \(P\), na pewno nie stracilibyśmy — takiego wyboru dokonała strategia zachłanna, także w tym momencie musi to być najlepszy wybór (lub jeden z wielu najlepszych). Ponieważ \(P'\) ma największą część wspólną z \(P\), zamiana \(P'\) na \(P\) nie może pogorszyć nam zysku z kolejno dodawanych ścieżek. A zatem podmiana \(P'\) na \(P\) w rozwiązaniu \(\mathcal{P}_{OPT}\) nie pogarsza jakości rozwiązania. Tym samym rozwiązanie \(\mathcal{P}_Z\) jest nie gorsze niż \(\mathcal{P}_{OPT}\). Uzyskana sprzeczność kończy dowód. \(\square\)

Implementacja

Czas na omówienie implementacji. W trakcie dodawania kolejnych ścieżek do rozwiązania utrzymujemy drzewo \(T_P\) będące sumą dotychczas dodanych ścieżek. W momencie, gdy pewną krawędź dodajemy do \(T_P\), wagę tej krawędzi w drzewie \(T\) możemy zamienić na liczbę przeciwną. Dzięki temu w każdym kroku wystarczy nam znaleźć w drzewie \(T\) ścieżkę o największej sumie wag krawędzi, która zaczyna się w korzeniu.

Jeśli w każdym kroku ścieżkę będziemy znajdować w czasie \(O(n)\), przeszukując całe drzewo, dostaniemy algorytm działający w czasie \(O(nk)\), bo ścieżkę będziemy dodawać do rozwiązania co najwyżej \(k\) razy. Niestety z ograniczeń na rozmiar danych wejściowych widać wyraźnie, że tego typu podejście nie pozwoli rozwiązać wszystkich podzadań.

Aby znaleźć lepsze rozwiązanie, musimy kolejne ścieżki znajdować sprytniej. Niech \(\text{WGórę}[v]\) oznacza wagę ścieżki łączącej korzeń z wierzchołkiem \(v\) w początkowym drzewie \(T\). Z kolei przez \(\text{WDół}[v]\) oznaczmy maksymalną wagę ścieżki w początkowym drzewie \(T\), która zaczyna się w \(v\) i prowadzi w dół drzewa \(T\). Tablice \(\text{WGórę}\) i \(\text{WDół}\) możemy wypełnić w czasie \(O(n)\) na początku naszego algorytmu. Pomogą one szybko znajdować ścieżki, które warto dodać do rozwiązania.

Powiemy, że wierzchołek \(w\) należy do drzewa \(T_P\), jeśli pewna krawędź incydentna z \(w\) należy do \(T_P\). Każda opłacalna ścieżka ma co najmniej jeden wierzchołek \(w\), który nie należy do \(T_P\), gdyż wszystkie krawędzie \(T_P\) mają w \(T\) ujemną wagę. Jeśli \(w\) jest wierzchołkiem spoza \(T_P\), którego ojciec \(\text{Ojciec}(w)\) należy do \(T_P\), to optymalna ścieżka przechodząca przez \(w\) ma wagę \[\text{NajlepszaŚcieżka}(w) = -\text{WGórę}[\text{Ojciec}(w)] + \text{waga}(w, \text{Ojciec}(w)) + \text{WDół}[w],\] gdzie \(\text{waga}(w, \text{Ojciec}(w))\) to waga krawędzi łączącej wierzchołek \(w\) z jego ojcem. Pierwszy składnik sumy bierzemy ze znakiem minus, bo wszystkie krawędzie na tej ścieżce należą teraz do drzewa \(T_P\).

Co ważne, w powyższym wzorze na \(\text{NajlepszaŚcieżka}(w)\) żaden składnik nie zależy od aktualnej postaci drzewa \(T_P\). Jedyny warunek jest taki, że wartości te mają sens dokładnie dla tych wierzchołków \(w\), które nie należą do \(T_P\) i mają ojca w \(T_P\). Nazwijmy te wierzchołki interesującymi.

Zbiór interesujących wierzchołków można prosto utrzymywać w trakcie działania algorytmu. Drzewo \(T_P\) jedynie rośnie, więc przy dołożeniu każdego wierzchołka do \(T_P\), wszystkich jego synów dodajemy do zbioru wierzchołków interesujących. Z kolei wierzchołek przestaje być interesujący, gdy trafia do drzewa \(T_P\). Te własności wykorzystamy w algorytmie. Dla każdego interesującego wierzchołka, odpowiadającą mu wartość \(\text{NajlepszaŚcieżka}(w)\) wstawimy do struktury danych znajdującej minimum w dynamicznym zbiorze. Kwestię doboru odpowiedniej struktury danych skomentujemy na koniec tej sekcji. W każdym razie dzięki efektywnej strukturze danych będziemy w stanie szybko znajdować najlepsze ścieżki.

Możemy już poskładać wszystkie elementy naszego rozwiązania. Najpierw wypełniamy tablice \(\text{WGórę}\) i \(\text{WDół}\), co zajmuje nam czas \(O(n)\). Przyjmiemy, że na początku tylko korzeń \(r\) drzewa \(T\) jest interesujący i odpowiadająca mu wartość \(\text{NajlepszaŚcieżka}(r)\) jest równa \(\text{WDół}[r]\). Tak więc do naszej struktury danych wstawiamy wartość \(\text{NajlepszaŚcieżka}(r)\).

Od tego momentu wykonujemy \(k\) kroków. W każdym kroku w strukturze danych znajdujemy największy element. Jeśli jego waga jest ujemna, algorytm się kończy. W przeciwnym razie dostajemy wagę ścieżki, którą możemy dołożyć do rozwiązania. Jednocześnie poznajemy interesujący wierzchołek \(w\), przez który przechodzi ta ścieżka. Krawędź łącząca \(w\) z jego ojcem oraz krawędzie ścieżki odpowiadającej wartości \(\text{WDół}[w]\) musimy teraz dodać do drzewa \(T_P\). Obliczając tablicę \(\text{WDół}\), możemy przy okazji zapisać, jaka jest pierwsza krawędź ścieżki realizującej obliczoną długość. To pozwoli nam odzyskać ścieżkę odpowiadającą wartości \(\text{WDół}[w]\) w czasie liniowym od jej długości. Ten czas jest zupełnie zadowalający, bo każdą krawędź z tej ścieżki dodajemy do \(T_P\). Na końcu kroku odpowiednio aktualizujemy zbiór interesujących wierzchołków i naszą strukturę danych.

Łączny czas aktualizacji drzewa \(T_P\) i zbioru interesujących wierzchołków to \(O(n)\). Najwolniejszą częścią naszego rozwiązania jest struktura danych znajdująca minimum.

Struktura danych utrzymująca minimum

Przypomnijmy, że potrzebna nam jest struktura danych, która pozwala na wstawianie i usuwanie wierzchołków drzewa oraz odpowiada na zapytania o minimum z wartości \(\text{NajlepszaŚcieżka}(w)\) dla wierzchołków \(w\) przechowywanych w strukturze. Operacje te kojarzą się z operacjami kolejki priorytetowej. Przykładem efektywnej implementacji kolejki priorytetowej jest kopiec binarny, w którym dodawanie elementu i usuwanie elementu minimalnego są wykonywane w czasie \(O(\log n)\), a zapytanie o minimum wykonuje się w czasie stałym. Niestety kopiec nie pozwala na usuwanie dowolnych elementów, a jedynie elementu minimalnego.

Można ten problem obejść na dwa sposoby. Pierwszy sposób korzysta z tego, że za pomocą standardowych operacji kopca jesteśmy w stanie w czasie \(O(\log n)\) usunąć dany element, jeśli tylko wiemy, gdzie konkretnie się on w tym kopcu znajduje. Aby móc to ustalać, będziemy przechowywać pewne dodatkowe informacje. Po pierwsze dla każdego elementu kopca zapamiętamy, któremu wierzchołkowi drzewa on odpowiada. Po drugie dla każdego wierzchołka drzewa będziemy pamiętali, w pomocniczej tablicy, miejsce w kopcu, gdzie ten wierzchołek jest przechowywany, jeśli znajduje się on w kopcu. Podczas każdej operacji wykonywanej na kopcu musimy te informacje aktualizować. Zapamiętane informacje pozwolą za każdym razem wskazać odpowiedni element kopca, gdy będziemy chcieli usunąć dany wierzchołek. Koszt poszczególnych operacji na strukturze wyniesie więc \(O(\log n)\).

Drugi sposób jest dużo prostszy w implementacji i polega na zastosowaniu metody „leniwej". Jeśli nie umiemy usuwać elementów z kopca, to po prostu tego nie róbmy! Wtedy w kopcu mogą pozostawać elementy, których nie powinno tam już być. Wystarczy jednak w dodatkowej tablicy zapamiętać dla każdego wierzchołka informację, czy powinien on znajdować się w strukturze, czy też nie. Podobnie jak poprzednio, kopiec będzie przechowywał wartości postaci \((\text{NajlepszaŚcieżka}(w), w)\). Gdy będziemy obliczać minimum w kopcu, sprawdzimy, czy odpowiadający mu wierzchołek powinien znajdować się w kopcu, czy też nie. Jeśli nie, to usuniemy go i będziemy tę operację powtarzać tak długo, aż minimum kopca będzie odpowiadać „prawowitemu" wierzchołkowi. Może to spowodować konieczność wykonania wielu usunięć minimum. Łącznie jednak każdy wierzchołek zostanie usunięty z kopca co najwyżej raz, zatem koszt zamortyzowany pojedynczej operacji wyniesie \(O(\log n)\). Dodajmy, że ta metoda może powodować większe zużycie pamięci, ale w tym przypadku i tak kopiec będzie zawsze zawierał co najwyżej \(n\) elementów.

Wreszcie jeśli mamy do dyspozycji kontenery z biblioteki standardowej C++, to drugą metodę możemy zaimplementować za pomocą kontenera priority_queue. W tym przypadku też możemy po prostu posłużyć się kontenerem set lub multiset, który pozwala wykonywać każdą z żądanych operacji w czasie \(O(\log n)\).

Ostatecznie dostajemy rozwiązanie całego zadania działające w czasie \(O(n \log n)\).