Kaktus

Wiadomo, że zadania o drzewach są fajne. Ale ileż można zajmować się drzewami? Na szczęście są też zadania o kaktusach! W tym konkretnym zajmiemy się kaktusem wierzchołkowym, czyli grafem nieskierowanym, w którym dowolne dwa cykle proste są rozłączne. Interesuje nas szybkie odpowiadania na pytania o wierzchołek, który znajduje się jak najbliżej środka najkrótszej ścieżki między podanymi dwoma wierzchołkami. Dla drzew jest to o tyle łatwe, że taka ścieżka jest unikalna, jednak jeśli rozważamy kaktusy, wcale nie musi tak być, czyli pewnie będzie ciekawie. Żeby było jeszcze ciekawiej, spróbujemy skonstruować rozwiązanie o złożoności liniowej.

Oryginalną treść (zadania F) można zobaczyć tutaj. Warto zwrócić uwagę na różnicę między kaktusem krawędziowym (w którym żadne dwa cykle proste nie mają wspólnej krawędzi) a kaktusem wierzchołkowym, z którym mamy do czynienia w zadaniu. Pewnie warto też zauważyć, że liczba wierzchołków n nie przekracza 50 000. Dość łatwo zobaczyć, że (o ile w grafie nie ma wielokrotnych krawędzi) w związku z tym liczba krawędzi m na pewno nie przekroczy 100000. Oznacza to pewnie, że autor miał odrobinę litości i postanowił, że wystarczy zaimplementować rozwiązanie o złożoności \mathcal{O}(n\log n). Ta odrobina litości jest o tyle zaskakująca, że autorzy zadań o kaktusach są jej zwykle pozbawieni: takie zadania są zwykle niesamowicie męczące implementacyjnie. Trochę jest tak i tutaj, jednak oprócz tej trudności implementacyjnej potrzebny jest przynajmniej jeden niezupełnie trywialny pomysł. Żeby było jeszcze bardziej nietrywialnie, spróbujemy zbić złożoność do liniowej, ale o tym dopiero za chwilę.

Naszym celem jest szybkie przetworzenie wielu pytań o wierzchołek, który znajduje się jak najbliżej środka najkrótszej ścieżki łączącej podane dwa wierzchołki u i v. Takich wierzchołków może być wiele, i to przynajmniej z dwóch powodów. Po pierwsze, nawet w zwykłym drzewie ścieżka łącząca dwa wierzchołki może mieć nieparzystą długość, w związku z tym mamy dwóch kandydatów na wierzchołek, który leży jak najbliżej jej środka. Jeśli zaś rozważamy kaktusy wierzchołkowe, najkrótsza ścieżka niekoniecznie jest jednoznacznie wyznaczona, jak widać na poniższej ilustracji.

kaktus1

Może więc być tak, że na każdej z możliwych najkrótszych ścieżek mamy dwóch kandydatów na odpowiedź. Łatwo zauważyć, że tak naprawdę oznacza to, że takich kandydatów w sumie może być nawet czterech, choć nie jest to w tym momencie istotne. Pewnie warto więc zacząć od skonstruowania efektywnego rozwiązania dla drzew.

Zanim zbierzemy się za wyznaczenie wierzchołka, który leży mniej więcej w połowie ścieżki, pewnie wypadałoby poznać jej długość. Ukorzeńmy nasze drzewo w (dowolnie wybranym) wierzchołku 1. Teraz jeśli interesuje nas ścieżka łącząca u i v, można podzielić ją na dwa kawałki: pierwszy łączy u z \mbox{lca}(u,v), czyli najniższym wspólnym przodkiem u i v, a drugi prowadzi z \mbox{lca}(u,v) do v. Długość ścieżki to oczywiście suma długości tych dwóch kawałków, a długość każdego kawałka to nic innego jak różnica głębokości jej końców. A głębokość każdego wierzchołka możemy sobie przecież zapamiętać! Pozostaje więc tylko wyznaczyć najniższego wspólnego przodka. Nie jest to super trywialne, ale na szczęście można skorzystać z jednego ze znanych efektywnych rozwiązań. Chyba najfajniejsze z nich, podane przez Tarjana, pozwala na odpowiedzenie na m pytań dotyczących drzewa na n wierzchołkach w czasie \mathcal{O}((m+n)\alpha(m+n,n)), gdzie \alpha jest pewną bardzo wolno rosnącą funkcja. Można o nim poczytać choćby na wikipedii. Warto w tym momencie zauważyć, że wspomniane rozwiązanie odpowiada na wszystkie pytania jednocześnie, co może być problemem w niektórych zastosowaniach. W tym naszym nie jest to kłopot, jednak pewnie warto wiedzieć, że istnieją (nawet szybsze) rozwiązania pozbawione tego ograniczenia.

