Omówienie zadania Rozdroża parzystości (III etap XXIV OI)

Wstępne badanie gruntu

Stopniem wierzchołka nazywamy liczbę krawędzi z niego wychodzących. Dla każdego wierzchołka wiemy jaką parzystość ma mieć jego stopień. W terminach teorii grafów musimy wybrać \(k\)-ty najtańszy podzbiór krawędzi grafu, który spełni żądania wszystkich wierzchołków, przy czym \(i\)-ta z krawędzi ma koszt \(2^i\).

Kiedy rozwiązanie w ogóle istnieje?

Suma stopni wszystkich wierzchołków jest równa podwojonej liczbie krawędzi, więc jest zawsze parzysta (lemat o uściskach dłoni). Jeśli więc liczba wierzchołków żądających nieparzystego stopnia będzie nieparzysta, to rozwiązanie nie może istnieć, bo z żądań wynika, że suma stopni musi być nieparzysta.

Sensowny układ parzystości to taki, w którym parzyście wiele wierzchołków ma żądanie nieparzystego stopnia.

Jeśli układ nie jest sensowny, żadne rozwiązanie nie istnieje. Pokażemy, że warunek sensowności jest jednoznaczny z istnieniem rozwiązania. Co więcej, policzymy przy tym ile jest rozwiązań spełniających nasze żądania.

Lemat (liczba planów). W spójnym grafie o \(n\) wierzchołkach i \(m\) krawędziach, dla każdego sensownego układu parzystości istnieje dokładnie \(2^{m-n+1}\) podzbiorów krawędzi go realizujących.

Dowód dla drzewa.

Skorzystamy z indukcji po liczbie wierzchołków w drzewie. Dla drzewa o jednym wierzchołku jasne jest, że plan jest dokładnie jeden. Załóżmy, że dla drzew o \(n\) wierzchołkach lemat zachodzi. Weźmy dowolny liść drzewa o \(n+1\) wierzchołkach - z jego żądania jasno wynika, że jego jedyna krawędź jest w planie wtedy i tylko wtedy gdy żąda nieparzystego stopnia. Usuwając liść razem z krawędzią dostajemy drzewo o \(n\) wierzchołkach, które z założenia indukcyjnego ma unikalny plan spełniający żądania (zmodyfikowane o usuwaną krawędź), co dowodzi ogólnej tezy lematu.

Dowód dla ogólnego grafu.

Ustalmy zatem żądany sensowny układ parzystości \(P\), który chcemy osiągnąć. Weźmy dowolne drzewo rozpinające danego grafu. Dla każdej krawędzi poza nim (których jest \(m-n+1\)) możemy sobie wybrać, czy ma ona należeć do naszego grafu lub nie. Po ustaleniu tego (co robimy na \(2^{m-n+1}\) sposobów) dostajemy zmodyfikowany przez wzięte krawędzie układ parzystości (ale nadal sensowny), któremu ma uczynić zadość wybór odpowiednich krawędzi z drzewa, co wiemy, że zawsze da się zrobić na dokładnie jeden sposób, co dowodzi ogólnej tezy lematu.

Najtańszy plan

Na razie zajmijmy się wyznaczeniem najtańszego planu (zakładamy, że układ parzystości jest sensowny). Wiemy, że chcielibyśmy iść od najcięższych krawędzi i zachłannie decydować, czy możemy jej nie brać i zachować własność, że resztę da się dopasować na co najmniej \(1\) sposób.

Załóżmy, że aktualnie rozważamy krawędź o indeksie \(i\) i zauważmy, że jeżeli rozważymy graf \(G_i\) złożony tylko z krawędzi o indeksach co najwyżej \(i\), to jeżeli rozpatrywana krawędź jest w nim mostem (tzn. jej usunięcie zwiększy liczbę składowych, która już w tym momencie może być większa niż \(1\)) to jest to już wyznaczone, czy ma ona należeć do szukanego planu, czy nie (w zależności od liczby nieparzystych stopni w składowych, na które rozpadłaby się aktualna składowa). Jeżeli tak nie jest, to możemy ją wziąć lub nie i zawsze resztę będzie się dało dopasować, zatem minimalizując zachłannie koszt, nie chcemy jej brać.

