Omówienie zadania Kolekcjoner bajtemonów 2 (III etap XXVIII OI)

Mamy \(n\) par liczb \((a_i,b_i)\), przy czym \(1 \leq a_i \leq A\) oraz \(1 \leq b_i \leq B\). Chcemy wybrać po jednej liczbie z każdej pary tak, aby największy wspólny dzielnik (NWD) wybranych liczb był jak największy.

Podzadanie 1

Na rozwiązanie zadania mogą naprowadzać dosyć nietypowe ograniczenia na wielkości liczb z wejścia, gdyż \(A=5\cdot 10^5\), natomiast \(B=2^{63}-1\). Może to sugerować algorytm, w którym będziemy się iterować po wszystkich możliwych wartościach \(a_i\).

Kluczowa obserwacja jest taka, że jeżeli wybierzemy choć jedną liczbę \(a_i\), to odpowiedź, czyli wynikowe NWD, nie będzie większe niż \(A\). Wynika to z tego, że NWD dowolnego zbioru liczb jest nie większe niż każda z tych liczb.

Na początek rozwiązujemy przypadek szczególny, w którym nie wybieramy żadnej wartości \(a_i\). W takim przypadku odpowiedzią byłoby \(NWD(b_1,b_2,\ldots,b_n)\). Jest to jedyny możliwy przypadek, w którym odpowiedź może być większa niż \(A\).

W drugim przypadku zakładamy, że bierzemy jakieś \(a_i\), więc odpowiedź nie może być większa niż \(A\). Iterujemy się po każdej wartości \(g\) z przedziału \([1,A]\) i sprawdzamy, czy \(g\) może być odpowiedzią. To znaczy, czy istnieje taki wybór liczb, że NWD wybranych liczb jest równe co najmniej \(g\).

Aby to sprawdzić, możemy przeiterować się po wszystkich parach i popatrzeć, czy dla każdej z nich chociaż jedna z liczb \(a_i\) lub \(b_i\) jest podzielna przez \(g\). Jeżeli tak i wszystkie wybrane liczby będą podzielne przez \(g\), to i wynikowe NWD będzie podzielne przez \(g\). Oczywiście może się zdarzyć, że będzie ono większe, ale to nam nie przeszkadza.

Tę część możemy zaimplementować w czasie \(O(A n)\), ponieważ dla każdego kandydata na odpowiedź musimy przejrzeć wszystkie pary liczb.

Dodatkowo musimy obliczyć NWD wszystkich liczb \(b_i\) z przypadku pierwszego, a możemy to zrobić przez obliczenie \(n-1\) razy NWD dla dwóch liczb, bo \[NWD(b_1,b_2,\ldots,b_{n-1},b_n) = NWD(NWD(b_1,b_2,\ldots,b_{n-1}), b_n).\] Realizacja tego algorytmem Euklidesa da nam czas \(O(n \log{B})\). Ostatecznie taka złożoność była wystarczająca do zaliczenia pierwszego podzadania.

Lepsze rozwiązanie

Dla rozwiązania ogólnej wersji zadania będziemy potrzebowali jakiegoś szybszego sposobu na sprawdzenie, czy kandydat \(g\) może być odpowiedzią. Załóżmy, że w naszej procedurze sprawdzającej, czy \(g\) może być odpowiedzią, dla każdej pary najpierw próbujemy wziąć do zbioru wartość \(a_i\). Jeżeli jest ona podzielna przez \(g\), to możemy to zrobić, ale jeżeli nie jest podzielna, wtedy jesteśmy zmuszeni wziąć do zbioru wartość \(b_i\). Innymi słowy, będziemy musieli wziąć do zbioru wszystkie wartości \(b_i\), które pochodzą z par, w których wartości \(a_i\) nie są podzielne przez \(g\).

Tak więc widać, że nasza odpowiedź będzie równa co najwyżej wartości \[D_g = NWD(b_k \mid g \textrm{ nie dzieli } a_k).\] Jeśli zatem \(D_g\) nie jest podzielne przez \(g\), to \(g\) nie może być odpowiedzią. W przeciwnym przypadku może być, bo to oznacza, że wymuszone wartości \(b_i\) są wszystkie podzielne przez \(g\).

