Omówienie zadania Sieć (eliminacje do IOI 2020, dzień 1)

Niech \(k=500\) oznacza maksymalny zasięg wirusa i zarazem maksymalną długość ścieżki. Sieć traktujemy jako drzewo, którego węzłami jest \(n\) serwerów, a krawędzie oznaczają połączenia.

Rozwiązanie wzorcowe

Na początku ukorzeniamy drzewo i w czasie \(O(n)\) obliczamy głębokości wszystkich węzłów. To pozwala nam wyznaczać odległość między dowolnym węzłyem \(x\) a jego potomkiem, oznaczaną jako \(\mathtt{dist}(x,y)\), w czasie stałym.

W każdym węźle \(x\) drzewa pamiętamy dwie wartości:

• zasięg (najsilniejszego) wirusa infekującego serwer \(x\) – tablica moj_zasieg;
• maksimum po potomkach \(y\) węzła \(x\) z wartości \(\mathtt{moj\_zasieg}[y]-\mathtt{dist}(x,y)\) (innymi słowy: jak daleko jeszcze poza \(x\) sięgają wirusy z poddrzewa zaczynającego się w \(x\)) – tablica zasieg.

Rozważmy zapytanie ryzyko(a, b). Ścieżkę z \(a\) do \(b\) znajdujemy w czasie \(O(k)\), idąc w górę od \(a\) i \(b\), porównując poziomy, aż dotrzemy do najniższego wspólnego przodka \(d\). Wirus, który ma wpływ na węzeł \(c\) (znajdujący się na ścieżce z \(a\) do \(b\)), infekuje pewnego potomka \(y\) przodka \(x\) węzła \(c\), przy czym odległość z \(c\) do \(x\) jest co najwyżej \(k\). Wirus taki jest uwzględniony w tablicy zasieg dla tego przodka \(x\). Musimy w takim razie wziąć pod uwagę wartości z tablicy zasieg dla węzłów na ścieżce z \(a\) do \(b\) oraz dla węzłów o co najwyżej \(k\) w górę od najniższego wspólnego przodka \(d\). Czas działania operacji ryzyko to \(O(k)\).

Przy operacji wirus(a,d) lub antywirus(a) zmieniamy wartość moj_zasieg w węźle \(a\), a następnie aktualizujemy wartości zasieg. Wartość zasieg może zmienić się jedynie w przodkach węzła \(a\), o co najwyżej \(k\) w górę. Zauważmy, że \(\mathtt{zasieg}[x]\) to maksimum z \(\mathtt{moj\_zasieg}[x]\) oraz z \(\mathtt{zasieg}[z]\) (pomniejszonego o \(1\)) dla synów \(x\) węzła \(x\). Pytanie jak liczyć nowe maksimum, gdy jedna z tych wartości sie zmienia (zmniejsza). Gdyby każdy węzeł \(x\) miał mało synów, to moglibyśmy przeiterować po nich wszystkich i znaleźć nowe maksimum. Jednak dla węzłów z dużą liczbą synów byłoby to wolne.

Zorganizujmy w takim razie synów każdego węzła w drzewo binarne (dodając sztuczne węzły pośrednie). Gdy zmienia się zasieg w pewnym synu \(y\) węzła \(x\), to trzeba zaktualizować zasieg jedynie na ścieżce między \(x\) i \(y\) w tym "sztucznym" drzewie binarnym.

Jak powinno wyglądać takie drzewo binarne?