No dobrze, czyli znamy długość ścieżki łączącej u i v. Teraz chcielibyśmy sprytnie dobrać się do wierzchołka, który leży jak najbliżej jej środka. Łatwo sprawdzić, w którym kawałku znajduje się środek ścieżki, więc tak naprawdę wystarczy skonstruować szybki sposób na dobranie się do k-tego przodka podanego wierzchołka u. Zauważmy, że znów nie ma potrzeby, żeby odpowiadać na każde pytanie jedno po drugim. Wystarczy, że odpowiemy na wszystkie jednocześnie. A to jest w gruncie rzeczy bardzo łatwe: wystarczy bowiem przejść drzewo w głąb utrzymując na stosie aktualną ścieżkę do korzenia. Jeśli jesteśmy aktualnie w wierzchołku u, na stosie mamy wszystkich jego przodków, a więc jeśli stos umożliwia nam szybki dostęp do k-tego elementu, możemy odpowiedzieć na wszystkie pytania dotyczące u. Wystarczy więc zaimplementować stos używając zwykłej tablicy, aby odpowiedzieć na wszystkie pytania w czasie liniowym. Czyli rozwiązaliśmy całe zadanie w wersji dla drzew w czasie bliskim liniowemu.

Ale przecież chcieliśmy się zajmować kaktusami… a dla nich jest pewnie zupełnie inaczej? Na szczęście nie jest zupełnie inaczej, gdyż przy odrobinie dobrych chęci w dowolnym kaktusie można dopatrzeć się drzewa. Wystarczy bowiem skolapsować nietrywialne cykle do pojedynczych wierzchołków, tak jak na poniższej ilustracji.

kaktus2

Widać, że ścieżce w oryginalnym kaktusie odpowiada ścieżka z u do v w utworzonym drzewie, czyli pewnie znów warto popatrzeć na najniższego wspólnego przodka \mbox{lca}(u,v) i podzielić ścieżkę na dwa kawałki. Sytuacja jest tak naprawdę odrobinę bardziej skomplikowana, gdyż krawędzie drzewa odpowiadają… no właśnie, czemu? Chyba najwygodniej udawać, że wierzchołek drzewa odpowiada najwyższemu wierzchołkowi na odpowiadającym mu cyklu w kaktusie. Wtedy każda krawędź drzewa odpowiada najkrótszej ścieżce między dwoma wierzchołkami w kaktusie. Oznacza to, że całą ścieżkę musimy pokroić na aż trzy kawałki tak jak poniżej (tym razem są one rozłączne wierzchołkowo; nie ma to większego znaczenia jeśli chodzi o implementację, ale upraszcza rysunek).

kaktus34

Musimy więc wyznaczyć nie tylko \mbox{lca}(u,v), ale też u' i v'. Okazuje się, że można w tym celu dokonać dość prostej modyfikacji algorytmu Tarjana (pewnie można też jeszcze raz przejrzeć całe drzewo i skorzystać ze sztuczki opartej na stosie zaimplementowanym na tablicy, ale taki sposób jest raczej nudnawy). Mając u' i v' można już łatwo wyliczyć długości każdego z trzech kawałków. Dla każdego wierzchołka w drzewie pamiętamy sumę długości wszystkich krawędzi na jego ścieżce do korzenia, co pozwala nam na wyznaczenie długości kawałka z u do u' oraz z v do v'. Aby wyznaczyć długość trzeciego kawałka, dla każdego wierzchołka kaktusa zapamiętujemy jego pozycję na cyklu (o ile leży on na nietrywialnym cyklu), wtedy wystarczy wyciągnąć pozycje „kaktusowych” ojców u' i v' i wykonać prosta operację arytmetyczną na ich pozycjach na cyklu. Zwróćmy uwagę, że całe rozumowanie troszkę się komplikuje, jeśli u lub v leżą na nietrywialnych cyklach, lub co nawet gorsze, jeden jest przodkiem drugiego. Załóżmy więc, że tak nie jest (uważny Czytelnik na pewno od razu zauważy, że dowolny kaktus można przerobić tak, aby nie zwiększyć istotnie jego rozmiaru, a jednocześnie uniknąć takiej niewygodnej sytuacji). Znamy więc długość najkrótszej ścieżki.

