Przyjaciele

Po długiej przerwie proponuję nietrywialne (choć też nie super trudne) zadanie z IOI 2014. Fajne jest w nim to, że autorzy jasno podają w treści podział testów na kolejne grupy, za które można dostać określoną liczbę punktów, co pozwala na rozwiązywanie zadania w coraz trudniejszych wersjach. Równie (a może nawet bardziej) fajne jest to, że ostateczne rozwiązanie jest istotnie krótsze niż cała treść.

W zadaniu dostajemy dość dziwacznie zdefiniowany graf nieskierowany, w którym każdy z n wierzchołków ma pewną wagę, i jesteśmy proszeni o znalezienie w nim zbioru niezależnego o jak największej sumarycznej wadze. Graf jest zdefiniowany poprzez dokładanie kolejnych wierzchołków i=1,2,\ldots,n do początkowo pustego zbioru. Wierzchołek i zostaje połączony krawędzią z pewnym wierzchołkiem v_i < i, lub kopiuje wszystkich sąsiadów pewnego wierzchołka v_i < i, lub jedno i drugie, to jest kopiuje wszystkich sąsiadów pewnego v_i < i oraz zostaje połączony z nim krawędzią.

Skoro autor był na tyle uprzejmy, że rozpisał całe zadanie na kilka coraz bardziej skomplikowanych wersji, spróbujmy popatrzeć na nie po kolei. Może jednak nie będziemy zniżać się do osobnego rozpatrywania wersji z n\leq 10. Zacznijmy więc od założenia, że n\leq 1000 i kolejny wierzchołek i zawsze kopiuje wszystkich sąsiadów v_i. Hmm. Ale przecież wtedy w grafie nigdy nie pojawi się jakakolwiek krawędź, więc możemy po prostu wziąć wszystkie wierzchołki. OK, przejdźmy więc do kolejnej wersji, w której ciągle n\leq 1000, lecz kolejny wierzchołek i kopiuje wszystkich sąsiadów v_i i zostaje połączony także z samym v_i. Dość łatwo zobaczyć, że w takim wypadku cały graf będzie jedną dużą kliką (co można pokazać indukcyjnie), więc bierzemy po prostu jeden najlepszy wierzchołek. Świetnie. To teraz wyobraźmy sobie, że n\leq 1000, a kolejny wierzchołek i zostaje połączony tylko z v_i. Wtedy cały graf jest drzewem (a może raczej drzewkiem). Czyli chcemy znaleźć najcięższy zbiór niezależny w drzewie. Jest to dość proste: wystarczy zastosować programowanie dynamiczne. Ukorzeniamy drzewo w wierzchołku 1 i dla każdego wierzchołka u wyznaczamy dwie liczby: wagę najcięższego zbioru niezależnego w poddrzewie ukorzenionym w u, który nie używa u, oraz wagę najcięższego zbioru niezależnego w poddrzewie ukorzenionym w u, do którego należy u. Dość łatwo wyliczyć te dwie liczby na podstawie liczb wyznaczonych (wcześniej) dla dzieci u w czasie proporcjonalnym do liczby tych dzieci, co daje nam rozwiązanie działające w sumarycznym czasie \mathcal{O}(n). Fajnie. To przejdźmy do kolejnej wersji, w której n\leq 1000, wszystkie wagi są równe 1, a kolejny wierzchołek i albo kopiuje wszystkich sąsiadów v_i, albo zostaje połączony tylko z v_i. Hmmm.

No tutaj nie jest już tak całkiem prosto. Można zauważyć, że konstruowany graf będzie dwudzielny, czyli interesuje nas znalezienie najliczniejszego zbioru niezależnego w grafie dwudzielnym. Twierdzenie Königa mówi, że jego rozmiar plus rozmiar największego skojarzenia to liczba wszystkich wierzchołków w grafie (tak naprawdę sytuacja jest odrobinę bardziej skomplikowana: twierdzenie mówi, że moc największego skojarzenia jest równa mocy najmniejszego pokrycia wierzchołkami; trzeba jeszcze zobaczyc, że dopełnienie pokrycia wierzchołkami jest zbiorem niezależnym i na odwrót). A największe skojarzenie w grafie dwudzielnym pewnie już potrafimy policzyć. Na pewno w czasie \mathcal{O}(n^3), a może nawet w \mathcal{O}(n^{2.5}).

No i wreszcie możemy rozwiązać właściwą część zadania, w której n\leq 100000, a kolejny wierzchołek i może zostać połączony z aktualnym grafem na dowolny z trzech sposobów. Zacznijmy od zauważenia, że tak naprawdę możemy myśleć, że wagi wszystkich wierzchołków są równe 1.

Lemat 1. Waga najcięższego zbioru niezależnego w grafie, w którym waga i-tego wierzchołka jest równa w(i), jest dokładnie taka sama jak liczność największego zbioru niezależnego w nowym (większym) grafie, w którym dla każdego z oryginalnych wierzchołków i dokładamy dokładnie w(i)-1 nowych wierzchołków, które kopiują wszystkich sąsiadów i.