• Najbardziej narzuca się pomysł, aby wziąć drzewo zrównoważone. Będzie ono głębokości \(O(\log n)\). Czas działania pojedynczej operacji wirus / antywirus to \(O(k\cdot\log n)\), co daje łącznie \(O(n+q\cdot k\cdot\log n)\). Z powodu dodatkowego czynnika logarytmicznego takie rozwiązanie działa minimalnie za wolno.
• Można zrobić trochę sprytniej. Otóż syna, w którym zaczyna się największe poddrzewo, podpinamy bezpośrednio pod ojca. Pozostałe poddrzewa układamy w drzewo zrównoważone. Wówczas na każdej ścieżce liść-korzeń co najwyżej \(O(\log n)\) razy przechodzimy przez drzewo zrównoważone (w każdym takim miejscu rozmiar poddrzewa zwiększa się co najmniej dwukrotnie). Czas działania pojedynczej operacji wirus / antywirus to \(O(k+\log^2 n)\), co daje łącznie \(O(n+q\cdot k+q\cdot\log^2 n)\) (dla naszych danych \(k\) i \(\log^2 n\) to podobne wartości). Takie rozwiązanie przechodziło wszystkie testy.
• Można też zawsze łączyć według rozmiaru. Początkowo, niech \(S\) zawiera drzewa, które zaczynają się w synach danego węzła. W pętli wyciągamy dwa najmniejsze drzewa z \(S\), łączymy je (wstawiając nad nimi sztuczny węzeł) i wstawiamy tak powstałe drzewo z powrotem do \(S\). Efekt jest taki, że poddrzewo zaczynające się w węźle \(x\) jest na pewno mniejsze niż poddrzewo zaczynające się w jego wujku (tzn. bracie ojca). Faktycznie, gdy łączyliśmy \(x\) z jego bratem, to wujek (lub któryś z jego potomków) był jeszcze dostępny w \(S\). Innymi słowy, przejście z \(x\) do dziadka zwiększa rozmiar poddrzewa co najmniej dwukrotnie. Zatem na każdej ścieżce liść-korzeń (w całym drzewie) co najwyżej \(O(\log n)\) razy przechodzimy przez "sztuczny" węzeł. Czas działania pojedynczej operacji wirus / antywirus wynosi więc \(O(k+\log n)\). Inicjalizacja działa jednak w czasie \(O(n\cdot\log n)\) zamiast \(O(n)\), bo trzeba sortować synów (najłatwiej jest użyć kolejki priorytetowej). Łącznie daje to złożoność \(O(n\cdot\log n+q\cdot k+q\cdot\log n)\) (ostatni składnik jest nieistotny, bo u nas \(\log n\) jest istotnie mniejsze niż \(k\)). To rozwiązanie również przechodzi wszystkie testy.

Podzadanie 1

Pierwsza grupa rozwiązań wolniejszych to takie, w których wywołanie wirus działa szybko (tylko zapamiętujemy, gdzie jest wirus), a wywołanie ryzyko działa powoli (szukamy naiwnie wirusów zakłócających pracę serwerów na ścieżce).

Niech \(q_R\) oznacza liczbę zapytań ryzyko. W rozwiązaniu:

• wywołanie wirus zapamiętuje wirusa na liście w czasie \(O(1)\);
• wywołanie antywirus przegląda po kolei tę listę i usuwa odpowiednie wirusy w czasie \(O(q)\) (można ewentualnie przyspieszyć, ale i tak jest szybsze niż ryzyko);
• wywołanie ryzyko znajduje ścieżkę; następnie dla każdego węzła na ścieżce i dla każdego wirusa sprawdza, czy jesteśmy w zasięgu; odległość liczona algorytmem DFS w czasie \(O(n)\) (odcinamy w odległości \(k\) od źródła), co daje złożoność operacji \(O(k\cdot q\cdot n)\).

Łączny czas działania to \(O(q^2+k\cdot q\cdot q_R\cdot n)\). Rozwiązanie to przechodzi podzadanie 1.

Podzadanie 2

