Omówienie zadania Przesunięcie cykliczne (II etap XXVI OI)

Podzadanie 1

Przesuwamy cyklicznie ciąg o \(k=1\), zapamiętując jego kolejne elementy. W momencie powtórzenia się elementu, wiemy, że wczytaliśmy cały ciąg. Ponieważ \(n\leq 10\), więc zadamy co najwyżej 11 pytań.

Podzadanie 2

Na początek \(s\) razy przesuwamy cyklicznie ciąg o \(k=1\), zapamiętując jego \(s\) pierwszych elementów \(b_1,b_2,\ldots,b_s\). Następnie przesuwamy o \(k=s\), aż w końcu znowu natrafimy na jakiś element \(b_i\), który widzieliśmy wcześniej. Jeśli zrobiliśmy \(\ell\) długich przesunięć, to musi być spełnione \(s + \ell s = n + i\), co pozwala nam wyznaczyć długość ciągu.

Jeśli przyjmiemy \(s = \lceil \sqrt{2000} \rceil = 45\), to zadamy co najwyżej \(s + \lceil n/s \rceil \leq 90\) pytań dla \(n \leq 2000\).

Podzadanie 3

Wygodniej nam będzie numerować elementy ciągu od 0. Ponadto, za ciągiem ustawmy jego kopię, czyli przyjmijmy, że \(a_{n+i} = a_i\) dla \(0\leq i< n\).

Najpierw raz przesuwamy o \(k=0\), potem dwa razy o \(k=1\), a potem o coraz większe potęgi dwójki \(k=2,4,8,\ldots\) Dzięki temu dostajemy elementy \(a_0,a_1,a_2,a_4,a_8,a_{16},\ldots\)

Dopóki liczby, które przesyła nam biblioteka są coraz większe, oznacza to, że jesteśmy ciągle w naszym ciągu. Jeżeli kiedykolwiek zdarzy nam się tak, że \(a_{2^k} = a_0\), to znaczy, że znaleźliśmy długość ciągu i jest nią właśnie \(2^k\). W momencie, kiedy okaże się, że \(a_{2^k} < a_{2^{k-1}}\), to znaczy, że przekroczyliśmy koniec ciągu i znajdujemy się teraz w jego kopii. Tak więc możemy powiedzieć, że długość naszego ciągu na pewno znajduje się gdzieś w otwartym przedziale \((2^{k - 1}\), \(2^k)\).

Teraz chcielibyśmy kontynuować już zwykłym wyszukiwaniem binarnym, w którym mamy połowienie przedziału. Więc następnym kandydatem na długość naszego ciągu byłby środek tego przedziału, czyli \(x = \frac{2^{k - 1} + 2^k}{2}\). Chcielibyśmy teraz napisać taką funkcję, która pozwoli nam odpowiadać na zapytanie dla ustalonej wartości \(x\), który z trzech warunków zachodzi: \(x<n\), czy \(x=n\), czy \(x>n\)? Problematyczne jest to, że ta funkcja musi obsługiwać przypadek, kiedy wskaźnik znajduje się w dowolnej części ciągu.

Możemy podejrzeć aktualny element ciągu \(a_p\). Skoro chcemy przetestować, czy \(x < n\), to moglibyśmy sprawdzić element, który stoi w odległości \(x\) dalej, czyli \(a_{p+x}\). Jednak nawet gdy dostaniemy informację, że \(a_{p+x} > a_p\), to nie wiemy, czy oba elementy są ciągle w ciągu, czy też \(a_{p+x}\) znajduje się już w kopii.

Ale możemy uzyskać dużo więcej informacji, rozbijając ten skok o \(x\) na dwa skoki o \(\frac{x}{2}\), czyli odpytując się o elementy \(A = a_p\), \(B = a_{p+\frac x 2}\) i \(C = a_{p+x}\).

Jeśli wszystkie trzy elementy są w ciągu, to jest spełnione \(A < B < C\).

Jeśli natomiast \(C\) znajduje się w kopii ciągu, to mamy albo \(B > C\) (jeśli \(B\) jest w ciągu) lub \(A > B\) (jeśli \(B\) jest w kopii). W obu sytuacjach mamy jedną inwersję wśród elementów \(A,B,C\). Okazuje się, że właśnie ta liczba inwersji jest kluczową informacją, która pozwoli nam rozróżnić przypadki \(x < n\) oraz \(x > n\).

Nie będziemy rozpisywać wszystkich sytuacji, które mogą się zdarzyć z ustawieniem tych trzech elementów. Ale po takim rozpisaniu okazuje się, że kluczowa jest parzystość liczby inwersji dla elementów \(A,B,C\): jeżeli ta liczba inwersji jest parzysta, wtedy mamy do czynienia z przypadkiem \(x < n\), a jeżeli liczba jest nieparzysta, wtedy mamy do czynienia z przypadkiem \(x > n\). No oczywiście został jeszcze przypadek \(x = n\), ale w tym przypadku mamy po prostu sytuację, w której \(A = C\), co można sprawdzić na samym początku.

Tutaj jeszcze uwaga techniczna do tego wyszukiwania binarnego: korzystaliśmy z założenia, że \(x < 2n\), ale jest to spełnione, jeżeli zaczynamy od przedziału \((2^{k - 1}, 2^k)\). Drugą uwagą techniczną jest to, że żebyśmy mogli dzielić ten przedział na połowę, to \(x\) za każdym razem musi być liczbą parzystą, ale to również jest spełnione, ponieważ długość przedziału, który dzielimy, jest potęgą dwójki, natomiast ostatnia liczba z tego przedziału jest również zawsze parzysta.

Na końcu, kiedy dojdziemy już do przedziału o długości 2, obustronnie otwartego, zostanie w nim tylko jeden kandydat \(x\) na odpowiedź, no i to właśnie będzie rozwiązanie zadania.

Pełne rozwiązanie

W pierwszej fazie naszego algorytmu, w której skakaliśmy potęgami dwójki, żeby znaleźć ograniczenie górne, korzystaliśmy z założenia, że znajdujemy się na początku rosnącego ciągu. Jeżeli nie chcemy korzystać z tego założenia, to również do tych skoków o potęgi dwójki możemy wykorzystać naszą funkcję porównującą.

Pytanie, ile ostatecznie wykonamy porównań? Najpierw będziemy musieli logarytmicznie wiele razy wywołać funkcję porównującą skacząc potęgami dwójki, a następnie logarytmicznie wiele razy wywołać zejście rekurencyjne. W każdym wywołaniu naszej funkcji porównującej musimy dwa razy skoczyć wskaźnikiem o \(\frac{x}{2}\). Czyli ostatecznie wykonamy około \(4 \log n\) porównań, czyli spokojnie zmieścimy się w limicie 100 porównań.