Omówienie zadania Powtórzenia (eliminacje do IOI 2020, dzień 0)

Pierwsze trzy podzadania

Najprostsze podzadania można rozwiązać, rozpatrując każde zapytanie zupełnie osobno. Mamy wtedy \(q\) łańcuchów, każdy długości maksymalnie \(n\), i musimy w każdym z nich zliczyć różne powtórzenia, czyli spójne podciągi złożone z co najmniej dwóch kopii tej samej liczby.

W tej sytuacji wystarczy podzielić łańcuch na maksymalne powtórzenia, z każdego maksymalnego powtórzenia wygenerować wszystkie różne powtórzenia w nim zawarte, a następnie pogrupować wygenerowane powtórzenia, np. za pomocą sortowania. Maksymalne powtórzenie długości \(k\) generuje \(k-1\) różnych powtórzeń. Jeśli zatem kolejne maksymalne powtórzenia w łańcuchu mają długości \(k_1,\ldots,k_p\), to łącznie generują one \[(k_1-1)+\dots+(k_p-1)=k_1+\dots+k_p-p=n-p < n\] różnych powtórzeń. Jeśli kolejne powtórzenia będziemy przechowywać w najprostszy możliwy sposób, jako łańcuchy, to będą miały łączną długość \(O(n^2)\), a posortowanie ich zajmie czas \(O(n^2 \log n)\). Jeśli zaś powtórzenia będziemy reprezentować w postaci par (długość, powtarzająca się liczba), to porównywać je będzie można w czasie stałym, więc sortowanie ich zajmie czas \(O(n \log n)\). Wreszcie zamiast sortowania można użyć tablicy haszującej, która daje oczekiwany czas grupowania powtórzeń \(O(n)\). Po wszystkich \(q\) zapytaniach otrzymujemy łączną złożoność \(O(qn^2 \log n)\) albo \(O(qn \log n)\), albo \(O(qn)\); takie rozwiązania pozwalały zaliczyć, odpowiednio, pierwsze podzadanie, pierwsze dwa podzadania i pierwsze trzy podzadania.

Czwarte podzadanie

W tym podzadaniu mamy gwarancję, że wszystkie fragmenty łańcucha, o które będą pytania, mają tę samą długość. Długość tę poznajemy w momencie otrzymania pierwszego pytania; oznaczmy ją przez \(\ell\). W tym momencie wyznaczymy od razu odpowiedzi na wszystkie pytania o fragmenty długości \(\ell\) i zapamiętamy je. Następnie na wszystkie kolejne pytania będziemy już odpowiadali w czasie stałym.

Żądane wyniki będziemy wyznaczać dla fragmentów od lewej do prawej. Najpierw w prefiksie ciągu o długości \(\ell\) wyznaczymy wszystkie powtórzenia; będziemy je przechowywali za pomocą par (długość, powtarzająca się liczba) w strukturze danych std::unordered_map w C++ zliczającej wystąpienia danej pary. Początkowo strukturę danych wyznaczamy w czasie \(O(\ell)\) (patrz poprzednia sekcja). Gdy przechodzimy do kolejnego fragmentu, tracimy co najwyżej jedno powtórzenie na prefiksie i zyskujemy co najwyżej jedno wystąpienie na sufiksie. Tak więc możemy zmodyfikować zawartość struktury danych w oczekiwanym czasie stałym. Mając naszą strukturę danych, możemy w czasie stałym wyznaczyć liczbę różnych powtórzeń w aktualnym fragmencie. Łącznie oczekiwana złożoność czasowa rozwiązania to \(O(n+q)\). Można by też użyć struktury danych std::map, co zwiększa złożoność do \(O(n\log n+q)\) (ale za to pesymistycznie); oba rozwiązania pozwalały zaliczyć czwarte podzadanie.

Piąte podzadanie

W tym podzadaniu w łańcuchu występują tylko dwie różne liczby. Dla uproszczenia opisu przyjmijmy, że są to liczby 0 i 1.

Podzielmy nasz łańcuch na maksymalne fragmenty stałe \(B_1,B_2,\ldots,B_t\), które nazwiemy blokami. Bloki składają się na przemian z liczb 0 i 1 (lub odwrotnie). Dowolny fragment łańcucha albo zawiera się w jednym bloku \(B_i\), albo składa się z sufiksu pewnego bloku \(B_i\), pewnej liczby kolejnych całych bloków \(B_{i+1},\ldots,B_{j-1}\) i prefiksu bloku \(B_j\).

Zauważmy, że aby odpowiedzieć na pytanie o fragment, wystarczy wyznaczyć w tym fragmencie najdłuższe powtórzenie złożone z liczb 0 i najdłuższe złożone z liczb 1. Niepełne bloki we fragmencie (co najwyżej dwa) potraktujemy osobno. Nad nieparzystymi blokami \(B_1,B_3,B_5,\ldots\) stworzymy strukturę danych do odpowiadania na zapytania o najdłuższy blok we fragmencie; podobnie dla bloków \(B_2,B_4,B_6,\ldots\). Taką strukturą danych może być chociażby drzewo przedziałowe, o czasie konstrukcji \(O(n)\) i zapytania \(O(\log n)\). Dzięki drzewu przedziałowemu możemy wyznaczyć w danym fragmencie w najdłuższy spójny podciąg złożony z zer i najdłuższy fragment z jedynek w czasie \(O(\log n)\). Otrzymujemy rozwiązanie działające w tym przypadku w czasie \(O(n+q \log n)\).

