Omówienie zadania Unia Bajtopejska (eliminacje do IOI 2020, dzień 0)

Wstęp

W zadaniu mamy dane \( q \) zapytań o przedziały liczb \([A, B]\). Koszt połączenia pomiędzy parą liczb \( x, y \) to \( x \oplus y \), gdzie \( \oplus \) oznacza operację XOR, czyli różnicę bitów dwóch liczb. Chcielibyśmy połączyć liczby z danego przedziału w ten sposób, by używając pewnej liczby połączeń dało się przejść pomiędzy każdą parą liczb i podać minimalny koszt takiego połączenia. Innymi słowy, chcemy znaleźć koszt minimalnego drzewa rozpinającego w grafie zadanym w powyższy sposób.

Drzewa rozpinające

Jednym z najpopularniejszych algorytmów na wyszukiwanie drzew rozpinających jest algorytm Kruskala. Polega on na trawersowaniu po posortowanej liście krawędzi (posortowanej po koszcie) i łączeniu pary wierzchołków tylko wtedy, gdy w momencie przeglądania krawędzi łączącej te wierzchołki nie istnieje jeszcze ścieżka pomiędzy nimi w tworzonym przez nas drzewie. Algorytm ten, zaimplementowany brutalnie, osiąga w naszym zadaniu złożoność czasową \( O((B-A)^2\log(B-A)) \).

Optymalizacja algorytmu Kruskala

Jednym z zauważeń, które możemy poczynić, jest to, że większość krawędzi jest kompletnie bezużytecznych. Na pierwszy rzut oka może się to wydawać zauważeniem trywialnym, gdyż krawędzi jest \( O((B-A)^2) \), zaś w drzewie potrzebujemy ich jedynie \( B-A \). Okazuje się jednak, że krawędzie te mają strukturę, która pozwala nam mocno zredukować liczbę rozpatrywanych krawędzi w algorytmie Kruskala. Które więc są to krawędzie?

Zastanówmy się, jak wyglądał nasz proces, gdy rozpatrywaliśmy algorytm Kruskala brutalnie. Na początku połączyliśmy ze sobą wierzchołki, których \( \oplus \) wynosi \( 1 \), i stworzyliśmy przedziały spójne postaci \([2x, 2x+1]\). Następnie łączyliśmy spójne krawędziami o koszcie \( 2 \), czyli tak naprawdę łączymy ze sobą przedziały postaci \([4x, 4x+1]\) oraz \([4x+2, 4x+3]\) w jeden przedział \([4x, 4x+3]\). Zachodzi to dla prawie wszystkich przedziałów, potencjalnie poza tymi, które zawierają \( A \) oraz \( B \), ponieważ w ogólności mogą one być przedziałami postaci \([A, 4x+3]\) i \([4x, B]\). Teraz przyszedł czas na krawędzie o koszcie \( 3 \)... ale czy na pewno?

Zauważmy, że jeżeli złączyliśmy już pewne przedziały krawędziami o koszcie \( 1 \) i \( 2 \), a dokładniej \( 2^0 \) i \( 2^1 \), nie będzie potrzeby używać krawędzi o koszcie \( 3 \), ponieważ nie będzie żadnych krawędzi pomiędzy różnymi przedziałami o koszcie \( 3 \). Różnią się one co najmniej na bicie odpowiadającym \( 2^2 \), więc wszystkie krawędzie o koszcie \( 3 \) możemy po prostu usunąć.

Rozumowanie to możemy uogólnić, mówiąc, że jeżeli użyliśmy już wszystkich krawędzi o koszcie \( 2^k \), to rozłączne przedziały będą się różnić na co najmniej \( k+1 \)-szym bicie, więc krawędzie o koszcie z przedziału \( (2^k, 2^{k+1}) \) są bezużyteczne. Innymi słowy, obchodzą nas krawędzie o koszcie będącym potęgą liczby \( 2 \).

Jeden problem

Niestety, może się okazać, że po zakończeniu powyższego procesu zostaną nam dokładnie dwa przedziały. Weźmy na przykład zapytanie o przedział \([6, 10]\). Po rozpatrzeniu krawędzi o koszcie \( 1 \) nasze spójne będą postaci \([6, 7]\), \([8, 9]\), \([10, 10]\), a po kolejnym kroku \([6, 7]\), \([8, 10]\). Nie istnieje jednak krawędź o koszcie \( 4 \) pomiędzy tymi przedziałami, ani o koszcie będącym większą potęgą dwójki. Sytuacja, w której zostają nam na końcu dwa przedziały, jest jedynym przypadkiem, w którym użyjemy krawędzi o koszcie niebędącym potęgą dwójki.

Ponadto krawędź ta będzie miała koszt co najmniej dwa razy większy od dotychczas wziętych do rozwiązania, ponieważ wynika to z naszej tezy z poprzedniego paragrafu.

