Omówienie zadania Ornitolog (III etap XXVI OI)

Podzadanie 1

Najprostsze rozwiązanie będzie polegało na bezpośredniej symulacji procesu opisanego w treści zadania. Możemy stworzyć listę jednokierunkową o długości \(n + m\), która będzie zawierać numery kolejnych ptaków. Będziemy poruszać się po tej liście wskaźnikiem, pokazującym, który ptak ma zaśpiewać kolejny dźwięk. (Ponieważ na koniec każdej pieśni będziemy chcieli usunąć z listy ptaka, który zaśpiewał ostatni dźwięk, więc przyda nam się również wskaźnik na ptaka, który poprzedza naszego aktualnego ptaka na liście.)

Jeżeli chcemy teraz zasymulować śpiewanie pieśni długości \(a\), to najpierw \(a - 1\) razy przesuwamy oba wskaźniki do przodu listy. Teraz pierwszy wskaźnik wskazuje na ptaka śpiewającego ostatni dźwięk. Przesuwamy ten wskaźnik jeszcze raz do przodu, więc teraz wskazuje na ptaka, który zacznie kolejną pieśń. Natomiast wskaźnik poprzedni używamy do tego, żeby usunąć z listy ptaka, który zaśpiewał ostatni dźwięk. Po uaktualnieniu listy znowu mamy zachowany niezmiennik, że pierwszy wskaźnik wskazuje na ptaka, który ma zacząć nową pieśń, natomiast drugi wskaźnik wskazuje na ptaka poprzedzającego.

Każdą pieśń jesteśmy w stanie przesymulować w czasie proporcjonalnym do jej długości, a musimy to zrobić \(k\) razy. Wobec tego złożoność czasowa tego rozwiązania, to jest \(O(n + m)\) na przygotowanie całej listy, plus \(k(a + b)\), to jest \(k\)-krotna symulacja jednej pieśni. Ponieważ wartości \(k\), \(a\) i \(b\) są ograniczone przez \(n + m\), wobec tego tą złożoność możemy również zapisać jako \(O((n + m)^2)\).

Podzadanie 2

Lista całkiem dobrze sprawdzała się przy usuwaniu ptaków, które robiliśmy w czasie \(O(1)\), ale symulacja pieśni już wymagała czasu \(O(a+b)\). Chcielibyśmy zatem stworzyć strukturę, która umożliwia szybkie usuwanie elementów, ale także odpowiedź na pytanie dla danego elementu, jaki jest \(k\)-ty w kolejności nieusunięty element, który występuje za nim. Taką strukturą danych może być drzewo licznikowe, dokładnie opisane w książce Przygody Bajtazara. Zarówno usuwanie elementów, jak i odpowiedź na pytanie o \(k\)-ty kolejny element, będziemy w stanie robić w czasie logarytmicznym od liczby elementów w drzewie.

Całkowita złożoność czasowa rozwiązania z drzewem licznikowym to będzie \(O(n + m)\) na konstrukcję drzewa plus \(O(k \log(n + m))\) na zapytania.

Rzeczą, na którą musimy zwrócić uwagę przy implementacji tego drzewa, to mała ilość pamięci dostępna w zadaniu, mamy bowiem tylko 8 MB. Warto zatem dokładnie obliczyć, ile pamięci będzie zajmować drzewo.

W przypadku ograniczenia \(n + m \leq 250\,000\) wystarczy nam \(2^{18}\) liści, więc wszystkich węzłów w tym drzewie będzie \(2^{19}\). Każdy węzeł będzie jedną liczbą \(32\)-bitową, zatem w sumie na drzewo będziemy potrzebowali \(2^{19} \cdot 4 = 2^{21}\) bajtów, czyli 2 MB. To spokojnie zmieści nam się w dostępnej pamięci.

Podzadanie 3

Gdybyśmy tą samą metodą próbowali rozwiązać podzadanie 3, to mielibyśmy kłopot, ponieważ tym razem wielkość \(n + m\) jest już \(20\) razy większa niż w poprzednim podzadaniu, tak więc drzewo licznikowe miałoby wielkość 40 MB i nie zmieściłoby się w limicie dostępnej pamięci.

Możemy z tym problemem poradzić sobie stosując rozwiązanie hybrydowe. Dalej będziemy mieli drzewo zawierające \(2^{18}\) liści, z tym że teraz każdy z liści będzie odpowiadał przedziałowi złożonemu z \(20\) ptaków. Dodatkowo informacje o konkretnych ptakach, które są w tym przedziale, będziemy trzymali na maskach bitowych o długości \(20\).

