Informatyczny kącik olimpijski

Coś się popsuło

W noworocznym kąciku omówimy zadanie Wykrywanie wrednej usterki pochodzące z zeszłorocznej Międzynarodowej Olimpiady Informatycznej, która odbyła się w Kazaniu (Rosja). Autorzy zadania oczekują od nas, że pomożemy zdiagnozować usterkę, która wkradła się do bazy danych zaimplementowaną przez niefrasobliwego inżyniera Ilszata.

Baza danych inż. Ilszata miała działać bardzo prosto. Zaprojektowane były tylko dwie operacje. Pierwsza operacja add(x) miała za zadanie dodanie do bazy danych nowego elementu x, o którym zakładamy, że jest zawsze ciągiem $|n$ bitów (przy czym dodatkowo możemy przyjąć, że $|n$ jest potęgą dwójki). Druga operacja check(x) powinna sprawdzać, czy x znajduje się w bazie, czy też nie.

Jako się rzekło, nie wszystko poszło według z góry ustalonego planu.

Okazało się, że operacja check(x) działa zupełnie poprawnie, natomiast operacja add(x) ma w sobie dziwnego buga (oszibkę?). Otóż, po wywołaniu add(x), zamiast ciągu x, do bazy danych dodawany jest ciąg $|π(x)$ dla pewnej (nieznanej nam) permutacji $π .$ Celem zadania jest właśnie ustalenie tej permutacji, poprzez wykonanie pewnego ciągu operacji na (początkowo pustej) bazie danych. Dodatkowym utrudnieniem jest założenie, że najpierw możemy wykonywać wyłącznie operacje typu add, a później wyłącznie operacje typu check. Innymi słowy: nie możemy przeplatać różnych typów operacji.

Zaprezentujemy dwa rozwiązania: pierwsze wymaga wykonania $O(n2)$ operacji, drugie (maksymalnie punktowane): $|O(nlog n)$ operacji.

W pierwszym podejściu zaczynamy od wykonania $n$ operacji add na następujących elementach (wykładnik oznacza krotność powtórzenia ostatniego symbolu): $10n−1,110n−2,1110n−3,...,1n.$ Następnie przechodzimy do fazy check-ów i zaczynamy od zapytania bazy danych o elementy: $|10n−1,010n−2,0010n−3,...,0n−11.$ Oczywiście dokładnie raz otrzymamy odpowiedź pozytywną, dzięki czemu ustalimy na co zamienił się element $|10n−1$ (jedyny z jedną jedynką), czyli poznamy $|π(1).$ Czas na kolejne pytania. Tym razem pytamy (kolejno) o wszystkie ciągi zawierające dwie jedynki, z których jedna jest zawsze na pozycji $π(1).$ Podobnie jak poprzednio dokładnie raz otrzymamy odpowiedź pozytywną, co pozwoli na ustalenie obrazu $110n−2,$ a ten określi wartość $π(2).$ Postępując dalej w ten sposób ustalamy w kolejnych krokach kolejne wartości $|π(i)$ dla $3 ⩽ i⩽ n.$ Każdy krok nie wymaga więcej niż $|O(n)$ zapytań, a więc łączny czas działania szacuje się z góry, zgodnie z obietnicą, przez $|n2.$

Rozwiązanie szybsze opiera się na zastosowaniu popularnej (znacznie dłużej niż teoria algorytmów) metody "dziel i zwyciężaj". Idea polega na ustaleniu obrazów pierwszej i drugiej połówki indeksów permutacji (czyli zbiorów $|{π(1),...,π (n/2)}$ oraz ${π (n/2+ 1),...,π(n)}$ ) a następnie przeanalizowanie (rekurencyjnie) każdej z połówek niezależnie od siebie. Aby ten pomysł zrealizować w ramach założeń zadania (nie możemy przeplatać add-ów i check-ów!) potrzeba pewnej zręczności.

Zacznijmy od definicji pewnej rodziny zbiorów. Niech $A = {10} 2$ oraz niech $k k 2k− 1 2k−2 k−1 k |A2k = Ak⋅1 ∪ 1 ⋅Ak∪ {10 ,010 ,...,0 10 }$ (patrz przykład na marginesie).

Właściwe rozwiązanie zaczyna się od wykonania operacji add na wszystkich elementach zbioru $An.$ Odtąd możemy już wykonywać wyłącznie operacje check. Zaczynamy od zapytania o wszystkie elementy postaci $|0m10n−m ,$ czyli te z jedną jedynką. Widzimy, że w zbiorze $A n$ znajduje się dokładnie $n/2$ elementów z jedną jedynką, a więc i tyle dostaniemy pozytywnych odpowiedzi, przy okazji ustalając na co "przechodzą" obie połówki permutacji $π.$ W tym miejscu chciałoby się po prostu napisać i dalej rekurencyjnie. Jest tak w istocie, ale trzeba mieć w głowie pewną subtelność. Otóż zbiór elementów, które włożyliśmy do bazy danych został już raz na zawsze ustalony. Trzeba się więc upewnić, czy w wywołaniach rekurencyjnych nie przeszkadzać nam będą jakieś inne elementy z innych faz oraz jak właściwie tłumaczyć zapytania z faz mniejszego rozmiaru na prawdziwe zapytania, gdzie mamy jedno $n$ ustalone z góry.

Zakończę sakramentalnym: da się, ale ze szczegółami pozostawiam Czytelnika samego.