Muzeum

Zadanie pochodzi z ACM ICPC Central European Programming Contest, które w latach 2008–2010 były organizowane przez Instytut Informatyki Uniwersytetu Wrocławskiego. Dla mnie była to pierwsza próba zmierzenia się z układaniem zadań na zawody o takiej skali, no i cóż, chyba nie wyszedłem z tej próby z tarcza 😉 Tym niemniej dalej wydaje mi się, że mieliśmy tam kilka całkiem ładnych problemików. Ten, o którym chciałbym opowiedzieć, pojawił się na CEPC 2008, a treść można zobaczyć tutaj. Są tam podpięte testy i sprawdzaczka odpowiedzi, która przez długi czas była źle skonfigurowana, i jakoś.. jakoś nikt tego nie zauważył.

Dostajemy spójny graf nieskierowany. Co więcej, stopnie wierzchołków nie przekraczają 3. Naszym zadaniem jest odpowiednie uszeregowanie krawędzi przyległych do każdego wierzchołka v, czyli nadanie im (różnych) numerów z \{1,\ldots,\mathrm{deg}(v)\}. Uszeregowanie musi być dobre w następującym sensie: rozpoczęcie wędrówki w dowolnym wierzchołku doprowadzi do odwiedzenia wszystkich krawędzi. Sposób, w jaki wędrujemy po grafie, jest bardzo prosty:

  1. jeśli aktualny wierzchołek v jest wierzchołkiem początkowym, pójdź krawędzią o numerze 1,
  2. jeśli do aktualnego wierzchołka v trafiliśmy idąc krawędzią o numerze i, pójdź krawędzią o numerze i+1, gdzie krawędź \mathrm{deg}(v)+1 traktujemy jako krawędź 1.

Istotne jest zwrócenie uwagi na to, że będąc w wierzchołku v operujemy tylko numerami krawędzi przyległych do v, czyli cały proces nie wymaga od nas przechowywania jakiejkolwiek informacji. Dla grafu z testu przykładowego wędrówka rozpoczęta w wierzchołku 1 wygląda tak jak na poniższym rysunku. Warto zauważyć, że niektóre krawędzie zostaną odwiedzone dwukrotnie. No i że prędzej lub później wrócimy do wierzchołka startowego i spróbujemy znów pójść krawędzią o numerze 1.

muzeum-przyklad

Na początek przyjrzyjmy się przez chwilę limitom na dane wejściowe. Nasz graf może składać się z nawet 10^5 wierzchołków, czyli pewnie interesuje nas rozwiązanie liniowe. Jeszcze bardziej niepokojące jest ograniczenie stopni wierzchołków do 3. Może by na przykład podejrzewać, że gwarantuje ono istnienie rozwiązania, które niekoniecznie istnieje gdy dopuszczamy istnienie wierzchołków wyższych stopni. Okazuje się jednak, że rozwiązanie istnieje zawsze (co, samo w sobie, wydało mi się na tyle ciekawe, że waż arte ułożenia zadania), a ograniczenie stopni do 3 ma na celu tylko i wyłącznie uproszczenie implementacji.

Zacznijmy od wyobrażenia sobie procesu wędrówki w trochę inny sposób. Dla każdej krawędzi u-v tworzymy dwa wierzchołki (u,v) i (v,u). Następnie dla każdego wierzchołka u patrzymy na jego uporządkowanych sąsiadów v_1,v_2,\ldots,v_{k} i dla każdego i tworzymy (w nowym grafie) skierowaną krawędź łączącą (v_i,u) z (u,v_{i+1}). Dla grafu z testu przykładowego otrzymamy dwa (skierowane) cykle widoczne na poniższej ilustracji. Łatwo zauważyć, że w ogólności otrzymamy jakiś ich zbiór. Chcielibyśmy, żeby dla każdego u cykl, na którym leży (u,v_1), zawierał przynajmniej jeden z każdych dwóch wierzchołków odpowiadających poszczególnym krawędziom.

muzeum-cykle

Na dobry początek możemy wybrać dowolne uszeregowanie i sprawdzić jego poprawność. Jeśli okaże się, że niestety nie jest ono dobre, musimy zmienić kolejność krawędzi wychodzących z niektórych wierzchołków. Nie ma najmniejszego sensu manipulować kolejnością krawędzi przyległych do wierzchołków stopnia mniejszego niż 3. Z kolei dla wierzchołków stopnia 3 mamy tylko dwa istotnie różne uszeregowania. Musimy więc tylko zdecydować, dla których z nich kolejność zostaje taka same, a dla których należy zmienić ją na tą drugą. Taką operację będziemy nazywali (niezbyt po polsku, ale za to krótko i wygodnie) flipnięciem.

