Omówienie zadania Reprezentacje różnicowe (I etap XXIV OI)

Mimo tego, iż ciąg \(\mathbf{a} = (a_1, a_2, a_3, \ldots)\) rośnie bardzo szybko, do rozwiązania zadania nie będziemy potrzebować wyznaczania dokładnych (potencjalnie gigantycznych) wartości wyrazów ciągu o dalekich indeksach, chociaż te właśnie indeksy mogą być wynikiem zadania. Jest to zasadnicza istota oraz najciekawszy aspekt zadania.

Do rozwiązania zadania wystarczy dobrze zrozumieć definicję ciągu \(\mathbf{a}\). Ciąg jaki jest — każdy widzi. Zauważmy, że ciąg \(\mathbf{a}\) jest rosnący i dla każdego \(n\) zachodzi \(a_{n+2} > 2a_n\) \((*)\). Ta własność jest kluczowa do efektywnego rozwiązania zadania.

Dla danego \(x\), przez \(\operatorname{ind}(x)\) oznaczmy najmniejszy parzysty indeks \(k\) elementu ciągu \(\mathbf{a}\), który spełnia \(a_k > x\). Na przykład \(\operatorname{ind}(18) = 6\). Na mocy własności \((*)\) wiemy, że \(\operatorname{ind}(x) \le 2\log_2 x\). W algorytmie liczymy explicite jedynie wyrazy o indeksach co najwyżej \(\operatorname{ind}(x)\), a więc tylko logarytmicznie wiele.

Schemat algorytmu.

Niech \(\operatorname{rank}(x, B)\) oznacza rangę elementu \(x\) w zbiorze \(B\), czyli liczbę elementów w \(B\) mniejszych od lub równych \(x\). Oznaczmy ponadto przez \(\bar{B}\) dopełnienie zbioru \(B\) względem zbioru dodatnich liczb całkowitych. Zbiór \(B\) będzie u nas skończony, natomiast \(\bar{B}\) (wirtualnie) nieskończony.

Poniższy algorytm oblicza parę \(p, q\) taką, że \(a_p - a_q = x\).

Przykład.

Niech \(x = 18\); wtedy \(\operatorname{ind}(18) = 6\). Algorytm oblicza \[A = [1, \dots, 8] \cup [12, \dots, 15] \cup \{17, 19, 20\},\quad \bar{A} = \{9, 10, 11, 16, 18\} \cup [21, \dots, \infty].\] Następnie algorytm zwraca parę \((p, p-1) = (16, 15)\), ponieważ \(\operatorname{rank}(18, \bar{A}) = 5\), \(p = 6 + 2 \cdot 5\). \[1 \to 2 \to 4 \to 8 \to 16 \to 21 \,\stackrel{{\times}2}{\longrightarrow}\, a_7 \,\stackrel{+9}{\longrightarrow}\, a_8 \,\stackrel{{\times}2}{\longrightarrow}\, a_9 \,\stackrel{+10}{\longrightarrow}\,\] \[a_{10} \,\stackrel{{\times}2}{\longrightarrow}\, a_{11} \,\stackrel{+10}{\longrightarrow}\, a_{12} \,\stackrel{{\times}2}{\longrightarrow}\, a_{13} \,\stackrel{+16}{\longrightarrow}\, a_{14} \,\stackrel{{\times}2}{\longrightarrow}\, a_{15} \,\stackrel{+18}{\longrightarrow}\, a_{16}.\] Zauważmy, że nie musimy znać wartości \(a_7, \ldots, a_{16}\).

Poprawność.

Udowodnimy, że różnice \(a_p - a_{p-1}\) dla \(p > \operatorname{ind}(x)\) parzystych są kolejnymi liczbami niewystępującymi w zbiorze \(A\), aż któraś z nich jest równa \(x\). Wygenerujmy prefiks ciągu długości \(\operatorname{ind}(x)\). Jeśli \(x = a_p - a_q\) dla \(p \le \operatorname{ind}(x)\), to łatwo wyznaczyć te indeksy, przeglądając wszystkie pary elementów w wygenerowanym prefiksie ciągu.

Załóżmy, że \(x = a_p - a_q\) dla \(p > \operatorname{ind}(x)\). Wykażemy, że wówczas \(q = p - 1\). Zauważmy, że \(k = \operatorname{ind}(x)\) zgodnie z definicją jest parzyste i spełnia \(a_k > x\). Mamy wówczas \(a_{k+1} - a_k = 2a_k - a_k = a_k > x\). To oznacza, że szukana para indeksów \((p, q)\) nie istnieje dla \(p = k+1\) ani też dla żadnego \(p > k+1\) nieparzystego, na mocy własności \((*)\).

Załóżmy więc, że \(x = a_p - a_q\) dla \(p\) parzystego, \(p > k\). Mamy wówczas \(a_p - a_{p-2} > a_{p-1} - a_{p-2} > x\); ta druga nierówność wynika z faktu, że wówczas \(p - 1 > k\) i jest nieparzyste, a ten przypadek rozważyliśmy wcześniej. To oznacza, że \(a_p - a_q > x\) dla dowolnego \(q \le p - 2\). Stąd, rzeczywiście, \(q = p - 1\).