Aby móc efektywnie poznać wynik tego procesu przetworzymy te krawędzie od najmniejszych wag. Będziemy je dodawać utrzymując strukturę Find & Union. Budujemy konkretnie najtańsze drzewo rozpinające naszego grafu. Jeżeli jakaś krawędź do niego nie należy, to już na tym etapie wiemy, że możemy zachłannie ją pominąć w budowie najtańszego planu. Zachłanne odrzucenie wszystkich krawędzi spoza najtańszego drzewa rozpinającego powoduje, że należenie lub nie do planu krawędzi drzewowych jest już jednoznacznie wyznaczone. Aby wyznaczyć, które z nich mają być uwzględnione w planie, a które nie, możemy na tym drzewie uruchomić algorytm opisany w dowodzie lematu z poprzedniej sekcji. Tym samym udało nam się już rozwiązać pierwsze podzadanie, warte 32% punktów.

\(k\)-ty plan

Już wiemy, że pomocnym podziałem krawędzi jest podzielenie ich na najtańsze drzewo rozpinające \(T\), oraz resztę \(R = E \setminus T\). Dla każdej krawędzi z \(R\) chcemy wybrać, czy ją bierzemy, czy nie, a wtedy to, które krawędzie z \(T\) bierzemy jest jednoznacznie wyznaczone. Ponadto udowodniliśmy już poprawność algorytmu zachłannego. Wynika z niego, że to, czy bierzemy pewną krawędź z \(R\), nie wpływa na to, czy bierzemy droższą krawędź z \(T\).

Jeżeli zatem stworzymy ciąg zerojedynkowy mówiący, czy wzięliśmy do naszego podgrafu kolejne krawędzie z \(R\) (od najtańszych do najdroższych), to reprezentuje on binarnie pewną liczbę \(p\) (pierwszy bit jest najmniej znaczący). Taki plan jest wtedy \((p+1)\)-szym najtańszym z kolei planem. To daje jasny ogląd na to, jak wygląda \(k\)-te najtańsze rozwiązanie. Zapisujemy \((k-1)\) binarnie i to, gdzie są zapalone bity wyznacza nam, które krawędzie z \(R\) musimy uwzględnić. Mając to, uruchamiamy algorytm wyznaczający, które krawędzie z \(T\) musimy wziąć.

To daje nam rozwiązanie kolejnego podzadania wartego 25% punktów. Przedstawione rozumowanie będzie też głównym faktem w przejściu z rozwiązania dającego 87% punktów do takiego dającego 100%.

Modyfikacja parzystości miast

Teraz zajmiemy się przetwarzaniem zapytań typu \(M\). Zastanówmy się, co by się zmieniło w naszym rozumowaniu, jeżeli zmienilibyśmy parzystość jednego miasta \(v\). Po prostu nasz algorytm dynamiczny na drzewie na ścieżce od \(v\) do arbitralnie wybranego wcześniej korzenia składowej, do której należy \(v\) podejmowałby dokładnie przeciwne decyzje. Zmiana parzystości jednego wierzchołka pociąga zatem za sobą konieczność zmiany przynależności do planu krawędzi na ścieżce od \(v\) do korzenia. Taką operację będziemy nazywać flipowaniem ścieżki.

W poprzednim rozwiązaniu mogliśmy sensowność układu parzystości sprawdzić tylko raz na początku. Teraz będziemy wielokrotnie przechodzić z sensownych układów do niesensownych i na odwrót, ale nie jest to problem. Z każdą zmianą parzystości żądania przechodzimy z bezsensownego do sensownego planu i na odwrót. Wystarczy więc, że będziemy pamiętać parzystość liczby wykonanych zamian. Przy tym pamiętamy by ścieżkę flipować niezależnie od tego.

Efektywna realizacja flipowania ścieżki.

