Omówienie zadania Konkurs tańca towarzyskiego (II etap XXIX OI)

Relacje pomiędzy uczestnikami konkursu będziemy reprezentowali za pomocą grafu. Wierzchołki grafu będą odpowiadały uczestnikom, natomiast istnienie nieskierowanej krawędzi pomiędzy dwoma uczestnikami będzie oznaczało, że mogą oni ze sobą tańczyć.

Podzadanie 1

Konstruowany w zadaniu graf może mieć co najwyżej \(q\) wierzchołków i co najwyżej \(q^2\) krawędzi. Wobec tego jego rozmiar to będzie \(O(q^2)\).

Za każdym razem, gdy przychodzi osoba wybredna, dodajemy jeden wierzchołek i jedną krawędź do grafu, a gdy przychodzi osoba zazdrosna, dodajemy jeden wierzchołek do grafu i robimy kopię wszystkich krawędzi z listy sąsiedztwa wierzchołka, o który jest zazdrosny. Sumarycznie czas działania wszystkich tych akcji będzie ograniczony przez sumaryczną liczbę krawędzi w ostatecznym grafie.

Jeśli listy sąsiedztwa będziemy trzymać np. w wektorach, to ich długości odzyskujemy w czasie stałym, wobec tego na każdą akcję zapytania będziemy odpowiadać w czasie stałym. Ostatecznie czas działania takiego programu to będzie \(O(q^2)\).

Podzadanie 2

W tym podzadaniu wszystkie przychodzące osoby są tego samego typu, a konkretnie zazdrosne. Graf, który konstruujemy podczas dodawania nowych osób do konkursu, jest dwudzielny: jego wierzchołki możemy podzielić na dwa zbiory \(X\) i \(Y\) w taki sposób, że każda krawędź łączy wierzchołki należące do różnych zbiorów.

Aby uzasadnić ten fakt, zauważamy, że początkowy graf zawierający jedynie wierzchołki \(1\) i \(2\) jest dwudzielny i żadna akcja nie psuje jego dwudzielności. Istotnie, jeżeli nowa osoba wybredna chce tańczyć z osobą ze zbioru \(X\), to dokładamy ją do zbioru \(Y\). A jeżeli jest zazdrosna o osobę ze zbioru \(X\), to z dwudzielności grafu wszystkie krawędzie od tej osoby prowadzą do zbioru \(Y\). Wobec tego wszystkie nowe krawędzie dla nowej osoby będą prowadzić do zbioru \(Y\), czyli tę osobę możemy umieścić w zbiorze \(X\). Argument, gdy nowy wierzchołek wybiera osobę ze zbioru \(Y\) lub jest zazdrosny o nią, jest symetryczny.

W przypadku, gdy wszystkie osoby są zazdrosne, graf ma jeszcze prostszą postać: jest pełny, to znaczy zawiera krawędź pomiędzy każdą parą wierzchołków z różnych zbiorów. W szczególności wielkość listy sąsiedztwa dla każdego wierzchołka ze zbioru \(Y\) to jest po prostu liczba wierzchołków ze zbioru \(X\). Analogicznie każdy wierzchołek ze zbioru \(X\) łączy się ze wszystkimi wierzchołkami ze zbioru \(Y\).

Wystarczy więc, że dla każdego wierzchołka będziemy obliczali, do którego zbioru on należy (a to będzie bardzo proste, ponieważ wierzchołek zazdrosny o jakiś inny wierzchołek należy do tego samego zbioru) oraz dodatkowo będziemy pamiętać liczność każdego ze zbiorów. Tak więc odpowiedź na zapytanie o jakiś wierzchołek będzie to liczba wszystkich wierzchołków z przeciwnego zbioru.

Rozwiązanie do tego podzadania jest bardzo proste i działa w czasie \(O(q)\).

Podzadanie 3

W kolejnym podzadaniu wszystkie zapytania występują po wszystkich zgłoszeniach uczestników. Wobec tego będziemy mogli najpierw przeanalizować sobie wszystkie zgłoszenia i przygotować strukturę danych, która umożliwia nam szybkie odpowiadanie na zapytania.