Warto zauważyć, że to rozwiązanie niestety nie uogólnia się zbyt dobrze dla łańcuchów, w których może występować wiele różnych liczb.

Redukcja do problemu zliczania różnych liczb we fragmentach

Okazuje się, że problem z zadania możemy zredukować w czasie liniowym do następującego problemu.

Problem. Dany jest ciąg liczb \(c=(c_1,\ldots,c_N)\). Otrzymujemy (on-line) \(q\) pytań. Każde pytanie jest zadane przez dwa indeksy \(a,b \in \{1,\ldots,N\}\) takie że \(a \le b\). W odpowiedzi na takie pytanie mamy wyznaczyć liczbę różnych liczb w zbiorze \(\{c_a,\ldots,c_b\}\).

Opiszemy najpierw redukcję do problemu, w którym ciąg \(c\) składa się z par liczb. Dla każdego kolejnego maksymalnego powtórzenia w danym łańcuchu, jeśli powtórzenie składa się z \(k\) kopii liczby \(x\), to w ciągu \(c\) umieszczamy gadżet zawierający kolejno pary \[(x,2),(x,3),\ldots,(x,k),(x,k-1),\ldots,(x,2).\] Otrzymany ciąg \(c\) ma długość \(N \le 2n\).

Gdy otrzymujemy pytanie o liczbę różnych powtórzeń we fragmencie łańcucha, to znajdujemy pierwsze i ostatnie maksymalne powtórzenie w tym fragmencie. Jeśli nie ma takich powtórzeń, wynikiem dla fragmentu łańcucha jest 0. Jeśli jest tylko jedno maksymalne powtórzenie we fragmencie, wynikiem jest jego długość pomniejszona o 1. W przeciwnym przypadku, niech pierwsze maksymalne powtórzenie we fragmencie składa się z \(k\) kopii liczby \(x\) i będzie sufiksem maksymalnego powtórzenia w całym łańcuchu złożonego z \(k' \ge k\) kopii liczby \(x\). Wówczas fragment ciągu \(c\) zacznie się na parze o numerze \(k-1\) od końca w gadżecie odpowiadającym maksymalnemu fragmentowi \((x,k')\). Podobnie niech ostatnie maksymalne powtórzenie we fragmencie składa się z \(h\) kopii liczby \(y\) i będzie prefiksem maksymalnego powtórzenia w łańcuchu złożonego z \(h' \ge h\) kopii liczby \(y\). Wówczas fragment ciągu \(c\) zakończy się na parze o numerze \(k-1\) od początku w gadżecie odpowiadającym maksymalnemu fragmentowi \((y,h')\).

Przykładowo, dla łańcucha \[aaaabbbaaa\] tworzymy ciąg \(c\) równy \[(a,2),(a,3),(a,4),(a,3),(a,2),(b,2),(b,3),(b,2),(a,2),(a,3),(a,2).\] Pytanie o liczbę różnych powtórzeń we fragmencie łańcucha \[a\underline{aaabbbaa}a\] redukuje się do pytania o liczbę różnych par w następującym fragmencie ciągu \(c\): \[(a,2),(a,3),(a,4),\underline{(a,3),(a,2),(b,2),(b,3),(b,2),(a,2)},(a,3),(a,2).\]

Aby redukcja w przypadku zapytań działała w czasie stałym, musimy w łańcuchu zapamiętać dla każdej pozycji pozycję najbliższego maksymalnego powtórzenia w lewo i w prawo od niej. Takie wartości możemy łatwo obliczyć na początku w czasie \(O(n)\). Wreszcie aby otrzymać ciąg liczb zamiast ciągu par, wystarczy parę postaci \((x,k)\) zamienić na liczbę \(x(n+1)+k\).

Nasz problem pomocniczy jest znany w środowisku konkursów programistycznych, ale jakoś tak wyszło, że nigdy wcześniej nie pojawił się na zawodach Olimpiady Informatycznej. Z tego względu opiszemy tutaj jego rozwiązanie. Będzie ono oparte na tzw. trwałych drzewach przedziałowych (ang. persistent segment tree).

Szóste i siódme podzadanie

Podpowiedź do rozwiązania stanowią podzadania, w których można założyć, że początki fragmentów łańcucha w zapytaniach są niemalejące. Zgodnie z redukcją, oznacza to, że początki fragmentów w ciągu \(c\) są niemalejące. Dla ustalonego początku fragmentu \(a\), dla każdej wartości w sufiksie ciągu \(c_a,\ldots,c_N\) interesuje nas tylko jej pierwsze (lewe) wystąpienie. Stworzymy zatem drzewo przedziałowe (na razie zwykłe), wariant "drzewa licznikowego", w którym będziemy przechowywać te indeksy w ciągu \(c_a,\ldots,c_N\), które zawierają takie pierwsze wystąpienia poszczególnych wartości. Gdy już będziemy mieli takie drzewo, zapytanie o liczbę różnych wartości we fragmencie \(c_a,\ldots,c_b\) zredukuje się do zliczenia indeksów umieszczonych w drzewie przedziałowym zawartych w przedziale \([a,b]\).