Przyjrzyjmy się bliżej sytuacji przed i po flipnięciu wokół wierzchołka u stopnia 3. Jeśli jego sąsiedzi to v_1,v_2,v_3, flipnięcie zmienia następników (i poprzedników) wierzchołków (u,v_1),(u,v_2),(u,v_3) i (v_1,u),(v_2,u),(v_3,u) na cyklach. Być może jest tak, że wszystkie te wierzchołki leżą już na jednym cyklu. Może być też tak, że leżą one na kilku z nich. A czy może być tak, że każdy znajduje się na innym cyklu? Oczywiście nie: każdy (v_i,u) leży tuż przed (u,v_{i+1}). Czyli w najgorszym przypadku wierzchołki znajdują się na 3 różnych cyklach. Twierdzimy, że w takim najgorszym przypadku zawsze warto sobie flipnąć!

muzeum-flip

Faktycznie, patrząc na powyższy rysunek łatwo się upewnić, że flipnięcie wokół u, gdy przyległe do niego krawędzie leżą na 3 różnych cyklach, powoduje sklejenie ich w jeden. Na dobry początek możemy więc wykonać taką operacje dla wszystkich takich u. Pozostaje pytanie jak zrobić to efektywnie? Możemy na przykład użyć struktury union-find do reprezentowania wierzchołków leżących na tym samym cyklu, wtedy sumaryczny czas działania wszystkich flipnięć będzie prawie liniowy. Pozostaje już tylko zastanowić się jak poradzić sobie z wierzchołkami u, których przyległe krawędzie leżą na dokładnie 2 różnych cyklach.

Popatrzmy na takie u, i dla ustalenia uwagi powiedzmy, że (v_1,u) oraz (u,v_2) leżą na jednym cyklu, a (v_2,u), (v_3,u), (u,v_1) i (u,v_3) na drugim. Flipnięcie wokół u spowoduje, że sytuacja zmieni się na następującą: (v_2,u) oraz (u,v_1) są na tym samym cyklu, a (v_1,u), (v_3,u), (u,v_2) i (u,v_3) na innym. W tym momencie musimy popatrzeć się na sytuacje w całym grafie trochę bardziej globalnie. Powiedzmy, że (nieskierowane) krawędzie (u,v_1) i (u,v_2) z opisanej przed chwilą sytuacji są niebieskie. Można zauważyć, że jeśli popatrzymy na cały (oryginalny) graf, niebieskie krawędzie tworzą tam zbiór rozłącznych wierzchołkowo cykli. Weźmy jeden taki cykl (w oryginalnym grafie) u_1 - u_2 -\ldots -u_k - u_1. Okazuje się, że jedyne, co musimy teraz zrobić, to w pewnym sensie zsynchronizować flipnięcia wokół wszystkich u_i. Jeśli (u_i,u_{i+1}) i (u_{i+1},u_{i+2}) znajdują się na tym samym cyklu, a pozostałe krawędzie przyległe do u_{i+1} są na innym, nie robimy nic. W przeciwnym wypadku flipujemy wokół u_{i+1}. W efekcie dostaniemy jeden cykl zawierający wszystkie (u_i,u_{i+1}), oraz jeden zawierający wszystkie pozostałe krawędzie przyległe do wierzchołków u_i. Powtórzenie takiej procedury dla wszystkich niebieskich cykli gwarantuje nam, że jakiś cykl zawiera przynajmniej jeden z każdej pary wierzchołków (u,v_i) i (v_i,u).

To już właściwie koniec całego pomysłu. Mając taki cykl trzeba jeszcze zapewnić, że należy do niego pierwsza krawędź wychodząca z każdego wierzchołka. Wymaga to tylko odpowiednio dobranego przesunięcia cyklicznego krawędzi wychodzących. Przy odrobinie wysiłku całe rozwiązanie można zaimplementować w czasie liniowym, choć wymaga to pozbycia się struktury union-find, co pewnie wcale nie przyśpiesza całego czasu działania.

Można się zastanawiać, na ile potrzebne było założenie o stopniach wierzchołków, które nie przekraczają 3. Okazuje się.. że nie było wcale potrzebne. Aby to zauważyć, najprościej zastosować ulubioną sztuczkę informatyków, czyli zastąpić wierzchołki wyższych stopni odpowiednio dobranymi gadżetami.

Advertisements

Skomentuj

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

Logo WordPress.com

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

Zdjęcie z Twittera

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

Facebook photo

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

Google+ photo

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

Connecting to %s