Omówienie zadania Głosowanie (III etap XXIX OI)

Jeżeli zadanie sformułujemy w języku teorii grafów, to mamy w nim do czynienia z ukorzenionym drzewem, w którym każdy wierzchołek, który nie jest liściem, ma nieparzystą liczbę synów. Na takim drzewie odbywa się gra między dwoma graczami. Każdy z nich w swoim ruchu zaznacza jeden liść na swój kolor, aż do momentu, kiedy wszystkie liście zostaną zaznaczone. Po zakończeniu gry każdy wierzchołek wewnętrzny kolorujemy na taki kolor, którego jest więcej w jego synach. Wygrywa ten z graczy, którego kolor znajdzie się w korzeniu. Naszym zadaniem jest napisanie programu, który będzie grał jako gracz zaczynający przeciwko bibliotece symulującej ruchy przeciwnika.

Analiza zadania

W treści zadania jest napisane, że drzewo wejściowe będzie dobrane tak, żeby gracz zaczynający miał strategię wygrywającą. Okazuje się, że to założenie jest spełnione dla każdego drzewa.

Powiemy że wierzchołek jest kontrolowany, jeśli jest zaznaczonym liściem lub wierzchołkiem wewnętrznym, dla którego można obliczyć głos (tzn. któryś z graczy ma przewagę w jego kontrolowanych dzieciach). Pozostałe wierzchołki są puste.

Po każdym naszym ruchu będziemy utrzymywać niezmiennik:

• kontrolujemy korzeń,

• jeśli wierzchołek jest kontrolowany, to kontrolowana jest cała ścieżka z niego do korzenia (z tego wynika, że jeśli wierzchołek jest pusty, to puste jest całe jego poddrzewo),

• w kontrolowanym wierzchołku wewnętrznym przewaga w dzieciach wynosi dokładnie 1 (niezależnie od tego, kto go kontroluje).

Na początek zaznaczamy dowolny liść, co daje nam kontrolę nad ścieżką z niego do korzenia. Niezmiennik jest spełniony.

Po ruchu przeciwnika wybierającego liść, będzie on kontrolował wszystkie wierzchołki na ścieżce w górę od tego liścia do pierwszego wierzchołka \(x\), który jest już kontrolowany (musi taki być, bo korzeń jest kontrolowany). Jeśli \(x\) był kontrolowany przez nas, to właśnie straciliśmy przewagę (bo wynosiła dokładnie 1), co znaczy że zaznaczonych dzieci jest parzysta liczba i możemy wybrać jakieś puste dziecko wierzchołka \(x\). Zaznaczamy dowolny liść w poddrzewie tego dziecka (jest ono całe puste, więc wystarczy iść dowolną ścieżką w dół, zaznaczając na niej wierzchołki, które teraz my kontrolujemy). To przywraca naszą przewagę.

Jeśli \(x\) był kontrolowany przez przeciwnika, to ma on teraz przewagę 2, więc w celu przywrócenia przewagi 1 również zaznaczamy dowolny liść w drzewie pustego dziecka wierzchołka \(x\).

W obu przypadkach nasz kontrruch spowodował, że status wierzchołka \(x\) i wierzchołków powyżej się nie zmienił. W szczególności nadal kontrolujemy korzeń.

Implementacja

Na ruch przeciwnika zawsze reagujemy tak samo. W każdym wierzchołku wystarczy tylko pamiętać, czy jest on kontrolowany (nawet nie trzeba pamiętać przez kogo) oraz trzymać jeden wskaźnik idący po dzieciach w prawo (używany do wyboru kolejnego pustego dziecka).

W drzewie idziemy tylko po wierzchołkach pustych i zawsze je zmieniamy na kontrolowane, zatem sumarycznie dostajemy rozwiązanie o złożoności \(O(n)\).