Zauważmy, że w rozwiązaniu brutalnym do podzadania 1 nieefektywne było obsługiwanie osób zazdrosnych, które podczas jednej akcji mogły generować dużo nowych krawędzi w grafie. W przypadku podzadania 2 wykorzystaliśmy specyfikę grafu z samymi osobami zazdrosnymi. Krawędzie tego gęstego grafu reprezentowaliśmy w sposób niejawny.

W ogólnym przypadku przydałby nam się jakiś pomysł, dzięki któremu moglibyśmy nasz graf reprezentować w bardziej zwarty sposób. Zauważmy, że każda osoba zazdrosna kopiuje listę sąsiedztwa pewnego wierzchołka. Zatem w grafach gęstych spodziewamy się, że różne wierzchołki będą współdzielić duże części swoich list sąsiedztwa. Przedstawimy teraz pomysł, który umożliwia przechowywanie takich list w sposób zwarty.

Nadal będziemy utrzymywać podział wierzchołków na dwa zbiory \(X\) i \(Y\). Nasza struktura danych będzie utrzymywać listy sąsiedztwa wszystkich wierzchołków ze zbioru \(X\). Aby obsłużyć wierzchołki ze zbioru \(Y\), skorzystamy drugi raz z tej samej struktury, tylko z zamienionymi rolami tych zbiorów.

Naszą strukturą będzie drzewo ukorzenione, które dla każdego wierzchołka ze zbioru \(Y\) będzie zawierało dokładnie jedną krawędź. Każda lista sąsiedztwa dla wierzchołka ze zbioru \(X\) będzie tutaj reprezentowana jako ścieżka zaczynająca się w pewnym wierzchołku drzewa, idąca w dół i kończąca się w pewnym innym wierzchołku.

Pokażemy teraz, jak uaktualniać nasze drzewo podczas czterech różnych rodzajów akcji rejestrowania osób do konkursu. Mamy cztery rodzaje w zależności od tego, czy rejestrujemy osobę wybredną, czy zazdrosną oraz czy ląduje ona w zbiorze \(X\), czy też \(Y\):

• Jeżeli mamy osobę wybredną, która ląduje w zbiorze \(X\), to dla tej osoby musimy stworzyć nową listę sąsiedztwa zawierającą dokładnie jeden wierzchołek ze zbioru \(Y\). Znajdujemy więc w naszym drzewie krawędź odpowiadającą temu wierzchołkowi i tworzymy z niej ścieżkę dla nowego wierzchołka.

• Osoba wybredna lądująca w zbiorze \(Y\) będzie musiała dodać nową krawędź do naszego drzewa oraz rozszerzyć listę sąsiedztwa jej ulubionego wierzchołka \(x \in X\) właśnie o tę krawędź. Robimy to w ten sposób, że ta krawędź w drzewie będzie wychodzić z dolnego wierzchołka ścieżki dla \(x\). Następnie dodajemy tę krawędź do ścieżki, przepinając jej dolny wskaźnik.

• Osoba lądująca w zbiorze \(X\), zazdrosna o jakiś inny wierzchołek \(x \in X\), będzie miała taką samą listę sąsiedztwa jak \(x\). Wystarczy zatem po prostu skopiować wskaźniki ze ścieżki dla wierzchołka \(x\).

• W końcu osoba zazdrosna lądująca w zbiorze \(Y\) musi pojawić się na wszystkich listach sąsiedztwa wierzchołków z \(X\), na których znajduje się wierzchołek \(y\in Y\), o który była zazdrosna. Zatem każdą ścieżkę zawierającą krawędź wierzchołka \(y\) będziemy musieli rozszerzyć o krawędź nowego wierzchołka. Można to bardzo prosto zrobić, dzieląc tę krawędź na dwie krawędzie.

Jak efektywnie zaimplementować te wszystkie operacje? Najwygodniej będzie trzymać drzewo w standardowy sposób, pamiętając dla każdego wierzchołka listę jego dzieci.

Wierzchołki grafu z obu zbiorów będzie wygodnie reprezentować w ujednolicony sposób, dla każdego z nich pamiętając górny i dolny wierzchołek na ścieżce w drzewie, przy czym wierzchołkom ze zbioru \(Y\) będą odpowiadały ścieżki jednokrawędziowe.