Implementacja.

Pewien niepokój może budzić nieskończony rozmiar zbioru \(\bar{A}\). Jednakże zamiast liczyć \(\operatorname{rank}(x, \bar{A})\) wystarczy liczyć \(\operatorname{rank}(x, A)\), ponieważ

\(\operatorname{rank}(x, \bar{A}) = x - \operatorname{rank}(x, A).\)

Maksymalny wynik, tj. \(p = 1\,999\,997\,160\), \(q = p - 1\) dla \(x = 10^9\), mieści się w typie int. Od tego miejsca możliwych jest kilka implementacji o nieco różniących się złożonościach. Niech \(n\) oznacza liczbę zapytań, a \(X\) oznacza maksymalną liczbę \(x\) w zapytaniu.

• Generujemy zbiór \(A\) dla \(x = X\) (czas \(O(\log^2 X)\)), zapamiętując dla każdego wygenerowanego elementu indeksy \((p, q)\). Sortujemy zbiór \(A\) (czas \(O(\log^2 X \log \log X)\)). Następnie dla każdego zapytania \(x\) wyszukujemy binarnie jego rangę \(\operatorname{rank}(x, A)\) i albo zwracamy parę \((p, q)\), jeśli \(x \in A\), albo obliczamy wynik w czasie stałym na podstawie rangi według opisanej powyżej procedury. Czas tego ostatniego kroku to \(O(n \log \log X)\) ze względu na wyszukiwanie binarne w zbiorze rozmiaru \(O(\log^2 X)\).

  Ostateczna złożoność to \(O(\log^2 X \log \log X + n \log \log X)\).

• Na początku wczytujemy wszystkie zapytania i umieszczamy je w zbiorze (np. set w C++), co zajmie czas \(O(n \log n)\). Generujemy zbiór \(A\) dla \(x = X\) (czas \(O(\log^2 X)\)). W trakcie generowania sprawdzamy, dla każdego elementu zbioru \(A\), czy znajduje się w zbiorze (czas \(O(\log^2 X \cdot \log n)\)). Jeśli tak, to od razu zapisujemy wynik dla tego zapytania i usuwamy je ze zbioru. Na koniec sortujemy zbiór \(A\) (czas \(O(\log^2 X \log \log X)\)). Teraz przeglądamy wszystkie zapytania, na które jeszcze nie odpowiedzieliśmy, i dla każdego z nich stosujemy wyszukiwanie binarne jak w rozwiązaniu wzorcowym (czas \(O(n \log \log X)\)). Różnica między tym rozwiązaniem a poprzednim jest taka, że nie musimy trzymać w zbiorze \(A\) indeksów \((p, q)\) elementów.

  Ostateczna złożoność to \(O(\log^2 X (\log \log X + \log n) + n(\log \log X + \log n))\).

• Można też obliczać wyniki dla każdego \(x\) osobno. Wyznaczamy zbiór \(A\); sprawdzamy, czy \(x \in A\); jeśli nie, obliczamy wynik na podstawie \(\operatorname{rank}(x, A)\). Złożoność czasowa: \(O(n \log^2 X)\).

Dygresja: dowód jednoznaczności.

W treści zadania podana została bez dowodu własność ciągu, że każda liczba występuje jako różnica dwóch elementów ciągu dokładnie raz. Dla kompletności opisu wypadałoby to tutaj udowodnić. Okazuje się, że po opracowaniu rozwiązania wzorcowego jest to już całkiem proste.

Definicja \(a_n\) dla \(n\) parzystego gwarantuje, że każda różnica wystąpi w ciągu \(\mathbf{a}\). Wystarczy zatem pokazać, że każda różnica występuje w ciągu co najwyżej raz.

Rozważmy jakieś \(x\) i oznaczmy \(k = \operatorname{ind}(x)\). Wiemy już, że jeśli \(x = a_p - a_q\) dla \(p > k\), to jest tylko jeden możliwy wybór indeksów \((p, q)\), określony wzorem z rozwiązania wzorcowego. Załóżmy zatem, że \(p \le k\). Jeśli \(p \le k - 2\), to \(a_p < x\) i nie może zachodzić \(x = a_p - a_q\). Jeśli \(a_{k-1} \le x\), to może być tylko jedna para indeksów \((p, q)\), gdzie \(p = k\). Dwie pary indeksów mogłyby tylko istnieć, jeśli \(x < a_{k-1}\): potencjalnie pary \((k-1, q_1)\) i \((k, q_2)\). To by oznaczało, że \(a_k - a_{q_2} = a_{k-1} - a_{q_1}\), czyli \(a_k = a_{k-1} + (a_{q_2} - a_{q_1})\). Stanowi to jednak sprzeczność z definicją \(a_k\) dla \(k\) parzystego: \(a_k = a_{k-1} + r_{k-1}\), gdzie \(r_{k-1}\) nie jest różnicą żadnych dwóch wcześniejszych elementów ciągu \(\mathbf{a}\).