Omówienie zadania Zjazd obieżyświatów (III etap XXVI OI)

Jest to zadanie grafowe, ponieważ świat, po którym podróżują tytułowe obieżyświaty, składa się z \(n\) schronisk połączonych jednokierunkowymi ścieżkami. Wobec tego będziemy go modelować jako \(n\)-wierzchołkowy graf skierowany.

Mamy \(k\) obieżyświatów, którzy początkowo znajdują się w pewnych schroniskach i każdy z nich każdego dnia zmienia swoje położenie, przechodząc dokładnie jedną, dowolnie wybraną ścieżką do innego schroniska. Mamy sprawdzić, czy jest możliwe, żeby w pewnym momencie wszyscy znaleźli się w jednym miejscu. Jeśli tak, to po ilu dniach najszybciej.

Rozgrzewka (podzadanie 2)

Główny powód, dla którego obieżyświaty mogą nie być w stanie spotkać się w jednym miejscu, jest to, że muszą ciągle być w ruchu. Gdybyśmy nie mieli takiego założenia, to nasze zadanie znacznie by się uprościło. Na rozgrzewkę omówimy sobie rozwiązanie takiego prostszego zadania, przy okazji rozwiązując podzadanie 2, w którym mamy warunek umożliwiający każdemu obieżyświatowi pozostanie w każdym schronisku.

To oznacza, że z każdego schroniska istnieje bezpośrednia ścieżka prowadząca z powrotem do tego samego schroniska. W grafie taką ścieżkę możemy reprezentować jako pętelkę z wierzchołka do niego samego.

Gdybyśmy zatem ustalili, w którym wierzchołku obieżyświaty mają się spotkać, to wystarczy, żeby każdy z nich poszedł tam jak najkrótszą drogą, a następnie poczekał na to, aż zjawią się tam pozostali. Tak więc dla wybranego wierzchołka \(v\), w którym mają się wszyscy spotkać, minimalny czas spotkania to będzie maksimum z długości najkrótszych ścieżek z początkowych wierzchołków, w których znajdują się obieżyświaty, do wierzchołka \(v\).

Ponieważ będziemy potrzebowali długości najkrótszych ścieżek do wszystkich wyborów wierzchołka \(v\), więc najprościej będzie obliczyć odległości pomiędzy wszystkimi parami wierzchołków. Można to zrobić w czasie \(O(n^3)\), na przykład algorytmem Floyda–Warshalla. Mając policzone te odległości, iterujemy się po wszystkich \(n\) wierzchołkach \(v\) i dla każdego z nich liczymy maksimum w czasie \(O(n)\). Ten drugi krok zajmie nam jedynie czas \(O(n^2)\). A ponieważ \(n \leq 250\), więc takie rozwiązanie o złożoności \(O(n^3)\) spokojnie zmieści się w limicie czasu.

Graf stanów (podzadanie 1)

No dobrze, ale jak poradzić sobie z zadaniem, w którym obieżyświaty nie mają zagwarantowane, że mogą pozostawać w schroniskach? W szczególności jak stwierdzić, czy w ogóle do spotkania obieżyświatów może dojść? O ile bowiem odpowiedź ,,tak” możemy uzasadnić, pokazując konkretne ścieżki obieżyświatów, które pozwalają im spotkać się w pewnym wierzchołku, to uzasadnienie odpowiedzi negatywnej nie jest już takie proste.

Będziemy konstruować graf stanów, w którym stany opisują podzbiory wierzchołków oryginalnego grafu, w których mogą znajdować się obieżyświaty (ponieważ w grafie mamy \(n\) wierzchołków, wobec tego możliwych stanów mamy \(2^n\)). Istnieje skierowana krawędź ze stanu \(s_1\) do stanu \(s_2\), jeśli obieżyświaty zajmujące wierzchołki z \(s_1\) w jednym ruchu mogą się tak przemieścić, żeby zajmować wierzchołki z \(s_2\).