Zamiast fizycznie flipować ścieżkę do korzenia, co zajęło by czas \(O(n)\), będziemy przy pytaniu o krawędź \(e \in T\) sprawdzać czy w jej poddrzewie wykonaliśmy parzystą, czy nieparzystą liczbę zmian parzystości. To za to można efektywnie w standardowy sposób symulować na drzewie przedziałowym zbudowanym na preorderach, co opiszemy obszerniej w następnej sekcji.

Jeżeli za to jesteśmy pytani o krawędź \(e \in R\), to musimy wiedzieć, która z kolei jest to krawędź z \(R\) (co liczymy raz, w trakcie obliczania najtańszego drzewa rozpinającego) i odpowiedzieć, czy bit o odpowiednim indeksie jest zapalony w \(k-1\) (jak bit ma indeks \(\le 60\), to sprawdzamy to operacją bitową, a jak ma indeks \(>60\), to wypisujemy \(0\)). Musimy także pamiętać, że jeżeli jednak aktualny układ parzystości nie jest sensowny lub \(k > 2^{m-n+1}\), to wypisujemy \(-1\).

Takie rozwiązanie pozwala nam już zdobyć 87% punktów za zadanie.

Drzewo przedziałowe na preorderach

W tym rozdziale opiszemy dokładniej sposób flipowania ścieżek do korzenia z wykorzystaniem drzew przedziałowych. Czytelnik, któremu wystarczył bardzo skrótowy opis w poprzedniej sekcji, gdyż jest zaznajomiony z techniką w tytule tej sekcji, może ją pominąć.

Problem, do którego sprowadziliśmy flipowanie ścieżek do korzenia można podsumować jako: dane jest ukorzenione drzewo \(T\), wykonuj dwa rodzaje zapytań:

Dodaj \(1\) do wartości wierzchołka \(v\)
Stwierdź, czy suma wartości wierzchołków w poddrzewie \(v\) jest parzysta, czy nieparzysta

Chcemy na te zapytania móc odpowiadać w złożoności czasowej \(O(\log n)\).

Kluczową obserwacją jest to, że jeżeli przenumerujemy wierzchołki względem kolejności preorder, to wierzchołki składające się na poddrzewo dowolnego wierzchołka tworzą przedział liczb całkowitych. Konkretnie jest to przedział \([\mathrm{preorder}(v),\ \mathrm{preorder}(v) + \mathrm{size}(v) - 1]\), gdzie \(\mathrm{size}(v)\) to rozmiar poddrzewa \(v\) (który łatwo wyznaczyć dla każdego wierzchołka na samym początku, przed rozpoczęciem przetwarzania zapytań).

Możemy zatem sprowadzić nasz problem do następującego: dany jest ciąg \(a_1, \ldots, a_n\) początkowo stale równy 0. Wykonuj dwa rodzaje zapytań:

Dodaj \(1\) do \(a_i\)
Dla podanych liczb \(l \le r\), podaj sumę \(a_l + a_{l+1} + \ldots + a_r\)

Sprowadzenie problemu na drzewie do problemu na ciągu następuje poprzez zamianę zapytania o dodaniu \(1\) do wartości wierzchołka \(v\) na dodanie \(1\) do \(a_{\mathrm{preorder}(v)}\) oraz poprzez zamianę podania sumy wierzchołków w poddrzewie \(v\) na spytanie się o sumę \(a_{\mathrm{preorder}(v)} + \ldots + a_{\mathrm{preorder}(v) + \mathrm{size}(v) - 1}\). Wykonywanie takich operacji jest standardowym ćwiczeniem na drzewo przedziałowe, z którym można się zaznajomić np. w opisie zadania Koleje z IX OI. Dodatkowo warto zauważyć, że tak naprawdę w całym naszym drzewie przedziałowym wystarczy trzymać tylko wartości \(0\) lub \(1\), bo interesuje nas jedynie parzystość, co pozwala oszczędzić na pamięci, ale nie było wymagane do rozwiązania zadania.

Modyfikacja kosztu planu