Wszystkie operacje dodawania nowych wierzchołków i przepięć wskaźników jesteśmy w stanie zrealizować w czasie stałym. Jedyną nietrywialną operacją może być podział krawędzi, ponieważ wtedy dla jednego z wierzchołków drzewa musimy usunąć jednego z jego synów. Nie musimy tego jednak robić od razu, możemy zapisać sobie na dodatkowej liście numery usuwanych wierzchołków i nie brać ich pod uwagę wtedy, kiedy będziemy przechodzić drzewo. Zatem całą konstrukcję drzewa możemy zrealizować w czasie \(O(q)\).

Mamy naszą strukturę danych, ale jak teraz odpowiadać na zapytania? Przypomnijmy, że nasza struktura obsługuje zapytania jedynie o wierzchołki \(X\). Odpowiedzią na zapytanie dla danego wierzchołka jest długość ścieżki, która mu odpowiada w drzewie. Jeżeli zatem policzymy algorytmem DFS głębokości wszystkich wierzchołków w drzewie, to odpowiedź na zapytanie będzie to po prostu różnica głębokości dolnego wierzchołka i głębokości górnego wierzchołka ścieżki. Tak więc po obliczeniach wstępnych w czasie liniowym na każde zapytanie będziemy odpowiadać w czasie stałym.

Ostatecznie zatem podzadanie 3 zrealizujemy w czasie \(O(q)\).

Pełne rozwiązanie

Rozszerzymy teraz nasze rozwiązanie podzadania 3, aby rozwiązać zadanie w pełnej ogólności, to znaczy zapytania będą mogły występować naprzemiennie z zgłoszeniami uczestników. Przy czym skorzystamy tutaj z faktu, że wszystkie akcje są tam dane od razu, to znaczy zaproponujemy rozwiązanie działające offline. W tym rozwiązaniu najpierw stworzymy sobie strukturę dokładnie taką jak w podzadaniu 3, to znaczy przejrzymy wszystkie akcje, ignorując zapytania. Następnie jeszcze raz będziemy przeglądać całą listę akcji, tym razem już odpowiadając na zapytania.

Idea jest taka, że mamy w ręku kształt, jaki przybierze nam ostateczne drzewo, przy czym w momencie drugiego przeglądania listy nie wszystkie krawędzie w tym drzewie rzeczywiście będą odpowiadały wierzchołkom ze zbioru \(Y\), które już się pojawiły. Tak więc każdej krawędzi w drzewie przypiszemy wagę \(1\) lub \(0\) w zależności od tego, czy dany wierzchołek ze zbioru \(Y\) już się pojawił. Na samym początku mamy tylko wierzchołek \(2\), wobec tego tylko jego krawędź dostanie wagę \(1\). Dla każdej akcji, która będzie tworzyć nowy wierzchołek ze zbioru \(Y\), zmienimy wagę odpowiadającej mu krawędzi na \(1\).

Teraz odpowiedzią na zapytanie nie będzie długość ścieżki, a suma jedynek, które występują na tej ścieżce. Tak więc dla naszego ukorzenionego drzewa potrzebujemy struktury danych, która umożliwi nam operację zmiany wagi danej krawędzi oraz podanie sumy wag krawędzi na pewnej ścieżce w dół drzewa.

Zauważmy, że sumę wag na takiej ścieżce możemy obliczyć jako sumę wag od korzenia do dolnego wierzchołka ścieżki minus suma wag od korzenia do górnego wierzchołka. W szczególności nie będziemy tutaj potrzebowali implementowania algorytmu LCA. Potrzebną nam strukturę możemy zrealizować za pomocą drzewa przedziałowego. Najpierw przechodzimy nasze drzewo algorytmem DFS, notując sobie numery krawędzi, które przechodzimy, z tym że jeżeli krawędź przechodzimy w górę drzewa, to zapisujemy ją ze znakiem minus. Zapisujemy również wagi tych krawędzi, przy czym dla krawędzi w górę zamiast 1 piszemy \(-1\).

Teraz sumie wag na każdej ścieżce od korzenia będzie odpowiadała suma pewnego prefiksu tej tablicy. Proste drzewo przedziałowe lub potęgowe umożliwi nam zmianę elementu oraz odpytanie się o sumę prefiksu w czasie \(O(\log q)\) dla pojedynczej operacji.

Wobec tego złożoność czasowa całego algorytmu to będzie \(O(q \log q)\).