Omówienie zadania Gra w kolorowanie (II etap XXX OI)

Podzadanie \(n \le 10\)

Przy małych ograniczeniach na dane wejściowe jesteśmy w stanie dokładnie przeanalizować wszystkie możliwe rozgrywki. Wystarczy dla każdej możliwej sytuacji sprawdzić, czy dany gracz może przejść do sytuacji, w której przeciwnik nie ma strategii wygrywającej (analizując tę sytuację analogicznie). Rozpoczynając od każdej końcowej pozycji, możemy rozstrzygać kolejne stany, a na koniec sprawdzić dla każdej pary a i b, kto wygra.

Przebieg rozgrywki

W celu przyspieszenia naszego rozwiązania należy dokładniej zrozumieć przebieg optymalnej rozgrywki. Spróbujmy dla danego a należącego do A i b należącego do B przeanalizować, jak będzie wyglądać rozgrywka, gdy wierzchołek a zostanie pokolorowany na czerwono, a wierzchołek b na niebiesko.

Zauważmy, że każdemu graczowi będzie opłacało się zająć taki wierzchołek, który "przybliży" go do drugiego gracza, tym samym "zabierając" mu wierzchołki, które on by mógł zająć. W ten sposób będzie w stanie zarezerwować dla siebie największą część drzewa. Zatem optymalną strategią dla danych wierzchołków startowych jest kolorowanie kolejnych wierzchołków na najkrótszej ścieżce między nimi.

Podzadanie \(n \le 200\)

Zauważmy, że w ten sposób jesteśmy w stanie w liniowym czasie zasymulować rozgrywkę dla każdego a i b. Wystarczy, że zliczymy, jak dużą część drzewa uda się zarezerwować dla siebie pierwszemu graczowi. Jeżeli będzie to ponad połowa drzewa, to wygrywa, a w przeciwnym przypadku przegrywa.

Podzadanie \(n \le 2000\)

Spróbujemy przyspieszyć symulację rozgrywki dla danego a i b. Największym problemem jest tutaj znajdowanie środkowego wierzchołka na ścieżce między a i b.

Skorzystajmy więc z algorytmu na szybkie wyznaczanie najgłębszego wspólnego przodka dwóch wierzchołków, który pozwoli nam ten proces przyspieszyć. Jesteśmy w stanie na początku działania naszego programu wyliczyć wartości tablicy dp[i][j], która będzie oznaczała, jaki jest 2^j-ty przodek wierzchołka i. Taka tablica pozwala nam w czasie logarytmicznym wyznaczyć najgłębszego wspólnego przodka dwóch wierzchołków oraz k-tego przodka danego wierzchołka.

Zauważmy, że w ten sposób w logarytmicznym czasie jesteśmy w stanie znaleźć najwyższy punkt na ścieżce między a i b, a dzięki temu także długość tej ścieżki, powiedzmy, że jest ona równa l. W ten sposób jesteśmy również w stanie szybko znaleźć środkowy wierzchołek. Wystarczy znaleźć wierzchołek, który jest przodkiem stopnia l/2 niższego z wierzchołków startowych (odpowiednio rozpatrując parzysty i nieparzysty przypadek).

Zauważmy, że jednemu z graczy ostatecznie do pokolorowania przypadnie całe poddrzewo tego wierzchołka, a drugi gracz będzie miał do dyspozycji resztę grafu. W ten sposób możemy łatwo policzyć, ile wierzchołków uda się zająć każdemu graczowi i sprawdzić, czy dla pierwszego gracza ta liczba będzie większa.

Pełne rozwiązanie

Ciężko jest dalej poprawiać nasz algorytm, spróbujmy więc nieco inaczej podejść do tego zadania. Zauważmy, że gracz, który "zarezerwuje" sobie ponad połowę grafu, zawsze wygrywa. Może to sugerować, że do analizy, kto wygra, kluczowe jest, komu uda się zająć centroid w drzewie (centroid to wierzchołek, którego każde poddrzewo ma co najwyżej n/2 wierzchołków).

Faktem jest, że w drzewie występuje zawsze dokładnie jeden albo dokładnie dwa centroidy. Spróbujmy więc oddzielnie rozważyć te przypadki.

Przypadek 1 – Jest dokładnie jeden centroid

Oznacza to, że wszystkie poddrzewa powstałe po ukorzenieniu drzewa w centroidzie będą rozmiaru ściśle mniejszego niż n/2. Zauważmy, że gdy jednemu z graczy uda się zająć centroid, to drugi z graczy będzie mógł zajmować jedynie wierzchołki w jednym z jego poddrzew. Takich wierzchołków jest mniej niż połowa, więc gracz ten na pewno pierwszy nie będzie mógł zagrać ruchu, czyli przegra.

Podsumowując, wygra gracz, któremu uda się zająć centroid drzewa przed drugim graczem, czyli ten gracz, którego wierzchołek startowy jest bliżej centroida, a w przypadku remisu gracz pierwszy.

Przypadek 2 – Dwa centroidy

Jeśli obaj gracze mają bliżej do tego samego z dwóch centroidów, sytuacja jest analogiczna do przypadku 1. W przeciwnym razie gracze mają bliżej do różnych centroidów. Zauważmy, że jeśli te odległości są różne, to i tak wygra gracz, który ma bliżej (zajmie oba centroidy). Natomiast jeśli odległości są takie same, to wygra gracz drugi. Obaj gracze będą mieli do dyspozycji n/2 wierzchołków, ale ponieważ gracz pierwszy zaczyna, to jemu najpierw zabraknie ruchu.

Implementacja

Spróbujmy skorzystać z tych spostrzeżeń w celu szybszego rozwiązania tego zadania. Zauważmy, że teraz aby obliczyć wynik, wystarczy dla każdego a ∈ A znaleźć, ile jest takich b ∈ B, których odległość od najbliższego centroida jest mniejsza niż ta odległość dla a, oraz ilość takich b, które mają bliżej do tego samego centroida i ich odległość jest równa odległości a. Wystarczy, że obliczymy sumę tych liczb i otrzymamy wynik.

W celu przyspieszenia tych obliczeń można skorzystać ze struktury drzewa przedziałowego obsługującego operację dodania w punkcie i sumy z przedziału, na którym będziemy utrzymywać dla zbiorów A i B ilość wierzchołków o danej odległości od danego centroida (jeśli jest on tym bliższym). Warto również na początku działania naszego programu obliczyć dla każdego wierzchołka, do którego centroida ma bliżej i jaka jest ta odległość.

Jesteśmy teraz w stanie dość szybko obliczyć wynik dla danych zbiorów A i B. Spróbujmy szybko zaktualizować ten wynik po dodaniu jakiegoś wierzchołka. Zauważmy, że dodając a do A, wystarczy do wyniku dodać wynik dla samego a, który jesteśmy w stanie wyliczyć za pomocą naszego drzewa przedziałowego w czasie logarytmicznym, a następnie zaktualizować nasze drzewa przedziałowe. Usuwanie ze zbioru obsługujemy bardzo podobnie, ale od naszego obecnego wyniku odejmujemy. Operacje na zbiorze B będziemy obsługiwać w analogiczny sposób.