Omówienie zadania Wakacje Bajtazara (II etap XXVII OI)

Dwukolorowanie drzewa

Zauważmy, że drzewo możemy pokolorować na dwa kolory tak, że jeśli istnieje połączenie między dwoma wierzchołkami, to są one różnych kolorów. Wtedy za każdym razem, gdy przechodzimy do nowego wierzchołka, będzie on koloru innego niż nasz obecny wierzchołek.

W takim przypadku możemy założyć, że Bajtazar będzie zwiedzał wyłącznie wierzchołki jednego koloru (niekoniecznie wszystkie), a pisał w wierzchołkach drugiego koloru. Możemy rozważyć wynik dla obu możliwych kolorowań i wybrać ten lepszy, w ten sposób sprawdzając wszystkie możliwości.

Optymalna trasa Bajtazara

Załóżmy, że Bajtazar znajduje się w jakimś wierzchołku, w którym pisze swój pamiętnik. Zauważmy, że Bajtazar jest w stanie odwiedzić wszystkie sąsiadujące z nim wierzchołki i je zwiedzić. Może to zrobić, ponieważ po odwiedzeniu każdego z tych wierzchołków może wrócić do tego poprzedniego, w którym pisał.

Oczywiście zawsze opłaca się Bajtazarowi to zrobić (w innym przypadku niezwiedzony pozostałby wierzchołek, który moglibyśmy bezkosztownie zwiedzić). Analizując dokładniej, możemy dojść do wniosku, że kolejność zwiedzania tych wierzchołków zależy tylko i wyłącznie od nas (oprócz wierzchołka, z którego Bajtazar potencjalnie tu trafił). Oznacza to, że dowolnie możemy wybrać, który z tych wierzchołków zwiedzi jako ostatni.

Po zwiedzeniu tego ostatniego oczywiście nie opłaca się Bajtazarowi już wracać (oznaczałoby to koniec jego podróży), a lepiej przejść do nowej części grafu i powtórzyć poprzedni krok.

W takim przypadku cała trasa Bajtazara będzie miała "poszerzone" ścieżki na naszym drzewie, a dokładniej będzie to jakaś ścieżka z dodatkiem wszystkich wierzchołków, które Bajtazar może zwiedzić oraz z nią sąsiadujących.

Rozwiązanie wolne

Takie spostrzeżenia sugerują rozwiązanie polegające na sprawdzeniu każdej ścieżki w grafie i sprawdzeniu dla niej wyniku. Można to zrobić na przykład przy użyciu algorytmu DFS. Takie rozwiązanie jest jednak za wolne i nie uzyska dużych punktów.

Rozwiązanie dla \(n \le 1000\)

Obliczenie wyniku

Spróbujmy nieco przyspieszyć nasz algorytm. Możemy zauważyć, że dla każdej ścieżki, znając jej wynik, jesteśmy w stanie łatwo znaleźć wynik dla ścieżki, która powstałaby poprzez przedłużenie jej o nowy wierzchołek. Możemy w tym celu posłużyć się programowaniem dynamicznym.

Ukorzeńmy drzewo w jakimś wybranym wierzchołku. W takim przypadku możemy ustalić, że wynikiem dla danego wierzchołka jest wynik dla najlepszej ścieżki, która się w nim zaczyna i cała mieści w jego poddrzewie. Ostatecznym wynikiem jest wtedy wynik dla korzenia.

Jesteśmy wtedy w stanie łatwo obliczyć wynik dla każdego wierzchołka, znając wyniki dla jego synów. Wtedy wynikiem dla wierzchołka, w którym Bajtazar pisze, jest suma współczynników atrakcyjności wszystkich synów tego wierzchołka (zauważyliśmy już, że możemy je wszystkie zwiedzić) i wyniku z najlepszego z nich (po odjęciu jego współczynnika atrakcyjności, żeby nie zliczyć tej wartości dwukrotnie).

Natomiast jeśli jest to wierzchołek, który Bajtazar zwiedza, wynikiem jest suma współczynnika atrakcyjności tego wierzchołka oraz najlepszego wyniku spośród wyników jego synów.

Odtworzenie ścieżki

Abyśmy byli w stanie odtworzyć ścieżkę Bajtazara, musimy dodatkowo w każdym wierzchołku zapamiętać, do którego z jego synów najbardziej opłacało się przejść (czyli w jaki sposób udało się w nim uzyskać jego wynik). Po takiej modyfikacji dość łatwo jesteśmy w stanie od tyłu odtworzyć najoptymalniejszą trasę (pamiętając o "odskokach").

Oczywiście, aby mieć pewność, że udało się nam znaleźć najlepszy wynik, musimy rozważyć nasze drzewo po ukorzenieniu go w każdym wierzchołku, co powoduje, że takie rozwiązanie nie jest jeszcze wystarczająco szybkie.

Pełne rozwiązanie

Po przeanalizowaniu powyższego algorytmu można dojść do wniosku, że największą jego wadą jest konieczność przekorzeniania drzewa. Marnujemy na to większość czasu. Spróbujmy więc rozwiązać to zadanie, ukorzeniając drzewo w tylko jednym wierzchołku.

Należy wtedy przeanalizować, kiedy dokładnie nasze dotychczasowe rozwiązanie nie działa. Dojdziemy wtedy do wniosku, że w ten sposób nie rozważamy przypadku, gdy optymalna ścieżka "zagina" się w jakimś wierzchołku. Spróbujmy więc dla każdego wierzchołka obliczyć dodatkowo wynik, zakładając, że to w nim ścieżka się "zagina".

Jeśli Bajtazar zwiedza ten wierzchołek, wynikiem jest suma współczynnika jego atrakcyjności oraz dwóch najlepszych wyników spośród wyników jego synów (z jednego z nich Bajtazar przyjdzie, a drugim wyjdzie).

Jeśli jest to wierzchołek, w którym Bajtazar pisze, wynikiem będzie suma współczynników atrakcyjności wszystkich jego synów oraz dwóch najlepszych spośród ich wyników (pamiętając o odjęciu ich współczynnika atrakcyjności).

Ostatecznym wynikiem jest wtedy najlepszy spośród wszystkich potencjalnych obliczonych przez nas wyników.

Odtwarzanie ścieżki

W tym przypadku odtwarzać ścieżkę możemy w bardzo podobny sposób. Jedyną modyfikacją, jaką musimy zrobić, jest utrzymywanie dla każdego wierzchołka dwóch najbardziej opłacalnych synów zamiast jednego.