Podobnie jak w prostszej wersji zadania, możemy teraz sprawdzić, w którym z trzech kawałków leż szukany wierzchołek. Jeśli jest to ten trzeci, sytuacja jest prosta, gdyż trzeba tylko umieć szybko dobrać się do dowolnego wierzchołka na wskazanym cyklu. W tym celu wystarczy osobno zapamiętać tablicę z kolejnymi wierzchołkami na cyklu. Zajmijmy się więc wyciągnięciem k-tego wierzchołka na ścieżce z u do u'. Znów wystarczy, że przetworzymy wszystkie pytania takiej postaci jednocześnie. Przejdźmy więc nasze drzewo w głąb utrzymując na stosie wierzchołki na aktualnej ścieżce do korzenia. Przypomnijmy, że dla każdego wierzchołka v znamy sumę długości krawędzi na jego ścieżce do korzenia, oznaczmy ją \mbox{s}(v). k-ty wierzchołek na ścieżce z u do u' jest tak naprawdę k-tym wierzchołkiem na ścieżce z u do korzenia. Jeśli przodkowie u to u_0=u,u_1,u_2,\ldots, k-ty wierzchołek na ścieżce u do korzenia leży na cyklu, który odpowiada pierwszemu wierzchołkowi u_i, dla którego \mbox{s}(v) \leq s(u)-k. W praktyce pewnie odrobinę wygodniej jest jednak znaleźć ostatni wierzchołek u_i, dla którego \mbox{s}(v) > s(u)-k, a następnie przejśc do jego „kaktusowego” ojca \mbox{p}(v). Może być bowiem tak, że odpowiedzią jest pewien wierzchołek na być może długim cyklu, na którym leży \mbox p(v). Wiemy jednak, że interesuje nas k'-ty wierzchołek na najkrótszej ścieżce z \mbox p(v) do najwyższego wierzchołka na tym samym cyklu, gdzie k' może być wyznaczone za pomocą prostej operacji arytmetycznej, więc znów możemy skorzystać z zapamiętanej wcześniej listy kolejnych wierzchołków na danym cyklu. I to już właściwie koniec! Można bowiem zwrócić uwagę na to, że kolejne s(u_i) są malejące, możemy więc zastosować wyszukiwanie binarne, by odpowiedzieć na każde pytanie w czasie \mathcal{O}(\log n), co daje nam rozwiązanie całego zadania w czasie \mathcal{O}(n\log n). Ale przecież obiecaliśmy liniowkę…

Ano obiecaliśmy. Problemem jest wyszukiwanie binarne. Nie byłoby ono potrzebne, gdybyśmy przechowywali na stosie całą ścieżkę u do korzenia w oryginalnym kaktusie (bardziej formalnie: jedną z najkrótszych ścieżek). Wtedy znów moglibyśmy zaimplementować stos używając tablicy, co zapewniłoby nam dostęp do k-tego elementu w czasie stałym. Kłopotliwe może być jednak to, że przejście z v do jednego z jego dzieci u_i być może wymaga odłożenia na stos wielu wierzchołków (gdy cykl, na którym leży v, jest długi), które następnie musimy z niego pracowicie zdjąć wracając do v. Zauważmy jednak, że jeśli dzieci v są posortowane według pozycji \mbox{p}(u_i) na cyklu, odwiedzając u_{i+1} musimy wrzucić na stos wszystkie wierzchołki, które wrzuciliśmy odwiedzając u_i. Może więc po prostu nie będziemy zdejmować tych drugich? Czyli przed odwiedzeniem u_1 wrzucimy wszystkie wierzchołki na cyklu między v a \mbox{p}(u_1), przed odwiedzeniem u_2 dorzucimy jeszcze wszystkie wierzchołki między \mbox{p}(u_1) a \mbox{p}(u_2), no i tak dalej. Każdy wierzchołek na cyklu zostanie przetworzony co najwyżej raz, co zbija całkowitą złożoność do liniowej.

kaktus4

Prawie. Problem może pojawić się wtedy, gdy u_i leży na pierwszej połówce cyklu, a u_{i+1} już nie (przez pierwszą połówkę rozumiemy tutaj pierwsze \frac{\ell}{2} wierzchołki na cyklu zaczynając od v i idąc zgodnie z ruchem wskazówek zegara). Wtedy bowiem najkrótsza ścieżka z u_{i+1} ulega całkowitej zmianie. Wystarczy jednak najpierw odwiedzić wszystkie u_i znajdujące się w pierwszej połówce, a następnie powtórzyć rozumowanie (w drugą stronę, czyli idąc przeciwnie do ruchu wskazówek zegara) dla u_i w drugiej połówce. Teraz naprawdę zbija to całkowitą złożoność do liniowej.

Reklamy

