Omówienie zadania Ukryte drzewo (III etap XXXIII OI)

W tym zadaniu będziemy kodować numery wierzchołków. Z tego względu wygodnie nam będzie założyć, że numery wierzchołków w drzewie o \(n\) wierzchołkach są z zakresu od 0 do \(n-1\).

Pierwsze i drugie podzadanie

W pierwszym podzadaniu, w którym każde drzewo jest gwiazdą, musimy umieć zakodować tylko centrum gwiazdy. W tym przypadku możemy w kodzie wierzchołka zawrzeć tyle jedynek, ile wynosi jego numer.

Na więcej punktów musimy jednak lepiej zapisywać numery wierzchołków.

Trzecie i czwarte podzadanie

Kod możemy podawać w systemie binarnym; dla numerów mniejszych niż 1000 wystarczy 10 bitów. Czyli dla każdego wierzchołka (o dużym stopniu) jego kolejnym krawędziom będziemy przypisywać bity odpowiadające jego reprezentacji binarnej. Ponieważ krawędzi może być więcej, niż potrzebujemy bitów, resztę wypełnimy zerami. Dla łatwiejszej implementacji warto zastosować notację od najmniej znaczących bitów.

To podejście mogłoby się zepsuć, gdyby dwa wierzchołki na wspólnej krawędzi chciały ustawić różne bity. W tych podzadaniach nie był to problem, bo wierzchołki o dużych stopniach nie stykały się ze sobą.

Wspólna krawędź

Jeżeli dwa wierzchołki mają wspólną krawędź, to ustawienie bitu dla jednego z nich wpływa na kod drugiego. Mamy więc sytuację, w której niektóre bity są wymuszone i nie możemy ich ustawiać dowolnie.

Kluczową obserwacją jest jednak to, że pracujemy na drzewie. Jeśli nadamy kody wierzchołkom w dobrej kolejności (na przykład BFS lub DFS), to w momencie przetwarzania wierzchołka mamy co najwyżej jeden bit narzucony z góry.

Kod z wymuszonym bitem

Skoncentrujmy się na przypadku, gdy wymuszony bit jest sprzeczny z oczekiwanym kodem. Musielibyśmy wtedy zapisać, który bit jest zanegowany, a to jest niewykonalne za pomocą tylko jednego dodatkowego bitu. Dlatego w takim przypadku negujemy pozostałe bity kodu. W ten sposób wystarczy dodać informację, czy kod jest normalny, czy zanegowany, do czego wystarczy nam jeden dodatkowy bit.

Ustalamy więc format kodu w następujący sposób:

pierwszy bit mówi, czy kod jest normalny (0), czy zanegowany (1),
kolejne bity przechowują numer wierzchołka (normalny lub zanegowany).

Dzięki temu niezależnie od tego, na której pozycji pojawi się wymuszony bit, możemy zawsze dobrać jedną z dwóch wersji (normalną albo zanegowaną), tak aby warunki były spełnione.

Tak więc jeżeli wymuszony bit jest pierwszy, zostawiamy kod normalny albo negujemy go zgodnie z wartością pierwszego bitu. Natomiast jeżeli wymuszony bit jest na jednej z pozostałych pozycji, dopasowujemy do niego resztę kodu i odpowiednio ustawiamy pierwszy bit.

To rozwiązuje zadanie na 100% i poprawnie generuje kod dla wszystkich wierzchołków o stopniu co najmniej 11.

Przykład

Przykładowo, załóżmy, że wierzchołek do zakodowania ma numer 512, czyli binarnie 1000000000 (jeden i 9 zer). Skoro musimy zakodować ten wierzchołek, to ma on stopień co najmniej 11, czyli mamy do dyspozycji co najmniej 11 bitów z krawędzi. Jeden z tych bitów może być wymuszony z krawędzi do ojca wierzchołka w rozważanym ukorzenieniu drzewa. Wierzchołek możemy zakodować jako 01000000000 (normalnie) albo 10111111111 (zanegowany). Kody te nie mają żadnego bitu wspólnego, tak więc niezależnie od tego, który z tych bitów będzie wymuszony i jak, uda się wybrać pasujący kod dla wierzchołka. Pozostałe bity kodu ignorujemy, niezależnie od tego, czy jest tam wymuszone zero lub jedynka.

Gorsze kody z wymuszonym bitem

\(L=30\) – każdy bit kodu zapisujemy w trzech wersjach i wybieramy tę, która najczęściej się powtarza.
\(L=20\) – każdy bit kodu zapisujemy dwoma bitami, których XOR daje prawidłową wartość.
\(L=14-17\) – podajemy: kod (10 bitów), pozycję, na której bit jest zanegowany (4 bity), oraz informację, czy bit jest zanegowany w kodzie (w pierwszych 10 bitach), czy gdzie indziej (0-3 bity).
\(L=12-13\) – bit mówiący, czy kod jest zanegowany, zapisujemy za pomocą 2 lub 3 bitów, by był odporny na przypadek, gdy to on jest wymuszony. Wariant wzorcowy obchodzi to przez dopasowanie się do pierwszego bitu.