Rozwiązanie podzadania 2 działa podobnie, lecz szybciej liczy odległość – w czasie \(O(k)\). Otóż idziemy od badanych węzłów w górę drzewa, do ich najniższego wspólnego przodka (na początek drzewo ukorzeniamy i zapamiętujemy głębokość każdego węzła). Wywołanie ryzyko działa w czasie \(O(k^2\cdot q)\); łączny czas działania to \(O(n+q^2+k^2\cdot q\cdot q_R)\). Oprócz podzadania 1 rozwiązanie przechodzi także podzadanie 2 (gwiazda), jako że w gwieździe odległości są nie większe niż \(2\).

Podzadanie 3

W kolejnym rozwiązaniu wirusy pamiętamy w węzłach, a nie na globalnej liście. Wywołania wirus i antywirus działają w czasie \(O(1)\). Wywołanie ryzyko znajduje ścieżkę, następnie dla każdego węzła na ścieżce uruchamia przeszukiwanie DFS w poszukiwaniu wirusów zakłócających pracę odpowiadającego serwera, co daje czas \(O(k\cdot n)\). Łączny czas działania to \(O(q_R\cdot k\cdot n)\). Rozwiązanie przechodzi podzadania 1 i 3 (jedno zapytanie ryzyko).

Inne rozwiązanie podzadania 1

W kolejnej grupie rozwiązań polecenia wirus i antywirus nie działają już w czasie stałym, lecz wręcz przeciwnie: roznoszą informację do wszystkich serwerów w zasięgu rozważanego wirusa. W tym rozwiązaniu jedna rzecz jest nieoczywista: nie wystarczy trzymać informacji, czy praca danego serwera jest zakłócana (gdyż przy poleceniu antywirus nie wiemy, czy jeszcze jakiś inny wirus ma wpływ na dany serwer). Zamiast tego należy trzymać liczbę wirusów, w zasięgu których jest dany serwer. Przy poleceniu ryzyko uruchamiamy przeszukiwanie DFS, aby znaleźć ścieżkę między danymi węzłami (nie wchodzimy głębiej niż \(k\) w żadną gałąź); z węzłów na ścieżce po prostu odczytujemy, czy są pod wpływem wirusów.

Inne rozwiązanie podzadania 2

Można napisać rozwiązanie, które działa poprawnie wyłącznie w przypadku gwiazdy. W każdym węźle pamiętamy zasięg wirusa, a poza tym pamiętamy liczbę węzłów na obwodzie, które mają wirusa o zasięgu 1 lub wirusa o zasięgu 2. Operacje obsługujemy wówczas w czasie stałym; łączny czas to \(O(n+q)\).

Inne rozwiązanie podzadania 3

W tym rozwiązaniu wywołanie ryzyko najpierw znajduje ścieżkę, a następnie z każdego węzła na ścieżce uruchamia DFS tylko w stronę węzłów poza ścieżką; na koniec w czasie kwadratowym rozprowadzamy wyniki po ścieżce. Pojedyncze ryzyko działa w czasie \(O(n+k^2)\). Wywołania wirus i antywirus działają w czasie \(O(1)\). Łączny czas działania to \(O(q_R\cdot (n+k^2))\). Rozwiązanie przechodzi podzadania 1 i 3.

Podzadanie 4

Rozwiązanie to jest słabszą wersją rozwiązanie wzorcowego. W rozwiązaniu wzorcowym w celu osiągnięcia dobrej złożoności zamienialiśmy drzewo na binarne. Obsługa polecenia antywirus wymaga zmniejszenia maksimum w przypadku zmniejszenia jednego z argumentów (tj. wartości zasięgu z dzieci). W tym rozwiązaniu obsługujemy to, przeglądając wszystkich synów. Czas przetwarzania węzła jest więc proporcjonalny do liczby jego dzieci. Czas działania całego zapytania antywirus jest proporcjonalny do łącznej liczby synów wszystkich węzłów na ścieżce (długości \(d\)) z \(a\) w górę; łącznie może być ich nawet \(n\). Cały algorytm pesymistycznie działa w czasie \(O(q\cdot n)\). Rozwiązanie to przechodzi podzadania 1 i 4 (bez zapytań antywirus).