Omówienie zadania Drzewo czwórkowe (II etap XXVII OI)

Streszczenie zadania

Mamy daną planszę o wymiarach \(2^m \times 2^m\) dla dużych \(m\) (nawet \(m \le 10^9\)), w której pola są zamalowane na biało bądź na czarno. Kolorowanie planszy jest podane w formie skompresowanego drzewa czwórkowego. Obszarem nazwiemy maksymalny zbiór sąsiadujących ze sobą pikseli koloru czarnego. Mamy podać:

• ile jest różnych obszarów,
• wielkość największego z nich.

Wczytywanie wejścia

Już sam sposób wczytywania drzewa na wejściu był nieoczywisty. Aby wczytać drzewo, możemy utworzyć funkcję rekurencyjną, która:

1. wczytuje liczbę na obecnym poziomie drzewa;
2. jeśli jest to 0 lub 1, to zapamięta kolor swojego obszaru i powróci do poprzedniego poziomu rekurencji;
3. jeśli jest to 4, wywoła się rekurencyjnie dla każdego z synów tego wierzchołka w drzewie.

Wyznaczanie liczby obszarów &ndash pierwsze podzadanie

Zacznijmy od wygodnej interpretacji zadania. Możemy reprezentować czarne kwadraty pól (które być może są większe, niż jeden pixel) na planszy jako wierzchołki grafu, w którym istnieje krawędź między dwoma wierzchołkami wtedy i tylko wtedy, gdy odpowiadające im kwadraty stykają się. Wyznaczenie liczby obszarów sprowadza się do wyznaczenia liczby spójnych składowych w tym grafie. Będziemy się zastanawiać jak konstruować taki graf.

Zacznijmy od podejścia, który wynika z tej interpretacji:

1. Wyznaczmy współrzędne każdego pixela.
2. Wyznaczmy krawędzie poprzez sprawdzenie jakie pixele się stykają.
3. Wyznaczmy spójne grafu.

W pierwszym podzadaniu, limity na wymiary planszy oraz liczbę czarnych pól są bardzo małe, więc możemy określić dokładne współrzędne każdego czarnego pixela (można stworzyć macierz pixeli), analogicznie do wczytywania wejścia. Takich pixeli będzie \(2^{2m}\) dla \(m\le10\), więc zmieścimy się w limitach czasowych, o ile dalsze kroki tego podejścia zostaną wykonane w czasie liniowym.

Wyznaczanie liczby obszarów – drugie podzadanie

W drugim podzadaniu, gdybyśmy mogli w stałym czasie sprawdzać, czy dwa kwadraty się stykają, to wystarczyłoby sprawdzić każdą parę. Jednak współrzędne znacznie przekraczają zakres zmiennych typu 64-bitowego, więc potrzebujemy bardziej wydajnego rozwiązania.

Jeśli dwa kwadraty się stykają, to jedna ze współrzędnych boków obydwu kwadratów musi być taka sama. Stwórzmy dla każdej współrzędnej listę kwadratów, które mają bok na tej współrzędnej. Wtedy sprawdzenie istnienia krawędzi redukuje się do sprawdzenia, czy przecięcie dwóch przedziałów jest niepuste.

Przykładowa implementacja składa się z następujących kroków:

1. Rozpatrujemy kwadraty w kolejności od najmniejszego do największego.
2. Dla każdego z boków dodajemy krawędzie między tym kwadratem, a wszystkimi kwadratami, których środki leżą w przedziale wyznaczonym przez ten bok, następnie usuwając te kwadraty ze zbioru do rozpatrzenia.
3. Na koniec dodajemy jego środek boku, wraz informacją o indeksie naszego kwadratu.

Taka implementacja nie ma problemu z kwadratami, które stykają się jedynie rogami – między nimi nie chcemy dodawać krawędzi.

Działania na dużych współrzędnych są kolejnym wyzwaniem. Możemy traktować współrzędne boków jako napisy złożone z zer i jedynek, reprezentujące liczbę w systemie binarnym. Porównywanie takich liczb (binarnych napisów) zajmuje \(O(m)\) czasu, więc graf skonstruujemy w czasie \(O(nm \log n)\), używając np. struktury std::set w C++.

Wyznaczanie liczby obszarów – rozwiązanie wzorcowe

Złożoność z poprzedniego podzadania jeszcze nie wystarcza, ale sam pomysł może zostać taki sam. Żeby go usprawnić, trzeba znaleźć sposób na szybkie porównywanie współrzędnych. Przyjrzymy się dokładniej temu sposobowi, dzięki któremu porównywaliśmy dwie liczby w poprzednim podzadaniu. Sprowadzało się to do rozpatrywania kolejnych bitów, zaczynając od najbardziej znaczących bitów. Istnieje pewna struktura danych, która pomaga nam robić to podobnie, lecz efektywniej:

• Wykorzystamy strukturę Drzewa Trie, Stworzymy dwie takie struktury, odpowiednio dla osi poziomej oraz pionowej. Tworzymy je poprzez schodzenie w dół po drzewie czwórkowym i zapamiętując ścieżki na odpowiednich osiach.
• Drzewo trie pozwala nam zachować liczby w odpowiedniej formie przy ograniczonym zużyciu pamięci oraz łatwo przeskalować je do liczb 64-bitowych.
• Wykorzystując drzewo, kompresujemy współrzędne do kolejnych liczb naturalnych. Odzyskujemy skompresowane współrzędne algorytmem DFS w kolejności Pre-Order.

W ten sposób uzyskujemy złożoność \(O(n \log n)\).

Po odzyskaniu skompresowanych współrzędnych, postępujemy jak w drugim podzadaniu, ale otrzymujemy teraz algorytm o złożoności \(O(n \log n)\).

Wyznaczanie największego obszaru

Na koniec wyznaczamy wielkość największego obszaru. Co prawda należy ją wypisać modulo \(10^9+7\), ale do samego porównania która liczba jest większa (aby wyznaczyć największą z nich) potrzeba pełnej reprezentacji, przed zmodulowaniem.

Wielkość jednego obszaru to, z definicji, suma wielkości kwadratów, z których się składa. Każdy taki kwadrat jest potęgą dwójki. Narzuca się więc pomysł, aby trzymać rozmiar w postaci binarnej, po czym wyznaczyć największą taką liczbę, i wypisać ją zmodulowaną. Żeby wyznaczyć taką postać binarną, wykonamy następujące kroki:

1. Tworzymy listę wykładników potęg dwójki sumujących się do wielkości obszaru.
2. Dla każdej grupy tworzymy pomocniczą listę, trzymając przy wykładniku liczbę wystąpień tej potęgi w sumie.
3. Idąc od najmniejszych potęg, jeśli jest więcej niż jedna, zmniejszamy licznik o 2 i dodajemy 1 do licznika potęgi o jeden większej.

Jest to po prostu sprowadzenie sumy potęg dwójki do postaci kanonicznej (każda potęga końcowo wystąpi z krotnością \(0\) lub \(1\)). Ten proces zajmie \(O(n \log n)\) czasu.

Pozostało nam jedynie wyznaczyć największą taką liczbę. Gdy mamy już przygotowane nasze listy, spójrzmy na ich największe wykładniki. Te listy, dla których wartość wykładnika jest równa maksymalnemu spośród wszystkich, są naszymi kandydatami na największe pole. Inne zaś możemy od razu odrzucić. Możemy więc odjąć tę potęgę dwójki od naszych kandydatów, dodać ją do wyniku, a następnie powtórzyć proces na pozostałym zbiorze kandydatów.

Końcowo osiągamy złożoność \(O(n \log n + n \log m)\).