Wielka Przesmycka Reloaded 2011 - omówienie zadań

22.11.2011

C Połącz kropki

To zadanie miało być typowym "zamulaczem", którego nie może zabraknąć w żadnym szanującym się zestawie. Można powiedzieć, że świetnie sprawdziło się w tej roli: nikt nie próbował go rozwiązać, choć być może głównie ze względu na długą treść (i to w dodatku o Jasiu).

Dla danego drzewa $ T $ definiujemy jego deck jako (multi)zbiór lasów powstałych przez usunięcie dokładnie jednego wierzchołka. W wersji basic naszym zadaniem jest sprawdzenie, czy podany na wejściu multizbiór $ n $ lasów jest deckiem pewnego drzewa $ T $. Co więcej, $ n\leq 100 $, a więc jasno widać, że będziemy mogli poszaleć ze złożonością rozwiązania. Pierwsza przydatna obserwacja jest następująca: w decku $ T $ na pewno znajduje się las składający się z tylko jednego drzewa. Dlaczego? Każde drzewo ma przynajmniej jeden liść, a usunięcie liście nie rozspaja drzewa. W drugą stronę, każdy las składający się z tylko jednego drzewa musiał powstać przez usunięcie liścia. Nasuwa to dość prosty pomysł na rozwiązanie: wybieramy z decku las składający się z jednego drzewa (jeśli takiego nie ma od razy wypisujemy NIE), a następnie próbujemy "doczepić" do niego jeden dodatkowy wierzchołek na wszystkie $ n-1 $ sposoby. Trzeba by tylko sprytnie sprawdzić czy po takim doczepieniu dostajemy $ T $, które ma taki sam deck jak ten podany na wejściu. Jak to zrobić? Najprościej skonstruować (multi)zbiór lasów powstałych przez usunięcie dokładnie jednego wierzchołka i sprawdzić czy jest taki sam... W tym momencie już jasno widać, że w tym zadaniu nie obejdziemy się bez sprytnego sprawdzania czy dwa drzewa są takie same. Co prawda taki problem jest dość trudny dla dowolnych grafów, ale dla drzew istnieje dość proste (choć wcale nie oczywiste) rozwiązanie liniowe. Co więcej, można go użyć aby dla każdego drzewa wyznaczyć jego unikalny identyfikator (liczbę naturalną nie przekraczającą sumarycznej liczby wierzchołków) o takiej własności, że identyfikatory dwóch drzew są takie same wtedy i tylko wtedy gdy drzewa są izomorficzne. Mając te wszystkie identyfikatory możemy łatwo sprawdzić czy dane dwa decki są takie same: wystarczy posortować identyfikatory drzew w każdym lesie, a następnie uporządkować leksykograficznie otrzymane krotki. Jaki będzie czas działania całego rozwiązania? Doczepiając liść na $ n-1 $ sposobów, a następnie usuwając wierzchołek na wszystkie $ n $ możliwe sposoby, dostajemy $ n^{2} $ drzew (każde na $ n-1 $ wierzchołkach). Jeśli użyjemy liniowego algorytmu wyznaczającego ich identyfikatory, cała złożoność to $ \mathcal{O}(n^{3}) $. Limity czasowe były dobrane tak, aby wystarczyło wyznaczyć identyfikatory w czasie liniowo-logarytmicznym, a więc w sumarycznej złożoności $ \mathcal{O}(n^{3}\log n) $.

Sytuacja w wersji professional na pierwszy rzut oka wydaje się podobna. Tym razem dostajemy tylko dwa lasy powstałe przez usunięcie z $ T $ dwóch różnych wierzchołków, naszym zadaniem jest (tak jak poprzednio) odtworzenie drzewa. Jeśli jeden z tych lasów jest drzewem, możemy użyć pomysłu z wersji basic. Ale oczywiście wcale tak nie musi być...

Pierwszy pomysł mógłby polegać na zgadnięciu sąsiadów usuniętych wierzchołków. W tym celu wystarczy wybrać dokładnie jeden wierzchołek w każdym drzewie (z obydwu lasów). Niestety tych drzew może być całkiem sporo i taka metoda raczej nie zakończy się niczym więcej niż bólem głowy. Możemy jednak popatrzeć na to zgadywanie w trochę inny sposób. Niech pierwszy las powstaje przez usunięcie $ u $ z $ T $, a drugie przez usunięcie $ v $ z $ T $. Informacja o sąsiadach $ u $ ($ v $) jest w pewnym sensie zakodowana w $ T\setminus\{v\} $ ($ T\setminus\{u\} $), tylko jak ją wydostać? Wyobraźmy sobie, że wiemy który wierzchołek w $ T\setminus\{v\} $ ($ T\setminus\{u\} $) odpowiada $ u $ ($ v $). Wtedy po ich usunięciu (z obydwu lasów) musimy otrzymać dwa izomorficzne zbiory drzew, patrz rysunek 4.