Przejdźmy do odpowiadania na zapytania typu \(K\). Zmiana wartości \(k\) (oznaczajmy tak numer planu) na jakąś inną oznacza po prostu, że musimy wziąć inne krawędzie z \(R\). Jednak liczba \(k\) jest równa co najwyżej \(10^{18}\), zatem ma co najwyżej \(60\) bitów, które mogą być zapalone. Zatem zmiana \(k\) na inne zmieni przynależność co najwyżej \(60\) krawędzi z \(R\). Zauważmy, że jeżeli zmieniamy przynależność krawędzi \(uv \in R\) do podgrafu, to z punktu widzenia naszego drzewa rozpinającego znaczy to tyle samo, co wykonanie zapytań \(M\ u\), \(M\ v\). Jesteśmy zatem w stanie jedno zapytanie typu \(K\) zasymulować za pomocą maksymalnie \(120\) zapytań typu \(M\) (no i trzeba też pamiętać, które krawędzie z \(R\) teraz należą do planu, a które nie). Tak zaimplementowane rozwiązanie działa w złożoności \(O(\log n \cdot \log \mathrm{K_{max}})\), gdzie wspomniane \(120\) odpowiadało podwojonemu logarytmowi z maksymalnej wartości \(k\) i odpowiednio zaimplementowane może zagwarantować \(100\) punktów, jednak postaramy się przyspieszyć tę operację.

Wiemy, że zmiana liczby \(k\) wpływa tak naprawdę na przynależność co najwyżej \(60\) krawędzi z \(R\). Te \(60\) krawędzi (lub mniej jeżeli całe \(R\) ma mniej niż \(60\) krawędzi) nazwijmy ważnymi. Ustalmy pewną ważną krawędź i zastanówmy się, na które krawędzie wpływa jej zmiana. Są to mianowicie krawędzie leżące na ścieżce w \(T\) łączącej końce tej krawędzi. Możemy zatem dla każdej krawędzi z \(T\) dowiedzieć się, zmiana których ważnych krawędzi wpływa na przynależność danej krawędzi do rozpatrywanego planu. Możemy w tym celu uruchomić \(60\) DFSów lub przy okazji DFSa liczącego pierwsze rozwiązanie oraz wartości preorder oraz size policzyć odpowiednie maski bitowe to reprezentujące. Konkretnie dla \(i\)-tej ważnej krawędzi \(ab\) (indeksowanie od 0) wykonujemy \(\mathit{mask}[a]\ \mathrel{+}= 2^i\), \(\mathit{mask}[b]\ \mathrel{+}= 2^i\), a następnie tworzymy tablicę \(\mathit{xor\_mask\_subtree}[v]\), która dla wierzchołka \(v\) mówi jaki jest xor wartości tablicy \(\mathit{mask}\) dla wierzchołków z poddrzewa \(v\), co obliczamy w DFSie za pomocą prostego równania \[ \mathit{xor\_mask\_subtree}[v] = \mathit{mask}[v] \oplus \bigoplus_{\mathrm{parent}(u)=v} \mathit{xor\_mask\_subtree}[u] \] (\(\oplus\) oznacza operację xorowania, a \(\bigoplus_{\mathrm{parent}(u)=v}\) xor wartości \(\mathit{xor\_mask\_subtree}[u]\) dla \(u\) będących dziećmi \(v\)). Jeżeli \(\mathit{xor\_mask\_subtree}[v]\) ma zapalony \(i\)-ty bit, to oznacza to tyle, że przynależność \(i\)-tej ważnej krawędzi zmienia przynależności krawędzi od \(v\) do \(\mathrm{parent}(v)\).

Gdy jesteśmy pytani o krawędź drzewową i chcemy obliczyć, jak aktualna liczba \(k\) wpływa na przynależność tej krawędzi do aktualnie rozpatrywanego planu i jest to krawędź \(ab\), gdzie \(a\) jest dzieckiem \(b\), to musimy sprawdzić, czy liczba zapalonych bitów wartości \((\mathit{xor\_mask\_subtree}[a]\ \mathrm{AND}\ (k-1))\) jest parzysta lub nie. Jeżeli jest nieparzysta, to przynależność jest zmieniona.

