Czy ktoś zechciałby podzielić się rozwiązaniem?

My możemy wstępnie opisać rozwiązanie wzorcowe.

Dla każdej pary indeksów (i, j), gdzie i!=j, chcemy policzyć jej orbitę, tzn. zbiór par pozycji, na które mogą się przemieścić elementy i oraz j. Wtedy każda para elementów (i, j) zawsze znajdzie się na losowej parze pozycji i łatwo będzie policzyć dla niej prawdopodobieństwo, że stworzy inwersję, zatem i finalny wynik.

Pojawia się tu rozwiązanie w O(k*n^2) - chcemy stworzyć graf na n^2 wierzchołkach (odpowiadających parom elementów) i dla każdej permutacji p chcemy połączyć wierzchołki (i, j) oraz (p_i, p_j) w jedną spójną.

Taka złożoność nie wystarcza. Narzuca się jednak pomysł, że gdybyśmy nie robili tego dla wszystkich permutacji z wejścia, a dla losowych permutacji z grupy przez nie generowanej, to musielibyśmy takich kwadratowych "połączeń" wykonać mniej.

I rzeczywiście tak jest. Wystarczy nawet rozważać permutacje będące złożeniem po kolei permutacji z wejścia, gdzie każdą pomijamy z prawdopodobieństwem 1/2. Skonstruowanie i rozważenie jednej takiej permutacji zajmuje czas O(n*(n+k)), a rozważyć musimy ich O(log(n)) (komplet punktów zapewne otrzymamy rozważając 30, ale oczywiście polecamy rozważać więcej).

Ja dostałem 2p za prostego bruta opartego o bazę z algorytmu Schreiera Simsa.

Robię dynamika iterując się po poszczególnych zbiorach, trackując dp[i][j] = "ile permutacji na indeksach i, j tworzy inwersje we wszystkich dotychczasowych możliwych permutacjach" oraz dpi[i][j] = "ile permutacji nie tworzy inwersji na indeksach i oraz j".

Tranzycja pojedynczej permutacji to dp[i][j] += dp[p[i]][p[j]] (analogicznie dpi), jesli p[i] < p[j] (tzn. "przepuszczenie" indeksów i oraz j przez aktualną permutację nie zmienia faktu istnienia inwersji) oraz dp[i][j] = dpi [p[j]][p[i]] (zmiana kolejnością p[j], p[i] oraz dodanie inwersji) gdy p[i] > p[i] (czyli przejście przez aktualną permutację odwraca inwersję).

Złożoność jest jakaś okropna, ale przynajmniej wielomianowa (coś typu O(n^5 log^3 n)).

Czy mogłbym prosić o uzasadnienie stwierdzenia "i rzeczywiście tak jest"?

Oczywiście. Skupmy się na jakiejś orbicie. Jeśli po aktualnie rozważonych permutacjach, orbita ta jest inna niż finalna, to dla każdej permutacji z wejścia możemy myśleć o tym czy wyprowadzi ona jakąś parę poza tę orbitę, czy też nie. Wtedy możemy skupić się na ostatniej permutacji, która to zrobi i przynajmniej jeden wynik rzutu monetą dla niej sprawi, że ta orbita połączy się z czymś nowym. Dla każdej pary elementów mamy zatem co najmniej 50% szans, że jej spójna urośnie po jednym kroku.

Mamy spisane dłuższe i bardziej formalne dowody, ale wstrzymamy się z nimi do publikacji rozwiązań wszystkiego (kto wie, może ktoś na forum przedstawi dowód ładniejszy niż nasz).

Ja miałem zupełnie inny algos, którego złożoność to O(n^2 log n log k + nk). Ostatecznie dał niestety tylko 7 pkt, ale patrząc na czasy lokalne to musiałem być na granicy 9 pkt i niewiele za 10 pkt.