Aby sprawnie obliczać wartości z tego wzoru, wprowadzimy sobie pomocniczą tablicę \(d[1..A]\), w której w ramach preprocessingu obliczymy \[d[i] = NWD(b_k \mid a_k = i).\] Taki preprocessing możemy zrobić w czasie \(O(n\log B)\).

Wtedy wzór na \(D_g\) przyjmuje postać \[D_g = NWD(d[i] \mid g \textrm{ nie dzieli } i).\]

Czyli będziemy chcieli obliczyć NWD z komórek tablicy \(d\), które leżą w przedziałach \[[1, g-1],\ \ [g+1,2g-1],\ \ [2g+1,3g-1],\ \ \ldots\]

Tych przedziałów będzie \(\lceil A/g \rceil\). Jeśli posumujemy to po wszystkich kandydatach \(g\), to dostaniemy sumaryczną ilość zapytań o NWD na przedziałach, które będziemy musieli wykonać: \[\sum_{g=1}^{A} \left\lceil \frac{A}g \right\rceil = O(A \log A).\]

Ponieważ NWD jest operacją łączną, więc jako strukturę danych do zapytań o przedziały możemy wziąć drzewo przedziałowe. Przy szacowaniu złożoności czasowej rozwiązania z drzewem musimy wziąć pod uwagę koszt tworzenia tego drzewa oraz koszt pojedynczego zapytania.

Koszt tworzenia drzewa jest proporcjonalny do iloczynu jego rozmiaru oraz złożoności czasowej dla pojedynczej operacji na drzewie. W naszym przypadku drzewo jest budowane nad tablicą \(d\), wobec tego ma rozmiar \(A\), a pojedyncza operacja wymaga uruchomienia algorytmu Euklidesa dla liczb rzędu \(B\), czyli \(O(\log B)\). Wobec tego inicjalizacja struktury działa w czasie \(O(A \log{B})\).

Jeśli chodzi o zapytania na drzewie, to ustaliliśmy już, że będzie ich \(O(A\log A)\). Koszt pojedynczego zapytania jest to dodatkowy logarytm z wielkości drzewa oraz koszt pojedynczej operacji, zatem \(O(\log A \cdot \log B)\). Ostateczny koszt zapytań to \(O(A \log^2 A \cdot \log B)\).

Złożoność czasowa całego algorytmu będzie \(O(n\log B + A \log^2 A \cdot \log B)\).

Alternatywna struktura danych

Warto wspomnieć, że w tym algorytmie alternatywą dla drzewa przedziałowego może być struktura danych zwana jako słownik podsłów bazowych występująca m.in. w algorytmie Karpa–Millera–Rosenberga. Szczegółowy opis zarówno drzewa przedziałowego, jak i słownika podsłów bazowych można znaleźć w książce Przygody Bajtazara.

Aby słownik podsłów bazowych umożliwiał nam na odpowiadanie o wartości operacji dla pewnego przedziału, ta operacja musi być nie tylko łączna, ale i idempotentna, to znaczy zastosowana do dwóch równych wartości musi dawać ją w wyniku. Na szczęście to jest prawdą dla operacji NWD, gdyż \(NWD(x,x)=x\).

W porównaniu do drzewa przedziałowego słownik podsłów bazowych umożliwia nam szybsze odpowiadanie na zapytania przy nieco wolniejszej konstrukcji struktury. W naszym przypadku zarówno czas inicjalizacji jak i wszystkich zapytań będzie wynosił \(O(A \log A \cdot \log B)\).

Rozwiązanie wzorcowe

Na początek zauważymy, że możemy znacząco ograniczyć liczbę operacji NWD, które wykonujemy. Przypomnijmy, że chcemy obliczyć, czy NWD ze wszystkich wartości \(d[i]\) na przedziałach jest podzielne przez \(g\). Ale do tego nie potrzebujemy obliczać NWD ze wszystkich przedziałów, wystarczy nam dla każdego przedziału sprawdzić, czy jego NWD jest podzielne przez \(g\). A taką podzielność możemy sprawdzić w czasie stałym. To powoduje, że w przypadku słownika podsłów bazowych w ogóle nie potrzebujemy wykonywać operacji NWD podczas zapytań.