Operację usuwania elementu z maski bitowej możemy wykonać w czasie stałym, korzystając z operacji bitowych, a ponieważ maski są krótkie, więc operację wyszukiwania zapalonego bitu również możemy potraktować jako operację w czasie stałym. Będziemy potrzebowali dodatkowego megabajta na przechowywanie masek bitowych, więc w sumie złożoność pamięciowa tego rozwiązania wyniesie 3 MB.

Podzadanie 4

Kluczowym pomysłem w rozwiązaniu jest ,,relatywne” numerowanie ptaków. Każdy ptak oprócz oryginalnego numeru będzie miał jeszcze numer relatywny, czyli jego pozycję od początku cyklu wśród ptaków, które pozostały (innymi słowy, dziury pomiędzy ptakami są ignorowane, a relatywna numeracja pozostaje spójna).

Chyba dość niespodziewanie rozwiązanie opieramy na wyszukiwaniu binarnym po wyniku. Chcemy umieć odpowiadać na pytanie ,,czy ptak, który będzie usuwany w \(k\)-tym kroku ma oryginalny numer mniejszy niż ustalony limit \(\ell\)”. Dzięki temu wyszukiwaniem binarnym wyznaczymy maksymalną wartość \(\ell\), dla której odpowiedź jest negatywna i to będzie oryginalny numer ptaka usuwanego w \(k\)-tym kroku.

Wykonujemy symulację, w której wystarczy trzymać jedynie kilka zmiennych:

• relatywny numer ptaka, który ma właśnie zostać usunięty,

• pozostała liczba ptaków,

• pozostała liczba samców,

• pozostała liczba ptaków o oryginalnym numerze mniejszym niż \(\ell\).

W każdym kroku relatywna pozycja pozwala określić czy usuwamy samca czy samicę (a więc jasne jest jaki jest następny skok) oraz czy usuwany ptak stał na kółku przed pozycją \(\ell\), czy nie. A zatem krok (aktualizację relatywnej pozycji, pozostałej liczby ptaków, pozostałej liczby samców oraz ptaków na lewo od \(\ell\)) możemy zrobić w czasie stałym.

Tak więc odpowiedź na pytanie wykonamy w czasie \(O(k)\), zatem cały algorytm działa w czasie \(O(k \log (n+m))\) i pamięci stałej.

Podzadanie 5

Chcemy szybciej wykonywać symulację: w tym celu będziemy robić wiele ruchów na raz. Ruchy kombinujemy do jednego dużego ,,susa” tak długo jak mają ten sam typ: tzn. płeć usuwanego ptaka oraz bycie na lewo od ptaka \(\ell\).

Na początek załóżmy dla uproszczenia, że \(a=b\). Jeśli cykl jest długości co najwyżej \(a\), w jednym susie usuniemy dokładnie jednego ptaka. Jeśli natomiast jest większej długości, to w co najwyżej trzech susach usuniemy co najmniej co \(a\)-tego ptaka: po dwóch susach obejdziemy cały cykl (i wyrzucimy co najmniej \(\left\lfloor \frac{n+m}{a} \right\rfloor\) ptaków), w trzecim susie wyrzucimy jeszcze co najmniej jednego ptaka; liczba usuniętych ptaków będzie więc równa co najmniej \(\frac{n+m}{a}\). Podobnie, w jednym susie nie usuniemy więcej niż \(\left\lceil\frac{n+m}{a}\right\rceil < \frac{2(n+m)}{a}\) ptaków.

Wobec tego, w stałej liczbie kroków zawsze usuwamy \(\Theta\left(\frac{n+m}{a}\right)\) ptaków, tj. dzielimy ich liczbę przez \(\frac{a}{a-1} = 1 + \frac{1}{a - 1}\). Zastanawiamy się, ile kroków potrzeba na pozbycie się wszystkich ptaków. Liczba susów potrzebnych na usunięcie ostatnich \(a\) ptaków wynosi \(a\); liczba susów potrzebnych na usunięcie wszystkich pozostałych jest rzędu \(\log_{1 + \frac{1}{a - 1}} n+m = \frac{\log (n+m)}{\log\left(1 + \frac1{a-1}\right)} = \frac{\log (n+m)}{\Theta\left(\frac{1}{a - 1}\right)} = \Theta(a \log (n+m))\).

Pełna symulacja zajmuje zatem czas \(O((a + b) \log (n + m))\). Dochodzi do tego kolejny logarytm z wyszukiwania binarnego, więc ostateczna złożoność czasowa to \(O((a + b) \log^2 (n + m))\).