Omówienie zadania Nawigacja samochodowa (III etap XXX OI)

Wstęp

W zadaniu mamy dane \(n\)-wierzchołkowe drzewo oraz zapytania postaci pary wierzchołków \((a, b)\). Na każde zapytanie chcemy odpowiedzieć, jaka jest odległość między parą wierzchołków w naszym drzewie. Zadanie można podzielić na dwie części:

• kodowanie,
• dekodowanie.

W części kodowania otrzymujemy informację o strukturze drzewa i musimy zakodować ją w taki sposób, aby w części dekodowania, bez znajomości struktury drzewa, móc odpowiadać na zapytania. Na kodowanie informacji mamy do dyspozycji \(512\) bitów na wierzchołek.

Najprostsza metoda

Zastanówmy się, jak najprościej zakodować potrzebne informacje. Ponieważ zapytania dotyczą odległości między wierzchołkami, moglibyśmy spróbować zakodować dokładnie tę informację.

Dla każdego wierzchołka zapiszemy odległości do pozostałych wierzchołków. W podzadaniu 1. zachodzi warunek \(n \leq 10\). Ponieważ odległość między parami wierzchołków w drzewie jest ograniczona przez \(n\), to ilość bitów potrzebnych do kodowania odległości w systemie binarnym dla jednego wierzchołka nie przekracza \(\lceil \log_2 n \rceil = 4\). Łącznie zużyjemy więc dla jednego wierzchołka \(4\cdot (n-1) = 36\) bitów na kodowanie informacji.

Szukanie optymalizacji

Aby zdobyć punkty z kolejnych podzadań, moglibyśmy znaleźć sposób na zoptymalizowanie naszej metody. Faktycznie da się to zrobić, zmniejszając o połowę ilość używanych bitów na wierzchołek.

Dla \(i\)-tego wierzchołka możemy zapisać informacje o odległościach do kolejnych \(n/2\) wierzchołków (tj. dla \(i\)-tego wierzchołka zapisujemy odległości do wierzchołków o indeksach \(i \bmod n+1, (i+1) \bmod n+1, \ldots, (i+n/2-1) \bmod n+1\). Dla dowolnych dwóch wierzchołków \(a, b\), jeden z nich będzie zawierał drugiego w swoim kodowaniu. Dzięki temu uzyskaliśmy rozwiązanie 2. podzadania, używając \(7\cdot 50 = 350\) bitów.

Konstrukcja optymalnego rozwiązania

Chcielibyśmy znaleźć metodę kodowania korzystająca z mniej niż \(O(n^2)\) bitów, która umożliwi odzyskiwanie wyników zapytań dla jeszcze większych \(n\).

Przechowywanie wszystkich odległości między wszystkimi wierzchołkami jest zbyt kosztowne, więc moglibyśmy spróbować jakoś wnioskować odległości między parami wierzchołków na podstawie innych odległości. Rzeczywiście, jedno z możliwych takich podejść jest następujące:

• Zauważmy, że wyróżniając jeden wierzchołek w drzewie i obliczając odległości od niego do pozostałych, możemy wyznaczyć odległość między każdą parą wierzchołków znajdujących się w osobnych poddrzewach wyróżnionego wierzchołka.

Pozostaje kwestia odzyskania odległości między wierzchołkami znajdującymi się w tym samym poddrzewie. Możemy wywoływać się rekurencyjnie dla każdego z poddrzew, traktując je jako osobne drzewa i powtarzając proces. Musimy sprytnie wybrać odpowiednie wierzchołki do wyróżnienia, aby uniknąć zapisywania zbyt dużej ilości informacji dla każdego z nich.

Zauważmy, że wyróżniając centroid rozważanego drzewa, dzielimy graf na spójne o rozmiarze nie większym niż połowa pierwotnej spójnej. W rozwiązaniu wzorcowym zastosujemy więc metodę rozbicia przez centroid, która dzięki tej własności ma głębokość rekurencji \(O(\log n)\).

Możemy podczas tego podziału zapisać informację o tych spójnych i ich wyznaczonych centroidach. Jeżeli dla każdego wierzchołka wyznaczymy wszystkie kolejne centroidy spójnych, w których ten wierzchołek należy, to wtedy:

• Żeby znaleźć odległość między dowolną parą wierzchołków \(v, u\), to...
• wystarczy znaleźć odpowiedni centroid zawierający \(v\) w poddrzewie jego spójnej (a takich centroidów jest co najwyżej \(\lceil \log_2 n \rceil\)), dla którego wierzchołki \(v\) oraz \(u\) są w różnych poddrzewach, i wtedy sumujemy ich odległości do tego centroida.

Rozwiązanie wzorcowe

Zapisujemy dla każdego wierzchołka \(v\) następującą informację:

• dla każdego centroida, którego spójna zawiera wierzchołek \(v\), jaki jest ten centroid i jaka jest odległość do wierzchołka \(v\)?

Informacje te możemy zakodować w dokładnie \(2\cdot \lceil \log_2 n \rceil ^2 = 2\cdot 16\cdot 16 = 512\) bitach, osiągając 90 punktów dla \(n \leq 50000\). Zbliżamy się już do zdobycia maksymalnej liczby punktów.

Wykorzystajmy jeszcze pewien fakt opisany na początku omówienia. Mianowicie, odległość między parą wierzchołków w drzewie jest ograniczona przez jego rozmiar. Przy każdym kolejnym rekurencyjnym podziale drzewa, rozmiar rozpatrywanej spójnej maleje dwukrotnie. Możemy zatem używać coraz mniej bitów na zapis odległości. Ostatecznie kończymy z \(O(\frac3 2\cdot \lceil \log_2 n \rceil ^2) \approx \frac3 2\cdot 18\cdot 18 = 486\) bitami, co bez problemu mieści się w limicie \(b=512\) bitów na wierzchołek oraz w limicie czasowym, ponieważ złożoność czasowa naszego algorytmu to \(O(n \log n + b\cdot m)\).