Dowód. Zauważmy, że najliczniejszy zbiór niezależny w nowym grafie albo bierze dany wierzchołek i i wszystkie nowe wierzchołki, które skopiowały jego sąsiadów, albo nie bierze żadnego z nich. Wszystkie one bowiem mają takich samych sąsiadów, więc nie ma żadnego powodu, żeby traktować je w inny sposób (bardziej formalnie, jeśli wzięliśmy jeden z nich, możemy wziąć wszystkie). Ale z tego wynika, że tak naprawdę o całym procesie możemy myśleć tak, że najpierw wybieramy zbiór niezależny w oryginalnym grafie, a następnie dla każdego wybrany wierzchołek i dostajemy jeszcze w(i)-1 bonusowych. A to jest dokładnie wybieranie najcięższego zbioru niezależnego w oryginalnym grafie.

Czyli te wagi to zwykła ściema. No ale chyba nie ułatwia to jeszcze rozwiązania całego zadania. Spróbujmy więc popatrzeć na cała sytuację od drugiej strony. Dosłownie, to jest pomyślmy o ostatnim wierzchołku n. Jeśli kopiuje on wszystkich sąsiadów v_n, to optymalne rozwiązanie albo bierze zarówno n jak i v_n, albo nie bierze żadnego z nich. Można więc po prostu zwiększyć wagę v_n o w(n), usunąć n z grafu, i rekurencyjnie rozwiązać mniejszy problem. Stosując rozumowanie z lematu widzimy, że nowy graf otrzymany przed i po sklejeniu n i v_n jest dokładnie taki sam, więc takie sklejenie nie zmienia kosztu optymalnego rozwiązania.

friends1

Jeśli n zostaje połączony tylko z v_n, jest trochę inaczej. Mamy dwie możliwości: albo v_n należy do optymalnego rozwiązania, albo nie. W tym drugim przypadku n na pewno należy do optymalnego rozwiązania. Można więc myśleć, że usuwamy n z grafu, dodajemy w(n) do wyniku, i szukamy optymalnego rozwiązania w mniejszym grafie, przy czym koszt v_n w tym mniejszym grafie to w(v_n)-w(n). Aby uniknąć być może niewygodnej sytuacji, w której koszty wierzchołków stają się ujemne, dla w(n) > w(v_n) można zauważyć, że optymalne rozwiązanie na pewno nie zawiera v_n. Gdyby bowiem zawierało, to można by zastapić v_n przez n i choć trochę na tym zyskać. Czyli jeśli w(n) > w(v_n) po prostu dodajemy w(n) do wyniku i usuwamy zarówno n jak i v_n z grafu. Jeśli w(n) \leq w(v_n) też dodajemy w(n) do wyniku, zmniejszamy koszt v_n o w(n), i usuwamy n z grafu.

friends2

No i fajnie, ale co jeśli n kopiuje wszystkich sąsiadów v_n oraz zostaje połączony krawędzią z samym v_n? Wtedy optymalne rozwiązanie nie może zawierać jednocześnie n i v_n. Ale jednocześnie te dwa wierzchołki mają dokładnie tych samych sąsiadów w pozostałej części grafu, więc lepiej jest wziąć tego cięższego! Czyli tak naprawdę możemy zastąpić koszt v_n przez \max(w(n),w(v_n)) i usunąć n z grafu.

friends3

A więc w każdym z trzech możliwych przypadków udało nam się zredukować problem (w czasie stałym! o ile tylko nie zrobimy czegoś głupiego) do mniejszego. Ale czy na pewno ten mniejszy problem jest tej samej postaci? Nie do końca, bowiem czasami zdarza nam się usunąć v_n. A przecież niektóre wierzchołki mogą (na przykład) kopiować jego sąsiadów! Może więc zamiast usuwać v_n z grafu powinniśmy zaznaczyć, że jest on martwy, to jest nie może zostać wybrany w naszym rozwiązaniu? Może. Wtedy być może rozważany wierzchołek n jest martwy, wtedy bez zbędnej refleksji usuwamy go z grafu i kontynuujemy. Może być też tak, że martwy jest v_n. Wtedy dodajemy w(n) do wyniku, usuwamy n z grafu, i kontynuujemy. To, czy pozostałe wierzchołki są martwe, nie wpływa na przedstawione przed chwilą rozumowanie, więc otrzymaliśmy rozwiązanie całego zadania w czasie \mathcal{O}(n).

Advertisements

3 myśli nt. „Przyjaciele

  1. Fajne! Ja jak próbowałem robić, to zadanie, to chciałem jakoś wnikać w strukturę tego całego grafu, jakieś dziwne claimy na temat jego wyglądu formułować, uogólniać ten algorytm dla drzew, ale no nie powychodziło z tego wiele :P. A tu taka prosta redukcja :).

    • Tak. Tak naprawdę możemy po prostu zmniejszyć w(v_n) o w(n) i jechać dalej, przy czym wtedy trzeba dodać ifa, że jeśli w(n)<=0… no to coś tam. Tak czy inaczej chyba trzeba mieć ifa, więc mi się bardziej podoba jawne zabijanie wierzchołków 🙂

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