Omówienie zadania Przedszkole (I etap XXVII OI)

Możemy zauważyć, że w tym zadaniu różne podzadania mają istotnie różne ograniczenia. Zatem intuicyjne jest, żeby rozwiązać każde z nich osobno, a w naszym programie połączyć te rozwiązania.

Podzadanie 1 (\(n \le 8, k \le 8, z \le 50\))

Zauważmy, że ograniczenia w tym przypadku są bardzo małe, więc możemy pozwolić sobie na dosyć brutalne podejście. Przeanalizujmy więc wszystkie możliwe kolorowania grafu. Można to zrobić np. rekurencyjnie, kolorując kolejne wierzchołki na każdy możliwy kolor, a następnie sprawdzając, czy nasze kolorowanie jest poprawne przez sprawdzenie każdej pary lubiących się dzieci. Jeśli jest poprawne, dodajemy 1 do wyniku. Warto nieco przyspieszyć nasz algorytm, na bieżąco sprawdzając, czy dana część kolorowania wciąż jest poprawna, a jeśli nie jest, to zrezygnować z dalszej rekurencji i szybciej przejść do kolejnego przypadku.

Podzadanie 2 (\(n \le 15\))

Spróbujmy przyspieszyć nasze rozwiązanie. Zauważmy, że często zdarza się, że podziały są do siebie analogiczne i różnią się jedynie zabawką, którą bawi się dana grupa dzieci (grupy dzieci, które bawią się tą samą zabawką, zostają takie same). Możemy w podobny sposób, rekurencyjnie przejść się po naszym grafie. Tym razem jednak będziemy starali się podzielić dzieci na grupy (nie przydzielając grupie żadnej konkretnej zabawki), w taki sposób, żeby w danej grupie wszystkie dzieci mogły otrzymać tę samą zabawkę (czyli tak, żeby nie było wśród nich pary dzieci, które się lubią). Następnie dla każdego takiego podziału można zliczyć, ile grup do niego użyliśmy. Zliczmy teraz dla każdej liczby \(x \le \min(n, k)\), na ile sposobów można podzielić nasz graf na dokładnie \(x\) grup.

Spróbujmy teraz policzyć, ile jest możliwych kolorowań dla danego \(k\) oraz podziału grafu na \(l\) grup. Zauważmy, że pierwszą grupę możemy pokolorować na \(k\) różnych kolorów, drugą na \(k-1\), trzecią na \(k-2\), ... aż \(l\)-tą grupę na \(k - l + 1\). Wynik dla takiego podziału jest równy iloczynowi liczb od \(k - l + 1\) do \(k\) (\(k\) nie może być mniejsze niż \(l\)).

Zatem dla każdego \(k\) możemy przejść się po naszej liście ilości różnych podziałów na \(l\) grup i do wyniku dodać nasz iloczyn pomnożony przez ilość takich podziałów na grupy.

Podzadanie 3 (\(m \le 24))

Zauważmy, że w tym przypadku większość wierzchołków nie będzie połączona z żadnym wierzchołkiem, a w ten sposób nie będą one miały żadnego wpływu na wynik dla reszty grafu. Wystarczy jedynie na sam koniec przemnożyć wynik przez \(k\) podniesione do potęgi liczby takich wierzchołków. Spróbujmy teraz obliczyć wynik dla reszty grafu, która składa się co najwyżej z \(2m\) wierzchołków. Niech \(n\) oznacza liczbę tych wierzchołków. Wtedy możemy policzyć ilość złych kolorowań, a aby otrzymać ilość dobrych, wystarczy od \(k^n\) tę liczbę odjąć.

Złe kolorowania to takie, gdzie na końcach jakiejś krawędzi wierzchołki są tego samego koloru. W celu obliczenia liczby takich kolorowań możemy skorzystać z zasady włączeń-wyłączeń. Wystarczy dla każdego podzbioru krawędzi sprawdzić, ile spójnych one utworzą. Zakładamy, że każda spójna jest pokolorowana na jeden kolor. Wtedy taki podzbiór możemy pokolorować na \(k^l\) sposobów, gdzie \(l\) oznacza ilość spójnych. Jeżeli rozważamy nieparzystą liczbę krawędzi, tę wartość dodajemy, a w przeciwnym wypadku odejmujemy.

Spróbujmy teraz przyspieszyć to rozwiązanie dla większej liczby różnych wartości \(k\). Możemy zauważyć, że po każdym zapytaniu sprawdzamy dla każdego podzbioru połączeń, ile spójnych one tworzą. Ta liczba oczywiście za każdym razem jest taka sama, zatem optymalniej będzie na początku dla każdej ilości spójnych policzyć, na ile sposobów jesteśmy w stanie uzyskać taki podział, a po każdym zapytaniu przejść się po zapamiętanych wynikach odpowiednio zmieniając wynik. Takie rozwiązanie działa wystarczająco szybko, aby uzyskać punkty za to podzadanie.

Podzadanie 4 (każdy wierzchołek ma dwóch sąsiadów)

Po rozrysowaniu kilku przypadków możemy zauważyć, że takie ograniczenia powodują, że nasz graf wygląda bardzo specyficznie, a mianowicie składa się jedynie z cykli, których długości są nie mniejsze niż 3. Skoro cykle te nie są w żaden sposób połączone, możemy zauważyć, że wynik dla grafu jest iloczynem wyników z wszystkich cykli. Zatem spróbujmy uprościć sobie problem i najpierw rozwiązać to zadanie dla jednego cyklu.

Możemy zauważyć, że zakładając, że część cyklu jest już pokolorowana, kolejny wierzchołek możemy pokolorować na \((k-1)\) sposobów, co sugerowałoby wzór \((k-1)^n\). Jednak łatwo zauważyć, że nie zawsze daje on prawidłowy wynik. Najlepszym pomysłem w takiej sytuacji jest samemu obliczyć wynik dla różnych długości cyklów i porównać go z tym dawanym przez nasz wzór. W taki sposób możemy zauważyć, że dobry wynik różni się o dokładnie \(k-1\) od \((k-1)^n\), z różnym znakiem w zależności od parzystości \(n\), a dokładny wzór to \((k-1)^n + (k-1)\cdot (-1)^n\).

W ten sposób potrafimy już znaleźć wynik dla danego cyklu. Aby nasze rozwiązanie działało szybko, warto zliczyć sobie długości cykli na początku działania naszego programu, a następnie po każdym zapytaniu obliczać wynik dla każdej długości cyklu, jaki występuje. Zauważmy, że wciąż sporo czasu tracimy na potęgowanie liczb. W tym celu możemy skorzystać z szybkiego potęgowania, które korzysta z własności \(x^k = (x^2)^{\lfloor k/2\rfloor }\cdot x^{k\bmod 2}\). Po zastosowaniu tych przyspieszeń nasz program powinien uzyskać maksymalną liczbę punktów za to podzadanie.

Pełne rozwiązanie

Aby nasze rozwiązanie działało szybko dla każdego grafu możliwego w tym zadaniu, powinniśmy zaimplementować wszystkie te podejścia i po analizie struktury grafu użyć tego optymalnego. W ten sposób jesteśmy w stanie zdobyć 100 punktów za to zadanie.