Opiszemy teraz, w jaki sposób możemy skonstruować takie drzewo przedziałowe dla początkowej wartości \(a=1\) oraz jak je aktualizować przy zwiększaniu wartości \(a\). Najpierw dla każdego indeksu \(i \in \{1,\ldots,N\}\), jako \(\mathit{next}[i]\) zapamiętamy najmniejszy indeks \(j>i\) taki że \(a_j=a_i\); jeśli taki indeks nie istnieje, możemy ustawić \(\mathit{next}[i]=N+1\). Tablicę \(\mathit{next}\) możemy wyznaczyć, idąc od prawej do lewej w ciągu i przechowując w strukturze danych std::map dla każdej napotkanej wartości w ciągu \(a\) najmniejszy indeks, pod którym ona dotychczas wystąpiła. W ten sposób tablicę \(\mathit{next}\) wyznaczamy w czasie \(O(N \log N)\). Do drzewa przedziałowego dla \(a=1\) najpierw wstawiamy wszystkie indeksy \(\{1,\ldots,N\}\). Następnie dla każdego \(i\) takiego że \(\mathit{next}[i] \ne N+1\), z drzewa usuwamy indeks \(\mathit{next}[i]\). W ten sposób początkowe drzewo przedziałowe konstruujemy w czasie \(O(N \log N)\).

Przechodząc z indeksu \(a\) do indeksu \(a+1\), wystarczy usunąć z drzewa przedziałowego indeks \(a\) oraz wstawić indeks \(\mathit{next}[a]\), o ile nie jest on równy \(N+1\). W ten sposób aktualizacja przebiega w czasie \(O(\log N)\). Łącznie wszystkie drzewa przedziałowe wyznaczamy po kolei w czasie \(O(N \log N)\). Na pytania odpowiadamy dokładnie wtedy, gdy mamy w ręku odpowiednie drzewo przedziałowe. Wtedy odpowiedź na pytanie wymaga czasu \(O(\log N)\). Łączna złożoność rozwiązania podzadań 6 i 7 to zatem \(O((n+q) \log n)\). Warto zauważyć, że jest to zarazem rozwiązanie całego problemu w sytuacji, gdy pytania mamy podane off-line, czyli możemy na nie odpowiadać w wybranej przez nas kolejności.

Rozwiązanie wzorcowe

Trwałe struktury danych zostały stworzone po to, by dawać dostęp do całej historii struktury danych, która ulega aktualizacjom. Trwałe drzewo przedziałowe jest reprezentowane jako drzewo na wskaźnikach (w przeciwieństwie do statycznego drzewa przedziałowego, które można reprezentować w tablicy). Gdy drzewo przedziałowe jest aktualizowane, tworzymy kopie wszystkich węzłów, w których poddrzewie coś się zmieniło. Te węzły to taki diff między nową strukturą a starą. Węzły te napotykamy przy okazji w trakcie wykonywania aktualizacji drzewa. Kopia węzła łączy się wskaźnikami z kopiami dzieci, jeśli te zostały stworzone, a jeśli nie, to z dziećmi z niezaktualizowanego drzewa. Zawsze tworzymy kopię korzenia; trzymamy tablicę wszystkich kolejno stworzonych korzeni, dzięki czemu, odnosząc się do odpowiedniego korzenia, mamy dostęp do każdej kolejnej wersji struktury danych. Musimy wtedy implementować operacje na drzewie przedziałowym w kolejności od korzenia do liści, np. rekurencyjnie.

Złożoność czasowa trwałej wersji drzew przedziałowych jest taka sama jak dotychczas. Rośnie tylko złożoność pamięciowa, gdyż przy każdej aktualizacji drzewa przedziałowego tworzymy kopie \(O(\log N)\) węzłów. Łączna złożoność czasowa i pamięciowa wszystkich aktualizacji to zatem \(O(N \log N)\). Gdy mamy dostęp do całej historii, odpowiedzi na kolejne zapytania uzyskujemy w czasie \(O(\log N)\). Otrzymujemy pełne rozwiązanie zadania w czasie \(O((n+q) \log n)\).

Ósme podzadanie?

Podzadanie z nieco niższymi limitami zostało zaproponowane z myślą o rozwiązaniach o złożoności \(O((n+q) \sqrt{n})\), które zamiast drzew przedziałowych wykorzystują jakąś dekompozycję ciągu na \(O(\sqrt{N})\) fragmentów o długości \(O(\sqrt{N})\). Tego typu rozwiązania również muszą być wyposażone w funkcję trwałości, tak więc nie wydaje się, żeby były one jakoś istotnie prostsze od rozwiązania opartego na drzewie przedziałowym.