Udało nam się zredukować nasze zadanie do znalezienia najtańszej krawędzi pomiędzy dwiema spójnymi, postaci przedziałów \([A, x-1]\), \([x, B]\). Zrobiliśmy to w czasie \( O(\log B) \), ponieważ liczbę używanych krawędzi o danym koszcie jesteśmy w stanie obliczyć w czasie stałym, uważając na przedziały, które zawierają \( A \) oraz \( B \). Oznaczmy przez \( x \) obecną ilość przedziałów. Rozpatrując krawędź o koszcie \( 2^k \), do wyniku dodamy \( 2^k \cdot \left\lfloor \frac{x}{2} \right\rfloor \) lub \( 2^k \cdot \left\lfloor \frac{x-1}{2} \right\rfloor \), w zależności od tego, czy połączone będą z czymś skrajne przedziały.

Rozwiązanie wzorcowe

Jak więc rozwiązać taką sytuację? Spójrzmy na strukturę tych przedziałów. Niech \( 2^k \) będzie największą potęgą liczby \(2\), która jest mniejsza bądź równa \( B \). Jeżeli zachodzi \( 2^k \leq A < B < 2^{k+1} \), to możemy bez straty ogólności zmniejszyć \( A \) i \( B \) (wraz z ich przedziałami) o \( 2^k \), ponieważ każda liczba w przedziale zawiera \( k \)-ty bit, więc nie będzie on obecny w różnicy bitów. Gdy w końcu zachodzić będzie \( A < 2^k \leq B < 2^{k+1} \), to okaże się, że nasze przedziały są postaci \([A, 2^k)\), \([2^k, B]\).

Jest to nietrudne do dostrzeżenia, z racji że skoro nasze rozwiązanie musi zawierać krawędź o koszcie będącym co najmniej potęgą dwójki większą od wszystkich wziętych wcześniej, to będzie zawierać tylko jedną taką krawędź, gdyż inne spójne połączyliśmy tańszymi krawędziami. Ponadto, gdyby tak nie było, tj. zachodziłoby \( A < 2^k < x \leq B \) lub \( A \leq x < 2^k \leq B \), to znaczy, że musieliśmy użyć krawędzi o koszcie \( 2^k \) we wcześniejszym procesie, a teraz nie musimy już jej używać, bo istnieją takie pary liczb z różnych przedziałów, które są zgodne na \( k \)-tym bicie. Jest to jednak sprzeczne z faktem z poprzednich paragrafów, mówiącym, że ostatnia wzięta przez nas krawędź będzie droższa od tych uwzględnionych w pierwszej części zadania.

Chcemy więc znaleźć koszt minimalnej krawędzi pomiędzy przedziałami \([A, 2^k)\), \([2^k, B]\). Zauważmy, że skoro wszystkie wierzchołki w drugim przedziale mają zapalony \(k\)-ty bit, to koszt szukanej krawędzi będzie identyczny, co \(2^k +\) koszt szukanej krawędzi pomiędzy przedziałami \(S_a = [A, 2^k)\), \(S_b = [0, B-2^k]\). Następnie zadanie rozwiążemy konsekwentnie zmniejszając przedziały, tak, by w prosty sposób odzyskać z nich wynik. Rozważmy kilka przypadków:

• Jeżeli dwa przedziały się przecinają, to koszt połączenia między nimi jest równy \( 0 \).
• Jeżeli \(\min S_a < 2^{k-1}\), to znaczy, że pewien sufiks przedziału \(S_a\) zawiera \((k-1)\)-wszy bit, a zarówno prefiks, jak i \(S_b\) nie zawierają tego bitu, czyli krawędź będzie na pewno pomiędzy \(S_b\) a prefiksem \(S_a\), czyli możemy "uciąć" \(S_a\) do tego prefiksu.
• Jeżeli \(2^{k-1} \leq \max S_b\), to znaczy, że prefiks przedziału \(S_a\) nie zawiera \((k-1)\)-wszego bitu, a zarówno sufiks, jak i \(S_a\) zawierają ten bit. Analogicznie, krawędź będzie na pewno pomiędzy \(S_a\) a sufiksem \(S_b\), czyli możemy "uciąć" \(S_b\) do tego sufiksu, a następnie pomniejszyć każdy element \(S_a\) i \(S_b\) o \(2^{k-1}\), ponieważ wynik pozostanie taki sam i \(\min S_b\) będzie dalej równy \(0\).
• W przeciwnym wypadku każdy element \(S_a\) zawiera \((k-1)\)-wszy bit, zaś żaden z \(S_b\) go nie zawiera. Dodajemy więc \(2^{k-1}\) do wyniku i pomniejszamy każdy element z \(S_a\) o \(2^{k-1}\), ponieważ uwzględniliśmy ten bit w wyniku.
• Po rozważeniu tych przypadków pomniejszamy \(k\) o \(1\) i powtarzamy proces, dopóki nie będzie spełniony pierwszy warunek.

Proces ten zajmuje \(O(\log B)\) czasu, czyli rozwiązaliśmy całe zadanie w czasie \(O(q \log (\max B))\).