Startujemy tak samo od bruta w O(n^2 k) i jedynie pytanie to jak prędzej mergować te składowe zbiorów par. Zbiór par A jest spójną składową, jeżeli wszystkie permutacje przeprowadzają go na samego siebie (i jest minimalny pod względem inkluzji z tą własnością). Kluczem mojego algorytmu jest funkcja, która dostając zbiór par A i liczbę b, stwierdza czy pierwsze b permutacji przeprowadza ten zbiór na samego siebie w czasie O(|A|). Mając takową możemy to opakować w binary searcha po b aby znaleźć pierwszą permutację, która tego nie spełnia. Mając taką w ręku możemy tę permutację zaaplikować do tego zbioru aby go z czymś połączyć, zatem jak zbiór A nie jest spójną składową, to możemy w czasie O(|A| log k) znaleźć jakąś inną składową, z którą go połączymy. Opakowując to wszystko w "mniejszy do większego" dostajemy O(n^2 log n log k).

Jak zatem wygląda owa funkcja? Dla prostoty opisu rozważę tylko b:=k. Oznaczmy i-tą permutację przez P_i oraz dla zbioru A \subset [n] x [n] oznaczmy A_i = {j : (i, j) \in A}, czyli zbiór drugich współrzędnych par, które na pierwszej współrzędnej mają i. To że permutacja P przerzuca A na samego siebie znaczy tyle że dla każdego i mamy P(A_i) = A_{P(i)}. To że wszystkie permutacje z całego zbioru P_1, ..., P_k przerzucają A na samego siebie to koniunkcja takich równości dla P_1, ..., P_k. Innymi słowy dla każdej pary (i, j) mamy mieć P_j(A_i) = A_{P_j(i)} (takich równości jest nk).

Jak sprawdzać takie nk równości szybko? Wylosujmy sobie liczby x[1], ..., x[n], y[1], ..., y[k] na początku programu. Zamiast sprawdzać nk równości sprawdźmy jedną, która będzie sumą tych nk z losowymi współczynnikami x[i]*y[j]. Ach, no i to są równości zbiorów, a nie liczb, zatem do każdego zbioru zaaplikujmy jeszcze funkcję haszującą H, gdzie H({a_1, ..., a_c}) = h[a_1]+...+h[a_c] dla także wylosowanych liczb h_[1], ..., h[n]. Chcemy zatem sprawdzić czy sum_{i, j} H(P_j(A_i)) * x[i] * y[j] = sum_{i, j} H(A_{P_j(i)}) x[i] * y[j]. Okazuje się, że po odpowiednim preprocessingu można obie strony tej równości zewaluować w O(|A|) oddzielnie analizując wkład każdego elementu A w tę sumę w O(1). Lewa strona jest trochę prostsza, prawa trochę bardziej trikowa, ale obie się da.

Ja mam tak samo jak opisał Mateusz. Dowód na liczbę iteracji:

W danej iteracji każda składowa ma ≥ 50% szansy połączyć się z inną (dopóki da się). Nie są to zdarzenia niezależne dla różnych składowych. Ale wartość oczekiwana liczby tych, które się z niczym nie połączą to ≤ 50% z nich. Z nierówności Markowa wiemy, że szansa na to, że nie połączy się ≥ 75% z nich wynosi ≤ 50%/75% = 2/3.

Zatem z prawdopodobieństwem ≥ 1/3 liczba niedokończonych składowych maleje o czynnik ≤ 7/8. Więc średnio wystarczy O(log n) iteracji.

Ja robię tak, że kończę gdy przez 30 iteracji z rzędu nic się nie połączy. Liczba 30 tu reprezentuje log (liczba potrzebnych iteracji) + log(1/ε) = log log n + log (1/ε) + O(1) dla ε ≈ 2^(-20). To gwarantuje, że prawdopodobieństwo błędu wynosi ≤ ε, i całe rozwiązanie działa w czasie O(n(n+k)(log n + log (1/ε))).

No ogólne szacowanie, że to jest O(log n) istotnie nie było jakoś bardzo trudne, ale w kontekście dania tego zadania istotne było jednak doszacowanie ile dokładnie. Najwredniejszy test jaki mieliśmy wymagał przy odrobinie pecha około 30 iteracji, a dowód podobny do tego, który opisał Tomek po doliczeniu do końca dawał szacowanie, że około 100 iteracji daje już bliskie 0 prawdopodobieństwo porażki. Jak ktoś ma chwilę, to zachęcam do pokminienia jak udowodnić lepsze szacowanie/poszukać lepszego testa
BTW dobry trik implementacyjny z tą stałą od ostatniego update'a (chociaż while(clock) prostsze 😆)