Omówienie zadania Sekretna siatka szpiegowska (II etap XXXII OI)

Zadanie

Dane jest drzewo, o którym wiadomo, że zostało wygenerowane w następujący sposób: zaczynamy od jednego wierzchołka (korzenia) i dodajemy wierzchołki po jednym. Nowy wierzchołek podłączamy do losowo wybranego spośród wcześniejszych. Numery wierzchołków na wejściu zostały zmienione, więc niekoniecznie odpowiadają kolejności dodawania. Naszym zadaniem jest znalezienie grupy wierzchołków, wśród których (z dużym prawdopodobieństwem) znajduje się korzeń drzewa.

Jak się za to zabrać?

Znamy dokładny sposób, w jaki generowane są testy do tego zadania. Z tego powodu bardzo dobrym pomysłem jest lokalne testowanie swoich rozwiązań na testach generowanych w ten sam sposób. W takim wypadku możemy spodziewać się, że te wyniki będą bardzo zbliżone do tych, które faktycznie otrzymamy.
Z tego powodu skuteczną strategią podczas zawodów było próbowanie różnych intuicyjnych podejść i dalsze eksplorowanie ich na podstawie skuteczności na własnych testach. Poniżej podajemy kilka popularnych intuicji oraz obserwacji wraz z liczbą punktów, jakie uzyskują.

Kilka pomysłów na rozwiązanie

Odcinanie liści

Podczas generacji dużego drzewa istnieje bardzo mała szansa, że korzeń pozostanie liściem (wierzchołkiem, z którego wychodzi tylko jedna krawędź). Z tego powodu można wypróbować rozwiązanie polegające na kolejnym "odcinaniu" liści z drzewa w jakiejś kolejności, aż zostanie nam tylko \(k\) wierzchołków. Wtedy możemy zwrócić te wierzchołki jako potencjalne korzenie. Takie rozwiązanie okazuje się działać całkiem dobrze, choć nie wzorcowo, i otrzymuje 80 punktów.

Liczba sąsiadów (stopień wierzchołka)

Korzeń drzewa często może mieć największą liczbę sąsiadów w całym drzewie (bo korzeń istnieje od samego początku, a każdy nowy wierzchołek ma taką samą szansę, by trafić na korzeń, co na jakiś inny wierzchołek). Z tego powodu warto spróbować zwrócić wierzchołki o największym stopniu. Niestety okazuje się, że nie jest to własność, na której można polegać (często jakieś inne wierzchołki mają trochę więcej sąsiadów), i takie rozwiązanie otrzymuje tylko 15 punktów. Możemy spróbować nieco wyeliminować ten problem, biorąc pod uwagę nie tylko stopień wierzchołka, ale również stopień jego sąsiadów, tzn. zliczyć dla każdego wierzchołka, ile jest wierzchołków w odległości niewiększej niż 2 od niego. Takie rozwiązanie otrzymuje już 35 punktów. Z tego powodu warto sprawdzić też wartości większe niż 2 – w ten sposób jesteśmy w stanie uzyskać nawet do 80 punktów. Należy jednak pamiętać, że zbyt duże wartości, przy brutalnej implementacji, mogą spowodować przekroczenie limitu czasu.

Wierzchołki przy centroidzie

Możemy intuicyjnie spodziewać się, że korzeń drzewa będzie znajdować się w pobliżu środka drzewa (można na wiele sposobów zdefiniować środek drzewa, ale nie każdy sposób dobrze wyznacza zbiór \(k\) wierzchołków). Z tego powodu warto spróbować znaleźć centroid drzewa, czyli wierzchołek, którego usunięcie powoduje, że żadne z poddrzew nie ma więcej niż połowę wierzchołków. Można wtedy wypisać wierzchołki najbliższe temu wierzchołkowi. Niestety okazuje się, że takie rozwiązanie nie działa zbyt dobrze i otrzymuje tylko 15 punktów.

Rozwiązanie wzorcowe

Rozwiązanie z centroidem może jednak zwrócić naszą uwagę na rozmiary poddrzew po usunięciu danego wierzchołka. Rozpatrzmy wierzchołki, których usunięcie powoduje, że największe poddrzewo ma najmniejszy rozmiar. Takie rozwiązanie okazuje się działać bardzo dobrze i otrzymuje 100 punktów.

Dlaczego to działa?

W drzewie, które powstaje przez dodawanie kolejnych wierzchołków do jednego początkowego korzenia, każdy kolejny wierzchołek przyłącza się losowo do już istniejących. W efekcie zwykle potomkowie korzenia rozkładają się dość równomiernie. Dlatego, jeśli obliczymy dla każdego wierzchołka, jak duże jest jego największe poddrzewo, to może się okazać, że korzeń ma relatywnie małą wartość tej miary.

Z kolei wierzchołki dodane później często mają większe wartości tej miary, ponieważ wielkość ich poddrzewa od strony korzenia jest relatywnie duża. Dlatego, jeśli zwrócimy wierzchołki o najmniejszych wartościach, to z dużym prawdopodobieństwem znajdziemy wśród nich korzeń drzewa.

Dla bardziej ciekawych czytelników polecamy artykuł (w języku angielskim), który zawiera dowód poprawności tego rozwiązania.

Jak znaleźć takie wierzchołki?

Możemy nasz graf tymczasowo ukorzenić w dowolnym wierzchołku, a następnie, zaczynając od liści, obliczyć wielkość poddrzewa każdego wierzchołka. Wystarczy dla każdego wierzchołka zsumować wielkości poddrzew jego dzieci i dodać 1 (wierzchołek sam w sobie). Znając te wartości, łatwo obliczyć wynik dla każdego wierzchołka. Wystarczy dla każdego wierzchołka znaleźć największe poddrzewo wśród jego dzieci. Należy również pamiętać o sprawdzeniu rozmiaru poddrzewa "w górę" od danego wierzchołka. Wystarczy od rozmiaru całego drzewa odjąć rozmiar poddrzewa danego wierzchołka. W ten sposób otrzymujemy rozmiar największego poddrzewa, które powstaje po usunięciu danego wierzchołka.