Jaskinia

W tym kąciku omówimy zadanie Jaskinia, które pojawiło się w zeszłym roku na Akademickich Mistrzostwach Polski w Programowaniu Zespołowym.

Tytułowa jaskinia składa się z $\text{[math]}$ komnat połączonych $\text{[math]}$ korytarzami, które tworzą drzewo. Grotołazi chcą podzielić się na kilka grup, a następnie chcą przydzielić każdej grupie zbiór komnat, tak by każda komnata została przydzielona dokładnie jednej ekipie grotołazów oraz by każda grupa dostała tyle samo komnat do zbadania i była w stanie poruszać się pomiędzy przydzielonymi komnatami bez przechodzenia przez komnaty innych ekip. Na ile grup mogą podzielić się grotołazi?

Poniższa obserwacja daje warunek konieczny i wystarczający na istnienie podziału:

Lemat. Drzewo o $\text{[math]}$ wierzchołkach można podzielić na spójne kawałki rozmiaru $\text{[math]}$ wtedy i tylko wtedy, gdy w tym drzewie znajduje się dokładnie $\text{[math]}$ krawędzi, które łączą poddrzewa o rozmiarach będących wielokrotnościami $\text{[math]}$

Dowód (prosty). Jeśli podzieliliśmy drzewo na kawałki rozmiaru $\text{[math]}$ zgodnie z warunkami zadania, to tych kawałków jest $\text{[math]}$ Krawędzi, które łączą wierzchołki należące do różnych kawałków, jest dokładnie $\text{[math]}$ a ponieważ poddrzewa połączone takimi krawędziami składają się z całych kawałków, wobec tego rozmiar każdego z tych poddrzew jest podzielny przez $\text{[math]}$ Krawędzie wewnątrz kawałków nie mają tej własności.

W drugą stronę: usuwamy kolejno wszystkie $\text{[math]}$ „dobrych” krawędzi. Po każdym usunięciu dostajemy zbiór niepustych kawałków o rozmiarach podzielnych przez $\text{[math]}$ Na końcu zostanie $\text{[math]}$ kawałków, czyli wszystkie muszą mieć rozmiar $\text{[math]}$

Powyższa obserwacja pozwala nam na stworzenie następującego rozwiązania: ukorzeniamy drzewo w dowolnym wierzchołku i dla każdego $\text{[math]}$ przechodzimy drzewo od liści do korzenia, zliczając „dobre” krawędzie, tzn. takie, które łączą poddrzewa o rozmiarach będących wielokrotnościami $\text{[math]}$ (rozmiary poddrzew obliczamy na bieżąco prostym programowaniem dynamicznym).

Złożoność czasowa tego rozwiązania to $\text{[math]}$ gdzie $\text{[math]}$ oznacza liczbę dzielników $\text{[math]}$ Wśród liczb $\text{[math]}$ możemy znaleźć takie, które mają dość dużo dzielników (rekord to $\text{[math]}$ ), zatem powyższe rozwiązanie jest niezbyt szybkie.

Można to zrobić sprytniej, wykonując tylko jedno przeszukiwanie drzewa. Rozważmy bowiem krawędź, która łączy dwa poddrzewa o rozmiarach $\text{[math]}$ oraz $\text{[math]}$ i zastanówmy się, dla jakich $\text{[math]}$ będzie ona „dobrą” krawędzią. Ano, dla takich $\text{[math]}$ które dzielą zarówno $\text{[math]}$ jak i $\text{[math]}$ zatem dla wszystkich dzielników liczby $\text{[math]}$ Możemy zatem postąpić następująco. W tablicy $\text{[math]}$ będziemy zliczać „dobre” krawędzie. W pierwszym kroku przechodzimy drzewo od liści do korzenia i dla każdej krawędzi zwiększamy licznik $\text{[math]}$ Przejście drzewa wykonujemy w czasie $\text{[math]}$ gdyż dla każdej krawędzi obliczenie największego wspólnego dzielnika możemy wykonać w czasie $\text{[math]}$ korzystając z algorytmu Euklidesa.

Następnie przeglądamy dzielniki $\text{[math]}$ w kolejności rosnącej i dla każdego takiego dzielnika $\text{[math]}$ zwiększamy o wartość $\text{[math]}$ liczniki $\text{[math]}$ dla $\text{[math]}$ Jeśli dla każdego $\text{[math]}$ w poszukiwaniu jego dzielników przejrzymy wszystkie liczby mniejsze od $\text{[math]}$ to ten krok wykonamy w czasie $\text{[math]}$ czyli czasie proporcjonalnym do sumy dzielników $\text{[math]}$ czyli $\text{[math]}$

Odpowiedzią są wszystkie liczby $\text{[math]}$ które spełniają $\text{[math]}$ Złożoność czasowa tego rozwiązania to $\text{[math]}$ Przejście drzewa moglibyśmy zrealizować w czasie liniowym, gdybyśmy znali dla każdego $\text{[math]}$ wartość $\text{[math]}$ Można te wartości obliczyć następującym algorytmem, który przypomina metodę sita Eratostenesa:

display-math

Po wykonaniu powyższego kodu będziemy mieli $\text{[math]}$ dla każdego $\text{[math]}$ Dla każdego $\text{[math]}$ wewnętrzna pętla wykona się $\text{[math]}$ razy, zatem w całym algorytmie wykona się $\text{[math]}$ razy. Ostatecznie daje nam to algorytm o złożoności czasowej $\text{[math]}$