Potwierdzam

Potwierdzam

Potwierdzam

Potwierdzam

@Świstak: https://i.imgflip.com/7c2wj0.jpg

@Kostek - jedna koszulka trochę mało, bo jednak trzeba sporo wysiłku aby skompletować te co się nie ma, nawet jeżeli się ma ich takie 7/9, a czasu w trakcie Potyczek za dużo nie ma. Może honorowe uczestnictwo w finale poza konkursem? Albo prywatny rejudge GRU z TL zwiększonym o 5 sekund?

Potwierdzam

Potwierdzam

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.

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).

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

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)).

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).

Możemy wprowadzić jakieś ograniczenie górne, po którym odpowiedzi zostaną ujawnione albo przynajmniej progi obniżone?

Serio nie ma k = 1? xd