6 myśli nt. „Kaktus

  1. Na rondzie zjedź … trzecim .. zjazdem. Fajne zadanie:) Chyba zostaje jeszcze taki detal, gdy jeden z u_i jest dokładnie l/2-gim na cyklu — tj. właśnie chyba ten case gdy jest więcej niż jedna droga do celu. Ale to chyba nie ma znaczenia gdzie go wtedy podepniesz.

  2. Do skończenia projektu z aplikacji jeszcze daleko, ale jest to na tyle nudne, że robię wszystko, aby go nie robić, m.in. jednak przeczytałem artykuł :P.
    Szczerze mówiąc, zadanie wydaje mi się ideologicznie wyjątkowo łatwe, z osiągnięciem złożoności liniowej włącznie. Jak czytałem po kolei, to wyobrażałem sobie DFSa po kaktusie (z uwzględnianiem wyboru krótszej części cyklu), a nie po drzewie i musiałem się zastanowić, skąd w ogóle ten logarytm się tam mógł wziąć :P. Ale kaktusy kaktusami, zanim bym to zaimplementował, to w optymistycznym przypadku minęłyby pewnie z co najmniej 3 godziny :P. Nie dziwię się, że to zadanie sprawiło największy pogrom na zawodach, na których było jedynym/jednym z dwóch zadań, którego w trakcie contestu nie zrobili Gennady, Suvorov + co, vepifanof i inni 😛 (choć jedna chińska drużyna zrobiła!).
    Swoją drogą, czy gdzieś było wykorzystywane, że ten kaktus to vertex, a nie edge cactus?
    No i się czepnę, że złożoności liniowej nie osiągnęliśmy, bo przecież musimy obliczyć LCA. No ale… no to się też da zrobić liniowo :).

    W zadaniach o kaktusach tak naprawdę dużo więcej rozkminy trzeba włożyć w to, jak to się w ogóle implementuje, w kwestie, które w opisie algorytmu się nie wnika, bo są „trywialne” i zastanawiam się, jakie triki tutaj mogłyby ułatwić implementację i wydaje mi się, że pomocne byłoby usunięcie „środkowej” krawędzi z cyklu (tzn. tej, po której wywaleniu korzeń cyklu jest na środku powstałej z niego ścieżki) – wtedy z kaktusa zrobimy drzewo i ta ostatnia część robiłaby się sama za nas w trakcie zapuszczania DFSa po oryginalnym grafie (nie po tym ze ściągniętymi cyklami). W ogóle po czymś takim całe zadanie by się sprowadziło do zadania na zwykłym drzewie, gdyby nie to, że LCA trzeba dość szczególnie rozważyć i chyba nie da się tego łatwo obejść i sprowadzić całego zadania do takowego na drzewie za pomocą łatwych trików.

    Jako nieszkodliwy dodatek wspomnę, że w zadaniach o edge kaktusach przydaje się trik, aby jako korzeń wybrać wierzchołek o stopniu <=2. Wtedy nasze drzewo po ściągnięciu cykli będzie miało unikalny cyklokorzeń.

  3. No przecież wspomniałem, że lca można robić lepiej 🙂 Mi najłatwiej myślało się o tym podczas pisania tak, że ściągamy cykle do wierzchołków, tak jak na jednym z rysunków. Dla kaktusa krawędziowego trzeba pewnie wcześniej zastąpić wierzchołek połączony z kilkoma cyklami taką wirtualną gwiazdką z krawędziami długości 0, i to chyba jedyna zmiana. Z trików ułatwiających implementację przydaje się zapewnienie, że końce zapytań są liściami.

    • Ah, rzeczywiście, to że to są vertex kaktusy wykorzystywaliśmy w tym, że mamy naturalne krawędzie między tymi zwiniętymi cyklami, nie zwróciłem na to uwagi. Ostatnio pisałem zadanie na krawędziowym kaktusie (przypuszczam, że istotnie boleśniejsze nawet od tego :P), więc przenosiłem swoje intuicje właśnie z niego. Na nich wypada to tak implementować, że pojedyncze krawędzie traktujemy jako dwukrotne, robiąc z nich cykle, a potem każdy cykl zwijamy do wierzchołka robiąc krawędź między dwoma odpowiadającym cyklom wierzchołkami u i v, jeżeli u jest „nadcyklem” v, tzn. korzeń cyklu v należy do cyklu u, ale nie jest jego korzeniem.

      I rzeczywiście umknęła mi wzmianka o szybszym lca, ale nie zostało wprost napisane, że da się liniowo, tylko że szybciej od O(n alfa(n)) :D. Choć alfa to najwolniej rosnąca sensowna funkcja, wątpię, aby istniał jakiś sensowny problem, w którym złożoność jego rozwiązania, to coś szybszego od O(n*alfa(n)), ale wolniejszego od O(n) :P.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s