Okazuje się, że tak jest również w przypadku drzewa przedziałowego. Standardowo bowiem wykonalibyśmy operację NWD dla wszystkich przedziałów bazowych, które tworzą dany przedział. Ale zamiast tego dla każdego przedziału bazowego możemy sprawdzić, czy obliczone dla niego NWD podczas inicjalizacji jest podzielne przez \(g\). To usunie nam czynniki \(\log{B}\) ze złożoności dla zapytań.

Druga obserwacja polepszająca nasze szacowania złożoności czasowej dotyczy wyznaczenia NWD dla wielu liczb. Okazuje się bowiem, że uruchomienie algorytmu Euklidesa \(n-1\) razy w pętli, której czas działania oszacowaliśmy przez \(O(n \log{B})\), działa tak naprawdę w czasie \(O(n + \log{B})\). W pojedynczym wywołaniu algorytmu Euklidesa, z grubsza każda para wywołań rekurencyjnych, poza być może pierwszym i ostatnim, powoduje, że oba argumenty zmniejszają się o co najmniej połowę. To uzasadnia, dlaczego standardowo algorytm Euklidesa działa w czasie \(O(\log{B})\).

Zauważmy jednak, że jeżeli wykonujemy ten algorytm dla wielokrotnie aktualizowanego argumentu \(x\), to górne oszacowanie na zmienność tego argumentu będzie dotyczyć wszystkich NWD. Tak więc złożoność to będzie \(O(n + \log B)\), gdzie \(n\) jest na wszystkie wywołania rekurencyjne, które nie zmieniają wartości \(x\), zaś \(\log{B}\) na te wywołania, które zmniejszają \(x\) o połowę.

Analogicznie możemy pokazać, że czas wypełniania tablicy \(d\) to będzie \(O(n + A \cdot \log{B})\), gdyż uruchamiamy tutaj algorytm NWD \(n\)-krotnie, ale liczba aktualizowanych wartości wynosi \(A\).

Tą obserwację możemy jeszcze zastosować w przypadku inicjalizowania słownika podsłów bazowych. Tutaj dla każdej z \(A\) pozycji generujemy logarytmiczną liczbę przedziałów bazowych, które zaczynają się na tej pozycji. Zatem policzenie NWD dla pewnego przedziału bazowego możemy potraktować jako uaktualnienie wartości NWD dla dwa razy krótszego przedziału zaczynającego się w tej samej pozycji. To spowoduje, że będziemy mieli \(O(A \log{A})\) uruchomień algorytmu Euklidesa, ale tylko \(A\) uaktualnianych wartości. Zatem złożoność czasowa tworzenia słownika będzie mogła być oszacowana przez \(O(A \log{A} + A \log{B})\).

Ostatecznie koszt dla drzewa przedziałowego to \(O(A \log B)\) na inicjalizację i \(O(A \log^2 A)\) na zapytania. Natomiast dla słownika podsłów bazowych to \(O(A\log A + A\log B)\) na inicjalizację i \(O(A \log A)\) na zapytania.

W tym momencie stwierdzenie, czy lepiej wybrać drzewo przedziałowe, czy słownik podsłów bazowych już nie jest takie oczywiste i wymaga porównania, czy lepiej zużyć czas \(O(\log^2{A})\), czy \(O(\log{A} + \log{B})\). Ponieważ \(\log{A}\) może być rzędu \(20\), natomiast \(\log{B}\) rzędu ponad \(60\), więc te wartości różnią się na tyle mało, że przy porównaniu istotne będą również czynniki stałe związane z efektywną implementacją tych struktur.

W przypadku naszego zadania skorzystanie z każdej z tych struktur da nam efektywny algorytm i pozwoli uzyskać komplet punktów.