Każdy stan możemy reprezentować jako \(n\)-bitową maskę i będziemy te stany przeglądali w kolejności rosnących masek. Aby wygenerować krawędzie ze stanu \(s\), patrzymy na pierwszy wierzchołek \(v\) z tego stanu i stan \(s_v = s \setminus \{ v\}\), który już był przeanalizowany. Krawędzie z \(s\) prowadzą do wszystkich stanów postaci \(\{v'\} \cup s'\), jeśli istnieje krawędź \(v\to v'\) w grafie oraz istnieje krawędź \(s_v \to s'\) w grafie stanów.

Ponieważ wyboru dla pierwszego wierzchołka mogliśmy wykonać na \(n\) sposobów, a liczba przejść dla stanu \(s_v\) to jest potencjalnie \(O(2^n)\), wobec tego czas generowania krawędzi dla jednego stanu to będzie \(O(2^n n)\).

Mając dany graf stanów, przy pomocy algorytmu BFS znajdujemy najkrótszą ścieżkę ze stanu zawierającego początkowe pozycje obieżyświatów, do pewnego stanu, który zawiera tylko jeden wierzchołek. Wiemy, że algorytm BFS działa w czasie liniowym od wielkości grafu. Graf stanów ma potencjalnie rozmiar \(O(4^n n)\), więc jest to dość duży wykładniczy rozmiar, ale pozwoli on na zaliczenie podzadania 1, w którym \(n \leq 10\).

Programowanie dynamiczne (podzadanie 1)

Do tego podzadania możemy zaproponować jeszcze jeden algorytm. Zauważmy, że jeżeli odpowiedź do zadania jest pozytywna, to znaczy, że w grafie stanów musi istnieć jakaś ścieżka ze stanu początkowego do stanu jednowierzchołkowego. Ponieważ interesuje nas najkrótsza taka ścieżka, wobec tego wiemy, że jej długość będzie ograniczona przez liczbę wszystkich stanów w grafie, czyli nie będzie dłuższa niż \(2^n\). Wobec tego, gdybyśmy umieli sprawdzać, gdzie po \(t\) dniach mogą znaleźć się obieżyświaty, to moglibyśmy przejrzeć wszystkie dni od \(1\) do \(2^n\).

Jeżeli w żadnym z nich obieżyświaty nie mogliby znaleźć się w jednym wierzchołku, to znaczy, że odpowiedź jest negatywna. Aby sprawdzić, gdzie obieżyświaty mogą znaleźć się po \(t\) dniach, zastosujemy programowanie dynamiczne. Będziemy wypełniać tablicę wartości logicznych \(dp\), w której \(dp_t[i,j]\) będzie oznaczało, czy startując z wierzchołka \(i\) można dojść do wierzchołka \(j\) po dokładnie \(t\) dniach. W szczególności zauważmy, że tabelka \(dp_1\) to jest nic innego jak macierz sąsiedztwa naszego grafu, czyli \(dp_1[i,j]\) jest prawdą wtedy i tylko wtedy, kiedy mamy krawędź \(i \to j\).

W jaki sposób obliczyć tabelkę dla czasu \(t + 1\), jeżeli mamy obliczoną tabelkę dla czasu \(t\)? Jeżeli istniałaby ścieżka z wierzchołka \(i\) do wierzchołka \(j\) o długości dokładnie \(t + 1\), to ścieżka ta po dokładnie \(t\) krokach musiałaby odwiedzić jakiś wierzchołek \(k\) oraz musi istnieć krawędź \(k \to j\). Ponieważ nie wiemy, który to jest wierzchołek \(k\), więc możemy przetestować wszystkie wierzchołki: \[dp_{t+1}[i,j] = \bigvee_{k}\ dp_t[i,k] \land dp_1[k,j].\]

Ponieważ każda tabelka \(dp_t\) ma \(n^2\) pól i wypełnienie każdego pola to jest przeglądnięcie \(n\) potencjalnych kandydatów na wierzchołek \(k\), więc wypełnienie jednej tabelki będzie działać w czasie \(O(n^3)\).

Mając obliczoną tabelkę \(dp_{t}\) możemy w czasie kwadratowym sprawdzić, czy obieżyświaty mogą spotkać się w jednym wierzchołku po dokładnie \(t\) krokach. Po prostu iterujemy się po wszystkich możliwych miejscach spotkania i sprawdzamy, czy istnieją ścieżki o długości \(t\) od wszystkich wierzchołków początkowych do tego miejsca.

Tak więc ostateczny algorytm jest następujący: obliczamy sobie tabelki \(dp_t\) dla coraz większych wartości \(t\) i dla każdej z nich sprawdzamy, czy obieżyświaty mogą spotkać się w jednym miejscu. Jeżeli dojdziemy do \(t\) równego \(2^n\) nie znalazłszy żadnej takiej tabelki, to wtedy kończymy algorytm i odpowiadamy ,,nie”.

Całkowita złożoność czasowa tego algorytmu to będzie \(O(2^n n^3)\). On również przechodzi podzadanie z \(n \leq 10\).

Wyszukiwanie binarne i szybkie potęgowanie

Aby zoptymalizować to wykładnicze rozwiązanie do rozwiązania wzorcowego, będziemy potrzebowali jeszcze dwóch obserwacji. Jeżeli obieżyświaty mogą spotkać się w jednym miejscu po \(t\) dniach, to wynika z tego, że mogą spotkać się po \(t + 1\) dniach, po \(t + 2\) dniach itd., czyli po dowolnym czasie większym równym od \(t\) (po prostu spotykają się w jednym miejscu po \(t\) dniach, a następnie od tego momentu już podróżują wspólnie).

Z tego wynika, że do rozwiązania zadania możemy zastosować wyszukiwanie binarne. Początkowo wiemy, że jeżeli odpowiedź jest pozytywna, to \(t\) musi się zawierać w przedziale \([0,2^n]\). Będziemy ten przedział sukcesywnie połowić. W pierwszym kroku spytamy się, czy dla \(t = 2^{n-1}\) możemy się spotkać, czy też nie. Jeżeli odpowiedź jest pozytywna, to wiemy, że przedział czasu zmniejsza się do \([0,2^{n-1}]\), a jeżeli odpowiedź jest negatywna, to wiemy, że ten przedział będzie \([2^{n-1}+1,2^n]\).

Ponieważ jednak długość przedziału, na którym będziemy wyszukiwać binarnie, jest wykładnicza względem \(n\), tak więc liczba iteracji wyszukiwania, będzie równa \(\log 2^n = n\).

Ponieważ do tej pory sprawdzaliśmy, czy do spotkania może dojść po czasie \(t\) poprzez analizę tabelki \(dp_t\), więc pozostała jeszcze jedna trudność, jak obliczać szybko tę tabelkę dla dużych wartości \(t\). W tym celu powróćmy do rekurencji na obliczanie tabelek. W rekurencji tej braliśmy tabelkę \(dp_t\) i łączyliśmy ją z tabelką \(dp_1\), po to, żeby uzyskać tabelkę \(dp_{t+1}\).

Ale nic nie stoi na przeszkodzie, żeby tą samą metodą złączyć tabelkę \(dp_t\) oraz tabelkę \(dp_s\). Interpretacja będzie taka, że jeżeli zaczynamy z wierzchołka \(i\) i idziemy jakąś ścieżką długości \(t\), dochodząc do pewnego wierzchołka \(k\), a następnie z wierzchołka \(k\) idziemy pewną ścieżką długości \(s\) i lądujemy w wierzchołku \(j\), to znaczy, że istnieje ścieżka długości \(t+s\) z wierzchołka \(i\) do wierzchołka \(j\).

Wobec tego, tym sposobem jesteśmy w stanie w czasie \(O(n^3)\) obliczyć tabelkę \(dp_{t+s}\) na podstawie tabelki \(dp_t\) i \(dp_s\): \[dp_{t+s}[i,j] = \bigvee_{k}\ dp_t[i,k] \land dp_s[k,j].\]

W szczególności na podstawie tabelki \(dp_t\) możemy w czasie \(O(n^3)\) obliczyć tabelkę dla \(dp_{2t}\), a to pozwala nam m.in. szybko obliczać tabelki \(dp_t\) dla \(t\) będących potęgami dwójek. Ponieważ taka operacja obliczenia tabelki dla \(t + s\) na podstawie tabelek dla \(t\) i \(s\) będzie dosyć istotna, wprowadzimy dla niej specjalne oznaczenie i będziemy pisać, że \(dp_{t+s} = dp_t \cdot dp_s\).

Nieprzypadkowo użyliśmy tutaj symbolu mnożenia, ponieważ jeżeli tabelki \(dp\) potraktujemy jako macierze boolowskie, to operacja, którą tutaj wykonujemy jest po prostu mnożeniem macierzy. W szczególności obliczenie \(dp_{t}\) możemy również potraktować jako \(t\)-krotne wykonanie mnożenia \(dp_{1} \cdot dp_1 \cdot \ldots \cdot dp_1\), czyli możemy to zapisać jako \(dp_t = (dp_{1})^t\). Przy takiej interpretacji nasuwa się skorzystanie z algorytmu szybkiego potęgowania.

W tym algorytmie, aby obliczyć \(dp_{t}\), patrzymy na parzystość liczby \(t\): \[dp_t = \left\{ \begin{array}{ll} (dp_{t/2})^2 & t \ \textrm{parzyste}, \\ (dp_{(t-1)/2})^2 \cdot dp_1 & t \ \textrm{nieparzyste}. \end{array} \right.\]

Tym sposobem \(dp_{t}\) możemy obliczyć w \(O(\log t)\) krokach, a ponieważ każdy krok zajmuje czas \(O(n^3)\), więc cały algorytm będzie działał w czasie \(O(n^3 \log t)\).

Pozostaje zastosować ten algorytm w naszym wyszukiwaniu binarnym, czyli teraz będziemy mieli \(n\) faz wyszukiwania binarnego i w każdej fazie będziemy stosowali szybkie potęgowanie, przy czym dla \(t\leq 2^n\) jego czas będzie wynosił \(O(n^4)\).

Ostatecznie cały rozwiązanie będzie miało złożoność czasową \(O(n^5)\).

Optymalizacja wyszukiwania

Rozwiązanie to można usprawnić, ściślej łącząc nasz algorytm wyszukiwania binarnego z algorytmem szybkiego potęgowania. W tym celu liczymy sobie tabelki \(dp\) dla kolejnych potęg dwójki: \(dp_1, dp_2, dp_4, \ldots, dp_{2^{n-1}}\).

Ponieważ każdą tabelkę możemy wyznaczyć w czasie \(O(n^3)\), korzystając z tabelki poprzedniej, a tabelek mamy \(n\), więc cała ta operacja zajmie nam czas \(O(n^4)\).

Teraz będziemy robić wyszukiwanie binarne, korzystając bezpośrednio z obliczonych tabelek. Początkowe kroki wyglądają następująco. Najpierw na podstawie ostatniej tabelki odpowiadamy na pytanie, czy dla \(t = 2^{n-1}\) możemy się spotkać, czy nie. Jeżeli to spotkanie będzie możliwe, to wtedy o środek przepołowionego przedziału zapytamy tabelkę \(dp_{2^{n-2}}\).

Natomiast jeżeli nie doszło do spotkania, to wtedy środkiem kolejnego przedziału będzie iloczyn tabelki \(dp_{2^{n-2}}\) i \(dp_{2^{n-1}}\). W ogólności algorytm będzie działał tak, że będziemy utrzymywali tabelkę \(dp\) dla lewego końca przedziału. Jeżeli teraz zmniejszymy nasz przedział do długości np. \(8\), to wiemy, że aby sprawdzić środek przedziału, to do jego lewego końca musimy domnożyć \(dp_4\). I na podstawie tego, czy w środku przedziału doszło do spotkania, czy nie, to lewy koniec albo pozostaje niezmieniony, albo jako lewy koniec bierzemy właśnie środek przedziału.

Tak więc teraz w każdej fazie wyszukiwania binarnego wystarczy nam wykonać tylko jedno mnożenie macierzy o czasie \(O(n^3)\). Wobec tego całość wyszukiwania będzie również działała w czasie \(O(n^4)\). Taki też będzie czas ulepszonego algorytmu.

Ograniczenie wielomianowe

Do pełni szczęścia pozostaje nam zrobienie jeszcze jednej obserwacji, tym razem dość nieoczywistej. Do tej pory nasze algorytmy polegały na tym, że możemy ograniczyć szukanie czasu spotkania do wartości \(t \leq 2^n\).

Okazuje się jednak, że to ograniczenie jest bardzo zgrubne. Można nabrać takich podejrzeń, próbując konstruować testy, które wymagałyby dużego czasu spotkania. Już nawet osiągnięcie nietrywialnego czasu wielomianowego może nastręczać pewnych trudności. Przykładem testu o kwadratowym czasie spotkania może być cykl o długości \(n\) ze skrótem, to znaczy jedną dodatkową krawędzią skaczącą o \(2\) oraz dwoma obieżyświatami \(A\) i \(B\), którzy na początku znajdują się na przeciwległych wierzchołkach cyklu, to znaczy w odległości \(\frac{n}{2}\).

W takiej sytuacji obieżyświaty muszą poruszać się po cyklu, przy czym dozwolone jest skorzystanie ze skrótu. Jeżeli obieżyświat \(B\) będzie poruszał się cały czas po cyklu, natomiast obieżyświat \(A\) za każdym razem będzie korzystał ze skrótu, to po jednym obrocie odległość między obieżyświatami \(A\) i \(B\) zmniejszy się o \(1\). Czyli spotkają się dopiero po \(\frac{n}{2}\) obrotach, więc minimalny czas do spotkania w tym przypadku wyniesie około \(\frac{n^2}{2}\).

Okazuje się, że za bardzo nie możemy polepszyć naszego testu. Zachodzi bowiem fakt, który znacząco polepsza ograniczenie na czas spotkania, a mianowicie można udowodnić ograniczenie tego czasu przez \(t \leq n^2\).

Jak zmiana tego ograniczenia wpływa na złożoność czasową naszego algorytmu? Przede wszystkim przedział w wyszukiwaniu binarnym będzie kończył się na \(n^2\). Wobec tego liczba obrotów w tym wyszukiwaniu to będzie \(\log n^2 = O(\log n)\).

Również tablic \(dp\), które musimy obliczyć, będzie logarytmicznie wiele, wobec tego preprocessing dla tych tablic zrobimy w czasie \(O(n^3 \log n)\) i w tym samym czasie zrobimy wyszukiwanie binarne. Tak więc ostateczne rozwiązanie będzie miało złożoność \(O(n^3 \log n)\).

Pozostaje oczywiście udowodnić poprawność nowego ograniczenia na \(t\). Ponieważ w złożoności czasowej algorytmu to ograniczenie występuje pod logarytmem, więc satysfakcjonowałoby nas dowolne wielomianowe ograniczenie. Z tego powodu pokażemy dowód nieco słabszego ograniczenia \(t \leq n^3\), z uwagi na to, że dowód ten jest dużo prostszy niż dowód ograniczenia \(t \leq n^2\).

Dowód poprawności ograniczenia

Załóżmy więc, że obieżyświaty mogą spotkać się w chwili \(t_\mathit{spo}\) (gdzie być może \(t_\mathit{spo}\) jest bardzo duże). Załóżmy ponadto, że miejsce spotkania znajduje się na pewnym cyklu w grafie (jeśli się nie znajduje, to obieżyświaty idą wspólnie dalej w dowolny sposób i po co najwyżej \(n\) krokach ich trasa zacykli się; to miejsce będzie miejscem spotkania leżącym na pewnym cyklu). Niech \(v_\mathit{spo}\) będzie miejscem spotkania oraz niech \(C_\mathit{spo}\) będzie pewnym (dowolnym) cyklem prostym na którym leży \(v_\mathit{spo}\). Ponieważ jest to cykl prosty, to \(|C_\mathit{spo}|\leq n\), gdzie \(|C_\mathit{spo}|\) to długość tego cyklu (poniżej używamy także długości \(|P|\) ścieżki \(P\), która oznacza liczbę krawędzi na tej ścieżce).

Zapisem cyklowym trasy obieżyświata \(j\) nazwiemy krotkę \((P,\alpha_1,C_1,\alpha_2,C_2,\dots,\alpha_n,C_n)\), gdzie

1. \(P\) jest ścieżką z \(s_j\) (wierzchołka startowego obieżyświata \(j\)) do \(v_\mathit{spo}\),

2. \(\alpha_1,\dots,\alpha_n\) są liczbami naturalnymi takimi, że \[|P|+\sum_{i=1}^n i\cdot\alpha_i\equiv t_\mathit{spo}\pmod{|C_\mathit{spo}|}\,,\]

3. dla każdego \(i\in\{1,\dots,n\}\), jeśli \(\alpha_i>0\), to \(C_i\) jest pewnym cyklem mającym przynajmniej jeden wierzchołek wspólny ze ścieżką \(P\) (jeśli natomiast \(\alpha_i=0\), to \(C_i\) może być nieokreślone).

Taki zapis oznacza, że obieżyświat \(j\) podąża ścieżką \(P\), a w międzyczasie chodzi sobie \(\alpha_i\) razy po cyklu \(C_i\) dla każdego \(i\in\{1,\dots,n\}\); (może zacząć krążyć cyklem \(C_i\), gdy dojdzie do pewnego wierzchołka leżącego na tym cyklu, co z definicji koniecznie nastąpi). Na koniec zaczyna krążyć po cyklu \(C_\mathit{spo}\).

Zapis cyklowy od którego zaczynamy to \((P,0,C_1,0,C_2,\dots,0,C_n)\), gdzie nie ma żadnych cykli, natomiast \(P\) to ścieżka z \(s_j\) do \(v_\mathit{spo}\) długości \(t_\mathit{spo}\) istniejąca z założenia.

Udowodnimy teraz, że istnieje zapis cyklowy, w którym \(|P|\leq n(n-1)\). W tym celu załóżmy, że mamy zapis cyklowy \((P,\alpha_1,C_1,\alpha_2,C_2,\dots,\alpha_n,C_n)\), w którym \(|P|>n(n-1)\); udowodnimy, że istnieje inny zapis cyklowy, w którym długość ścieżki jest mniejsza (powtarzając taką zamianę wielokrotnie dostaniemy w końcu zapis cyklowy, w którym długość ścieżki to co najwyżej \(n(n-1)\)). Po pierwsze, możemy zmienić \(\alpha_{|C_\mathit{spo}|}\) na \(0\). Nie wpłynie to na poprawność punktu 2 definicji (ani tym bardziej punktów 1 i 3), gdyż przemnażamy tam \(\alpha_{|C_\mathit{spo}|}\) razy \(|C_\mathit{spo}|\), a na wynik patrzymy modulo \(|C_\mathit{spo}|\).

Dla każdego \(i\) takiego, że \(\alpha_i>0\), wyróżnijmy na ścieżce \(P\) pewien punkt (moment), w którym jesteśmy w wierzchołku należącym do cyklu \(C_i\). Tych punktów będzie co najwyżej \(n-1\) (nie ma punktów dla \(i\) takich, że \(\alpha_i=0\), w szczególności dla \(i=|C_\mathit{spo}|\); ponadto niektóre punkty mogą się pokrywać). Dzielą nam one ścieżkę \(P\) na co najwyżej \(n\) odcinków. Ponieważ z założenia \(|P|>n(n-1)\), to z zasady szufladkowej któryś odcinek ma długość co najmniej \(n\). Wśród \(n+1\) pierwszych wierzchołków tego odcinka (jest co najmniej \(n\) krawędzi, czyli co najmniej \(n+1\) wierzchołków) pewien wierzchołek się powtarza. Innymi słowy, fragmentem rozważanego odcinka jest cykl pewnej długości \(l\), gdzie \(l\leq n\). Usuńmy sobie ten cykl z \(P\), zwiększając jednocześnie \(\alpha_l\) o \(1\); w ten sposób suma rozważana w punkcie 2 definicji się nie zmieni, natomiast długość ścieżki się zmniejszy. Jeśli wcześniej \(\alpha_l\) było zerem (czyli \(C_l\) było nieokreślone), to jako \(C_l\) bierzemy usuwany cykl. Widzimy, że nowa ścieżka przechodzi przez pewien wierzchołek tego cyklu. Przechodzi także przez wierzchołek każdego z pozostałych cykli \(C_i\) (dla których \(\alpha_i>0\)), gdyż nie usunęliśmy z \(P\) żadnego z wyróżnionych punktów. Zatem punkt 3 definicji także pozostaje spełniony.

Używając powyższego, dostajemy zapis cyklowy \((P,\alpha_1,C_1,\alpha_2,C_2,\dots,\alpha_n,C_n)\), w którym \(|P|\leq n(n-1)\). Zamieńmy ponadto każde \(\alpha_i\) na \((\alpha_i\bmod|C_\mathit{spo}|)\); nie wpływa to na prawdziwość punktu 2 definicji, gdyż i tak bierzemy wszystko modulo \(|C_\mathit{spo}|\).

Ponieważ \(i\cdot \alpha_i\leq i\cdot|C_\mathit{spo}|\leq i\cdot n\), odkodowując otrzymany zapis cyklowy dostajemy ścieżkę z \(s_j\) to \(v_\mathit{spo}\) długości \[|P|+\sum_{i=1}^n i\cdot\alpha_i \leq n(n-1)+(1+2+\dots+n)\cdot n\leq n^3\,.\] Ponadto, ta długość przystaje do \(t_\mathit{spo}\) modulo \(|C_\mathit{spo}|\). Jest tak dla każdego obieżyświata \(j\): znajdzie się on przed chwilą \(n^3\) w punkcie \(v_\mathit{spo}\). Jeśli następnie będzie krążył po cyklu \(C_\mathit{spo}\), to w chwili dokładnie \(n^3\) będzie \((t_\mathit{spo}\bmod|C_\mathit{spo}|)\) wierzchołków dalej.