Rysunek 4: Lasy po usunięciu $ v $ i $ u $.

 

Mamy więc pierwszy pomysł na rozwiązanie: spróbuj usunąć po jednym wierzchołku z każdego lasu tak, aby otrzymać izomorficzne lasy. Pojawiają się jednak (przynajmniej) dwa problemy:

  1. mamy $ (n-1)^{2} $ możliwości usunięcia po jednym wierzchołku z każdego lasu, dla każdej z nich musimy sprawdzić izomorfizm drzew, a więc cała złożoność to $ \mathcal{O}(n^{3}) $... trochę sporo.
  2. jasne jest, że izomorfizm lasów jest warunkiem koniecznym, ale czy także wystarczającym? A więc, inaczej mówiąc, czy przypadkiem takie rozwiązanie jest poprawne?

Na szczęście okazuje się, że poradzenie sobie z tym pierwszym problemem może chwilę poczekać, ponieważ... takie rozwiązanie wcale nie jest poprawne. Okazuje się, że porządek drzew w otrzymanych lasach jest (trochę) istotny. A dokładniej, niech $ T\setminus\{u\}=\{T_{1},T_{2},\ldots,T_{k}\} $ i załóżmy, że usuwamy wierzchołek $ v\in T_{k} $ otrzymując $ T_{k}\setminus\{v\}=\{T'_{1},T'_{2},\ldots,T'_{k'}\} $. Dodatkowo załóżmy, że $ u $ było połączone z wierzchołkiem z $ T'_{k'} $. Wtedy {\bf sygnaturą} nazywamy trójkę składającą się z $ \{T_{1},T_{2},\ldots,T_{k-1}\} $, $ T'_{k'} $ i $ \{T'_{1},T'_{2},\ldots,T'_{k'-1}\} $, patrz rysunek 5. Podobnie definiujemy sygnaturę dla lasu otrzymanego z $ T\setminus\{v\} $, przy czym tutaj pierwszy i trzeci element krotki są ze sobą zamienione. Można udowodnić, że sygnatury $ T\setminus\{u\} $ i $ T\setminus\{v\} $ są takie same wtedy i tylko wtedy gdy dane wejściowe faktycznie odpowiadają pewnemu drzewu $ T $. Pozostaje jednak jeden problem: założyliśmy, że znamy drzewa połączone z $ u $ i $ v $. Na szczęście nasz pomysł i tak nie będzie jakiś szczególnie szybki: usuwamy na wszystkie możliwe sposoby (jest ich $ n-1 $) po jednym wierzchołku z każdego lasu. Równie dobrze możemy od razu zgadnąć po jednym sąsiedzie każdego z nich (zwiększy to ilość kombinacji w każdym lesie do $ 2(n-1) $, czyli tylko dwukrotnie).

Rysunek 5: Jedna z sygnatur otrzymanych na podstawie $ T \setminus\{v\} $ .

No dobrze, czyli mamy $ \mathcal{O}(n^{2}) $ podproblemów, w każdym z nich musimy sprawdzić izomorfizm drzew. Czyli sumaryczny czas działania to, przy najlepszych chęciach, $ \mathcal{O}(n^{3}) $. A więc nawet przy poprawnej implementacji i tak dostaniemy Time Limit Exceeded. Jak sobie z tym poradzić? Kluczowe jest następujące spostrzeżenie: to co tak naprawdę robimy, to sprawdzenie czy dwa zbiory mają wspólny element. Zamiast zgadywać po jednym elemencie z każdego z nich i sprawdzać czy jest to tak naprawdę ten sam element, o wiele lepszym pomysłem jest wygenerowanie i zapamiętanie pierwszego zbioru, a następnie przeglądanie drugiego. Dla każdego z jego elementów sprawdzamy czy był on wcześniej zapamiętany. Przy odrobinie staranności (i po zauważeniu, że zapomnieliśmy o jednym szczególnym przypadku) daje to rozwiązanie działające w czasie $ \mathcal{O}(n^{2}\log n) $.

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com