Omówienie zadania Permutacje (III etap XXXI OI)

Rozwiązanie brutalne

Zaczniemy od najbardziej brutalnego rozwiązania. Możemy przeiterować się po wszystkich możliwych permutacjach \(p\) i osobno sprawdzić, czy dana permutacja jest szukaną ukrytą permutacją.

Aby sprawdzić konkretną permutację \(p\), na początku przypiszmy \(q = p^{-1}\) - tak zwaną permutację odwrotną, w której \(q(i) = j\) jeśli \(p(j) = i\). Wtedy \(r\) jest permutacją identycznościową wtedy i tylko wtedy, gdy nasze \(p\) jest rzeczywiście ukrytą permutacją. Aby sprawdzić, czy \(r\) jest identycznością, pytamy o każdą parę \((a, b)\) i sprawdzamy, czy dla każdego \(a \neq b\) dostajemy odpowiedź \(\texttt{false}\).

Takie rozwiązanie zadaje \(O(n! \cdot n^2)\) zapytań i przechodzi pierwsze podzadanie.

Trochę mądrzej

Aby uzyskać lepsze rozwiązanie możemy zauważyć, że jeśli liczba \(i\) przejdzie na siebie samą w \(pq\), czyli \(i = q(p(i))\), to \(q^{-1}(i) = p(i)\). Możemy sprawdzić, czy tak się stało, pytając o każdą parę \((i, a)\) dla \(a \neq i\). Jeśli otrzymamy za każdym razem \(\texttt{false}\), to zawsze \(i\) przeszło na samo siebie (utworzyło cykl długości \(1\)).

Mając takie "narzędzie", wystarczy dla każdej pary \((i, j)\) sprawdzić, czy \(p(i) = j\). To rozwiązanie zadaje \(O(n^3)\) zapytań i przechodzi drugie podzadanie.

Przydatne przekształcenie

W tym zadaniu jesteśmy proszeni o odgadnięcie jakiejś permutacji \(p\). Możemy lekko uprościć sobie to zadanie. Powiedzmy, że znamy jakąś dobraną przez nas permutację \(g\) i poznamy także permutację \(pg\). Wtedy można obliczyć odpowiedź poprzez \((pg)g^{-1} = p\). Takie spojrzenie jest pomocne, ponieważ permutacja \(pg\) może być prostsza do odgadnięcia. To my dobieramy \(g\) i dzięki temu \(pg\) może mieć jakieś przydatne dla nas własności.

Jeden cykl

Zgodnie z powyższą myślą postaramy się uzyskać permutację \(g\) taką, aby \(pg\) było jedym cyklem. Zaczniemy od liczby \(0\) i będziemy po kolei dodawać kolejne liczby do cyklu, na którym jest \(0\). Więc startujemy z permutacją \(g\), która jest identycznością. Teraz, gdy chcemy aby liczba \(i > 0\) była na cyklu z \(0\), to sprawdzamy, czy w naszym aktualnym \(g\) są razem na cyklu. Jeśli nie są, to podmieniamy \(g\) na \(g'\), w którym \(g'(0) = g(i)\) oraz \(g'(i) = g(0)\) (reszta jak w \(g\)). Wtedy cykle, na których są liczby \(0\) oraz \(i\), złączą się.

Uzyskanie takiej permutacji \(g\) kosztuje nas \(n - 1\) zapytań.

Sortowanie

W tym momencie załóżmy już, że \(h = pg\) jest jednym cyklem. Teraz chcemy poznać kolejne liczby na tym cyklu zaczynając od \(0\) - czyli wartości \(0, h(0), h(h(0)), \dots, h^{-1}(0)\).

Jak to zrobić mając tylko operację z treści zadania? Możemy spróbować zrozumieć jak porównać dwa elementy - pozwala to na "posortowanie" ciągu \(1, 2, \ldots, n - 1\) według kolejności występowania tych elementów w \(h\) - stąd możemy już odtworzyć permutację \(h\). Żeby stwierdzić dla danych dwóch wartości \(a\), \(b\) która z nich występuje wcześniej w tym ciągu, konstruujemy permutację, która rozcina nasz cykl na dwa, gdzie pierwszy będzie zawierał kolejno \(0, h(0), h(h(0)), ..., a\), a drugi pozostałe wartości. Takie zadanie spełnia permutacja \(h'\), w której \(h'(a) = 0\) oraz \(h'(h^{-1}(0)) = h(a)\) (reszta jak w \(h\)). Jeśli w tym zapytaniu \(0\) będzie na tym samym cyklu co \(b\), to \(b\) jest przed \(a\), a w przeciwnym przypadku jest po.

Rozwiązanie wzorcowe

Rozwiązanie wzorcowe sortuje liczby \(1, 2, \dots, n - 1\) według kolejności ich występowania w ciągu \(0, h(0), h(h(0)), \dots, h^{-1}(0)\), a następnie odzyskuje z tego permutację \(h\). Mając \(h = pg\) oraz \(g\) wyliczamy \(p\) i zwracamy odpowiedź. Aby uzyskać maksymalną liczbę punktów należy użyć algorytmu sortującego, który zada co najwyżej \(n \log_2 n\) zapytań. Algorytm zastosowany w \(\texttt{std::sort}\) może czasami zadać więcej zapytań i nie uzyskać kompletu punktów. Zalecamy użycie na przykład algorytmu merge-sort.

To rozwiązanie zadaje co najwyżej \(n + n \log_2 n\) zapytań.