Informatyczny kącik olimpijski

Zalesianie

Tym razem omówimy zadanie Zalesianie, które pojawiło się na finale zawodów drużynowych XII Olimpiady Informatycznej Gimnazjalistów.

Zadanie (Zalesianie). Danych jest $|n$ wierzchołków ponumerowanych od $|1$ do $n.$ Ciąg $a = (a1,a2,...,an)$ składa się z wartości przyporządkowanych kolejnym wierzchołkom ( $ai$ to wartość przyporządkowana $|i$ -temu wierzchołkowi). Naszym zadaniem jest zbudować drzewo (spójny, acykliczny graf), przez ustalenie $|n− 1$ krawędzi między wierzchołkami oraz wybranie wierzchołka, który będzie korzeniem. Chcemy to zrobić w taki sposób, aby zminimalizować współczynnik niezadowolenia. Współczynnik niezadowolenia to maksymalna wartość wyrażenia $|a ⊕ a , u v$ dla takich $|u$ i $v,$ że $|u$ jest przodkiem $v$ ( $|⊕$ oznacza operację bitową xor).

Zastanówmy się najpierw nad strukturą drzewa, które budujemy. Zauważmy, że korzeń jest przodkiem każdego innego wierzchołka w tym drzewie. Zatem, licząc współczynnik niezadowolenia, zawsze będziemy rozpatrywali każdą taką parę wierzchołków $u$ i $|v,$ że $|u$ jest korzeniem drzewa. Okazuje się, że istnieje drzewo, w którym nie ma więcej par wierzchołków pozostających w relacji przodek-potomek. Wystarczy wybrać korzeń oraz połączyć go krawędziami ze wszystkimi pozostałymi wierzchołkami. Obok schemat takiego drzewa $|(K$ oznacza korzeń).

Ustaliliśmy już strukturę drzewa. Opiszemy teraz, w jaki sposób wybrać taki korzeń, który będzie minimalizował współczynnik niezadowolenia.

Rozwiązanie $O |$
Pierwszy, najbardziej intuicyjny pomysł, polega na naiwnym sprawdzeniu każdego z $n$ sposobów ustalenia korzenia. Dla każdego wierzchołka $|u∈ {1,2,...,n}$ konstruujemy drzewo, którego korzeniem jest $|u$ oraz pozostałe wierzchołki są z nim połączone krawędzią. Następnie, dla każdego z tych drzew obliczamy (z definicji) współczynnik niezadowolenia. Spośród otrzymanych wyników wybieramy najmniejszy. Drzew mamy $n$ (po jednym dla każdego kandydata na korzeń). Obliczenie współczynnika niezadowolenia dla jednego drzewa odbywa się w czasie $O(n).$ Zatem cały algorytm działa w czasie $O(n2).$

Rozwiązanie $|O$
Potraktujmy zapisy binarne elementów ciągu $a$ jako słowa nad alfabetem $|{0,1}.$ Niech $′ ′ ′ ′ b = (b 1,b2,...,bn)$ oznacza zapisy binarne kolejnych elementów ciągu $a$ ( $bi′$ oznacza zapis binarny $ai,$ który nie zawiera zer wiodących). Następnie "wyrównajmy" długości słów ciągu $b′.$ Chcemy otrzymać słowa o takiej samej długości, równej długości najdłuższego słowa w ciągu $′ b .$ W tym celu wszystkie krótsze słowa należy poprzedzić odpowiednią liczbą zer wiodących. Kolejno otrzymane słowa nazwijmy $|b = (b1,b2,...,bn).$

Podobnie jak w rozwiązaniu $O(n2),$ dla każdego potencjalnego korzenia chcemy obliczyć współczynnik niezadowolenia. W istocie, dla każdego $|bi$ chcemy znaleźć takie $b j,$ że $bi ⊕ b j$ jest maksymalne. Na potrzeby tego artykułu zakładamy, że każdemu $bi$ jest przypisana wartość $|ai$ oraz $|bi⊕ b j$ ma wartość $|ai⊕ a j.$

Weźmy $bi = cm−1 ...c1c0,$ dla którego szukamy takiego $b j = c′m−1 ...c′1c′0,$ że $|bi⊕ b j$ jest maksymalne. Idealnie byłoby, gdyby istniało $---- --- |b j = cm−1 ...c1c0$ ( $ci$ oznacza negację $|ci$ ). Wtedy $|bi⊕ b j = 2m − 1,$ czyli najlepszy możliwy wynik. Ta obserwacja daje nam pewną intuicję. Będziemy wyszukiwali $|b j$ cyfra po cyfrze, w kolejności od najbardziej znaczących do najmniej znaczących. Załóżmy, że mamy już ustalony prefiks $c′m−1c′m−2 ...c′k+1$ słowa $|b j.$ Zastanawiamy się teraz, jaką wartość może mieć $|c′. k$ Oczywiście, gdyby $′ -- |ck = ck,$ wtedy wynik wzrósłby o $k 2 .$ Zatem, jeśli $′ ′ ′ -- cm−1cm−2 ...ck+1ck$ jest prefiksem jakiegoś słowa w ciągu $b,$ to $-- |c′k = ck,$ w przeciwnym przypadku $|c′k = ck.$ Prosty dowód pozostawiamy Czytelnikowi.

Pozostało nam jeszcze opisać, w jaki sposób dla danego słowa sprawdzać, czy jest ono prefiksem jakiegoś słowa w ciągu $|b.$ W tym celu zbudujemy drzewo trie nad słowami ciągu $|b.$ Wyszukiwanie $|b j$ cyfra po cyfrze odpowiada wędrówce w drzewie trie od korzenia do liści. Załóżmy, że w danym kroku ustalamy wartość $c′k.$ Jeśli wierzchołek, w którym jesteśmy, ma dwóch synów, to poruszamy się krawędzią z etykietą $-- ck.$ W przeciwnym przypadku nie mamy wyboru - idziemy krawędzią z etykietą $ck.$ Wędrówkę kończymy w liściu. Kolejno wybierane etykiety krawędzi tworzą szukane $|b j.$

Konstrukcja drzewa trie zajmuje czas $O(n .$ Wyznaczenie $|b j$ dla danego $bi$ zajmuje czas $O(log(max$ (długość ścieżki od korzenia do liścia). Współczynnik niezadowolenia obliczamy dla każdego z $|n$ potencjalnych drzew, co w sumie daje $|O(n$ operacji. Zatem cały algorytm działa w czasie $O(n .$

Rozważmy przykład. Niech $a = (1,3,6, 7).$ Wówczas $b′= (1,11,110,111),$ $|b = (001,011,110,111),$ a drzewo trie widać na rysunku obok.