To sprawia, że przy wykonaniu pewnych dodatkowych obliczeń na początku programu jesteśmy potem w stanie wykonywać zapytania typu \(K\) w czasie stałym (jedynie zapamiętujemy aktualną wartość i nie robimy nic więcej), o ile przy odpowiadaniu na zapytania zmodyfikujemy swoją odpowiedź w wyżej opisany sposób (co daje jedynie stały narzut czasowy na każde zapytanie).

Warto zaznaczyć, że aktualny opis zmiany przynależności liczy zmianę przynależności w stosunku do najtańszego planu, co mocno sugeruje obliczenie najtańszego planu na samym początku oraz następnie wykonanie zapytania \(K\ k\), gdzie \(k\) jest początkowo zadaną wartością, a nie liczenie \(k\)-go planu na początek.

Można jeszcze zaznaczyć, że jeżeli ktoś nie jest fanem operacji bitowych, to może wybrać alternatywną drogę implementacji (być może dla niektórych wygodniejszą), w której każdy bit rozpatrujemy osobno, co spowoduje pomnożenie złożoności czasowej w niektórych miejscach przez \(\log k\), ale cały czas będzie to czas akceptowalny.

Podsumowanie i złożoność

Podsumujmy zatem, co trzeba zrobić i ile to czasu zajmuje.

Na początku musimy zastosować algorytm wyznaczający najtańsze drzewo rozpinające (np. algorytm Kruskala), co robimy w czasie \(O(m \alpha(m))\), co dzieli nam krawędzie na \(T\) i \(R\).
Na podstawie wartości \(k-1\) wyznaczyć przynależność krawędzi z \(R\), a potem na \(T\) uruchomić algorytm DFS połączony z programowaniem dynamicznym, który policzy przynależność do planu krawędzi z \(T\), a przy okazji także i wartości preorder i size wierzchołków, które przydadzą się później. Czas \(O(m)\). Ewentualnie można nie wyznaczać w tym momencie oddzielnie przynależności \(R\) tylko założyć, że dane na wejściu \(k\) wynosi \(1\) i dodać sztuczne zapytanie \(K\ k\).
Na zapytania typu \(M\ v\) dodajemy \(1\) na drzewie przedziałowym w punkcie o indeksie równym \(\mathrm{preorder}(v)\). Czas \(O(\log n)\).
Przy zapytaniach typu \(D\ v\) najpierw sprawdzamy, czy \(k\)-ty plan w ogóle istnieje poprzez sprawdzenie czy układ parzystości jest sensowny oraz czy \(k\) jest nie większe niż sumaryczna liczba planów (tzn. \(2^{m-n+1}\)). Jeżeli tak, to patrzymy, czy krawędź należy do \(T\) czy \(R\). Jeżeli do \(R\), to uzyskujemy odpowiedź na zapytanie używając jednej lub zera operacji bitowych AND (w zależności od tego, czy indeks krawędzi w \(R\) jest większy, czy mniejszy od \(60\)) — czas \(O(1)\). Jeżeli \(e \in T\) i \(e = ab\), gdzie \(a\) jest dzieckiem \(b\) w \(T\), to czytamy sumę dodawanych jedynek na przedziale preorderów \([\mathrm{preorder}(a),\ \mathrm{preorder}(a) + \mathrm{size}(a) - 1]\), gdzie \(\mathrm{size}(a)\) jest rozmiarem poddrzewa \(a\). W zależności od tego, czy jest ona parzysta, czy nieparzysta i czy krawędź oryginalnie należała do planu budowy odpowiadamy \(0\) lub \(1\). Dodatkowo pamiętamy jeszcze aby uwzględnić wpływ liczby \(k\) na naszą odpowiedź, co obsługujemy w czasie stałym. Czas \(O(\log n)\).
W zapytaniach typu \(K\ k\) jedynie zapamiętujemy jaka jest aktualna wartość liczby \(k\). Czas \(O(1)\).