Migający tłum

03.06.2009
Trudność

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?

Wiktor Janas

4
Twoja ocena: Brak Ocena: 4 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com