Migający tłum

03.06.2009

Większość zawodników dokonała tylko jednego zgłoszenia do tego zadania, jednak większość z tych zgłoszeń okazała się niepoprawna. Ci,którym udało się rozwiązać zadanie w większości podeszli do niego jak do problemu grafowego: wyznaczali wszystkie cykle grafu oraz pozycję poszczególnych osób w tych cyklach. Po tym etapie, majacym złożoność $O(n)$ byli w stanie odpowiadać na kolejne zapytania w czasie $O(1)$ (czyli stałym). Jest to optymalne rozwiązanie tego problemu oraz podejście, którego się spodziewaliśmy.

Tutaj przedstawimy inny sposób spojrzenia na to zadanie. Rozwiązanie będzie nieco wolniejsze - obliczenia wstępne będą miały złożoność $O(n \log k_{\max})$ , a na pytania będziemy odpowiadali w czasie $O(\log k)$ , jednak sposób rozumowania ujawni pewne ciekawe właściwości matematyczne.

Na wejściu dana jest permutacja n-elementowa. Cóż to takiego? Intuicyjnie można permutację zrozumieć jako opis przekazywania sobie żarówek. Formalnie rzecz ujmując permutacja jest przyporządkowanim każdemu elementowi zbioru drugiego elementu w taki sposób, aby każdy element był przyporządkowany dokładnie jednemu. Fakt, że wejście jest permutacją był zgwarantowany przez stwierdzenie "n różnych liczb naturanych z zakresu 1 ... n". Permutację identycznościową, czyli taką, w której każdemu elementowi przyporządkowany jest on sam, zapiszemy jako

$e = (1, 2, 3, \ldots, n-2, n-1, n)$

Natomiast permutację, w której każdemu elementowi przyporządkowany jest następny, a ostatniemu pierwszy (tego typu permutacja pokazana została w teście przykładowym) zapiszemy jako

$p = (2,3,4, \ldots, n-1, n, 1)$

Zdefiniujemy operację składania permutacji (będziemy oznaczać ją symbolem $\circ$ ). Będzie ona odpowiadała uderzeniom zegara z treści zadania. W permutacji $p$ elementowi pierwszemu przyporządkowany jest drugi, a elementowi drugiemu przyporządkowany jest trzeci. Zatem po pierwszym uderzeniu zegara osoba pierwsza będzie trzymała żarówkę koloru drugiego, a druga - trzeicego. Po drugim uderzeniu zegara osoba pierwsza będzie trzymała żarówkę koloru trzeciego. Zatem w złożeniu permutacji $p$ z samą sobą (co zapiszemy jako $p \circ p$ ) elementowi pierwszemu jest przyporządkowany element trzeci. Formalnie jeżeli w permutacji $a$ elementowi $x$ jest przyporządkowany $y$ , a w permutacji $b$ elementowi $y$ jest przyporządkowany $z$ , to w złożeniu $a \circ b$ elementowi $x$ jest przyporządkowany $z$ . Nowopowstała permutacja może zastępować nam złożenie dwóch permutacji wyjściowych w każdym wypadku (tzn. jeżeli $c$ jest złożeniem $a \circ b$ , to zawsze, gdzie pojawia się $a \circ b$ możemy napisać po prostu $c$ ).

Widzimy, że pytanie "jaki kolor żarówki trzyma osoba a po k uderzeniach zegara" jest równoważne pytaniu "jaki element jest przyporządkowany elementowi a w k-krotnym złożeniu permutacji z samą sobą". Wielokrotne złożenie permutacji $p$ z samą sobą zapizsemy jako $p^k$ , gdzie $k$ jest ilością złożeń. Obliczenie jednokrotnego złożenia permutacji ma złożoność $O(n)$ . My chcielibyśmy obliczyć złożenia $p^2, p^4, p^8, p^{16}, p^{32}, \ldots, p^{2^{31}}, p^{2^{32}}$ . Najpierw składamy $p \circ p = p^2$ . Później możemy złożyć $p^2 \circ p^2 = p \circ p \circ p \circ p = p^4$ . Następnie $p^4 \circ p^4 = p^8$ i tak dalej. Taki sposób potęgowania (nie tylko permutacji) nazywany jest szybkim potęgowaniem. Używając go każdą kolejną permutację otrzymujemy wykonując tylko jedno złożenie.

Teraz czas odpowiedzieć na zapytania. Przyjmijmy $k = 12321 = 2^{13} + 2^{12} + 2^5 + 2^0$ . Skorzystamy z tego, że

$p^{12321} = p^{2^{13} + 2^{12} + 2^5 + 2^0} = p^{2^0} \circ p^{2^5} \circ p^{2^{12}} \circ p^{2^{13}}$

. W ten sposób rozkładamy interesującą nas permutację na złożenie permutacji, które mamy już obliczone. Teraz nie musimy składać całych permutacji - interesuje nas tylko, jaki element będzie przyporządkowany a-temu elementowi. Zatem możemy skorzystać z definicji składania permutacji dla pojedyńczego elementu, co będzie nas to kosztowało zaledwie $\log k$ (każda wartość k rozkłada się na conajwyżej $\log k$ potęg dwójki).

Zastanów się, czy istnieje taka wartość $x$ , że $p^x = p$ ? Jeżeli umiemy składać permutacje, jak wykonać działanie odwrotne?