Omówienie zadania Długie podróże (III etap XXVI OI)

Pierwsze podzadanie

Przy pomocy przeszukiwania grafu wszerz można wyznaczyć odległości z wybranego wierzchołka początkowego do wszystkich pozostałych w czasie \(O(m)\).

Rozwiązanie brutalne może więc uruchomić powyższy algorytm dla każdego zapytania. Działa wówczas w złożoności \(O(mp)\)

Dla podzadania, w którym mamy do odpowiedzenia tylko na jedno zapytanie, jest więc to wystarczające.

Drugie podzadanie

Ograniczenia nałożone na strukturę grafu w drugim podzadaniu oznaczają, że mamy do czynienia ze ścieżką. Do rozwiązania zadania wystarczy więc znaleźć kolejność wierzchołków, a następnie odjąć od siebie pozycje wierzchołków z zapytań.

W tym celu odnajdujemy jeden z końców ścieżki (wierzchołek o stopniu 1), a następnie wyznaczamy jednoznaczną kolejność wierzchołków na tej ścieżce przy pomocy przeszukiwania grafu wzdłuż lub wszerz, dla każdego wierzchołka zapisując, który jest w kolejności przeszukiwania.

Dla zapytania o najkrótszą odległość między wierzchołkami \(s\) i \(t\) obliczymy różnicę pomiędzy ich pozycjami i na zapytanie odpowiemy w czasie stałym.

Złożoność takiego rozwiązania to \(O(n+m+p)\).

Trzecie podzadanie

W trzecim podzadaniu zadany graf jest drzewem.

Problem szybkiego znajdowania odległości pomiędzy dowolną parą wierzchołków w drzewie jest znany i dobrze opisany w literaturze.

Dla wierzchołków \(s\), \(t\) wystarczy znaleźć ich najniższego wspólnego przodka (ang. Lowest Common Ancestor, LCA), a następnie policzyć wartość \(głębokość_s + głębokość_t - głębokość_{lca(s, t)}\).

Opis algorytmu znajdującego LCA można znaleźć w opracowaniu zadania Komiwojażer Bajtazar z IX Olimpiady Informatycznej.

Złożoność to \(O((n + p)\log n)\).

Czwarte podzadanie

Po raz kolejny uproszczeniem jest specyficzna struktura grafu, w przypadku \(m = n\) mamy do czynienia z pierścieniem, do którego mogą być podpięte drzewa. Łatwo się przekonać, że przypadek w którym wierzchołki których dotyczy zapytanie znajdują się w jednym takim drzewie jest analogicze do trzeciego podzadania.

Pozostaje więc rozpatrzyć przypadek, w którym wierzchołki znajdują się w różnych drzewach.

Wychodząc z wierzchołka \(s\) musimy dojść do korzenia drzewa, w którym się znajdujemy, następnie przejść do korzenia drzewa, który zawiera wierzchołek \(t\), a na końcu przejść z korzenia drzewa, w którym jest \(t\) do wierzchołka \(t\).

Odległość w tym przypadku to \(głębokość_s + głębokość_t + odległość(korzeń(s), korzeń(t))\).

Trudnością w tym podzadaniu była implementacja.

Przykładowa lista kroków, która realizuje powyższy pomysł:

1. Przy pomocy przeszukiwania grafu wzdłuż znajdziemy cykl w grafie i zapiszemy które wierzchołki na nim leżą.
2. Z każdego z wierzchołków na cyklu uruchomimy kolejne przeszukanie, które pójdzie tylko w kierunku wierzchołków, które na cyklu nie leżą i zapiszemy informacje:
   • o głębokości wierzchołka
   • o korzeniu drzewa, w którym się znajduje
   • informacje potrzebne do obliczania najniższego wspólnego przodka

Złożoność to \(O((m + p)\log n)\).

Pełne rozwiązanie

Zauważmy, że w poszukiwaniu najkrótszej ścieżki pomiędzy wierzchołkami \(s\) i \(t\), nie musimy ograniczać się do przeszukiwania grafu wszerz z \(s\) lub \(t\). Możemy równie dobrze rozważyć dowolny wierzchołek pośredni \(v\) leżący na takiej ścieżce i obliczyć sumę odległości \(d(v, s)\) oraz \(d(v, t)\).

Wykorzystamy tę wiedzę i spróbujemy stworzyć zbiór wierzchołków \(S\), taki, aby znajdował się w nim wierzchołek pośredni dla każdego z zapytań.

Następnie w preprocessingu obliczymy odległości z każdego wierzchołka naszego zbioru do każdego innego w czasie \(O(|S| \cdot m)\).

Na zapytanie odpowiemy, sprawdzając sumę odległości \(d(v_i, s_i) + d(v_i, t_i)\) dla każdego wierzchołka \(v_i\) z naszego zbioru \(S\). Zajmie to czas \(O(|S|)\).

Cała złożoność wynosi \(O((m + p) \cdot |S|)\).

Pozostaje pytanie, w jaki sposób wyznaczyć zbiór \(S\). Skorzystamy tutaj z własności grafu, mianowicie tego, że dla każdego zapytania istnieje co najmniej \(\lfloor \frac{n}{10} \rfloor \) wierzchołków pośrednich.

Wylosujmy dowolny zbiór wierzchołków \(S\) i spróbujmy przeliczyć prawdopodobieństwo, że znajdziemy wierzchołek pośredni dla ścieżki. Dokładniej policzymy prawdopodobieństwo porażki:

Prawdopodobieństwo, że pojedynczy wierzchołek nie jest wierzchołkiem pośrednim dla ścieżki, wynosi co najwyżej \(\frac{9}{10}\). Prawdopodobieństwo, że po powtórzeniu losowania \(|S|\) razy nie uda się ani razu, wynosi więc \((\frac{9}{10})^{|S|}\). Możemy przyjąć, że zapytania są niezależne, więc prawdopodobieństwo pponiesienia porażki na jakimkolwiek z zapytań wynosi \(p \cdot (\frac{9}{10})^{|S|} \). Wystarczy więc wyznaczyć odpowiednie \(|S|\), aby to prawdopodobieństwo było znikome.

Ponieważ od stałej \(|S|\) zależy jednocześnie złożoność obliczeniowa, jak i prawdopodobieństwo porażki, musimy znaleźć balans pomiędzy limitami czasowymi i pewnością poprawności. Za małe \(|S|\) może prowadzić do błędów, za duże do przekroczenia limitu czasowego. Rozwiązanie wzorcowe przyjmowało \(|S| = 200\).