Pachinko

Pewnie większość z Was śledziła tegoroczne finały zawodów ACM ICPC. Było sporo emocji, i całkiem przyjemny zestaw zadań. No, może odrobinę zbyt trudny (a może nawet zdecydowanie za trudny i z dziwnie dobranymi limitami), ale to nawet lepiej: będziemy mieli o czym porozmawiać. Zaczniemy od zadania H, w którym dostajemy planszę o szerokości w i wysokości h, na której niektóre pola są zablokowane, niektóre są wolne, a w niektórych znajdują się cele. Plansza służy do gry w pachinko, która zaczyna się od położenia kulki w losowo wybranym pustym polu w pierwszym wierszu. Następnie kulka zaczyna wędrować po planszy w losowy sposób, to znaczy w każdym kroku losuje, czy przesunąć sie w lewo, w prawo, do góry, czy do dołu (jeśli wylosowane kolejne pole jest zablokowane, lub znajduje się poza planszą, losujemy jeszcze raz). Prawdopodobieństwa, z jakimi wybiera każdą z tych możliwości, są takie same dla każdego pola (no i sumują się do 1). Cała zabawa kończy się wtedy, gdy kulka trafi na pole, w którym znajduje się cel. Naszym zadaniem jest wyliczenie dla każdego pola, na którym znajduje się cel, jakie jest prawdopodobieństwo, że rozgrywka zakończy się właśnie tam.

Electric_City_Akihabara_Pachinko

W całej (trochę długiej, ale jest chyba tak krótka, jak to tylko możliwe) treści warto zwrócić uwagę na dwa szczegóły. Po pierwsze, h\leq 10000 i w\leq 20, czyli plansza może być dość wysoka, ale na pewno nie jest szeroka. Po drugie, autorzy obiecują, że oczekiwana długość rozgrywki nie przekracza 10^9. Oba szczegóły są lekko podejrzane i pewnie trzeba skorzystać z przynajmniej jednego z nich, aby skonstruować efektywne rozwiązanie. Zacznijmy jednak od rozwiązania naiwnego.

Oznaczmy N=w\times h i skonstruujmy macierz M składającą się z N wierszy i N kolumn. M[i][j] to prawdopodobieństwo, że kulka znajdująca się w i-tym polu przejdzie w jednym kroku na j-te pole, przy czym myślimy, że kulka znajdująca się na polu z celem „znika” w kolejnym ruchu, czyli nigdzie nie przechodzi, no i jakoś tam numerujemy wszystkie pola. Skonstruujmy także wektor u, w którym i-ta liczba to prawdopodobieństwo, że cała gra zaczyna się z kulką umieszczoną w i-tym polu. Teraz widać, że uM^t to po prostu rozkład prawdopodobieństwa po t ruchach, czyli interesuje nas wyliczenie u(1+M+M^2+\ldots). Ale czy taka nieskończona suma na pewno ma sens?

Ano ma, bo autorzy obiecują, że oczekiwany długość gry nie przekracza 10^9, a więc w szczególności jest skończona. To oznacza, że uM^t zbiega do wektora zerowego dla t\rightarrow\infty. Czyli u(1+M+M^2+\ldots) jest dobrze zdefiniowane, ale jak wyliczyć takie nieskończone wyrażenie?

Są przynajmniej dwa sposoby, przy czym jeden jest trochę naciągany. Możemy bowiem wyliczyć u(1+M+\ldots+M^t) dla dość dużego t, powiedzmy t=10^{20}, i powiedzieć, że prawdziwy wynik nie może być istotnie różny od tego wyliczonego. A jak wyliczyć u(1+M+\ldots+M^t)? Można na przykład skonstruować nową (trochę większą) macierz M' taką, że z M'^t da się „wyczytać” 1+M+M^2+\ldots+M^t. Można też trochę bardziej wprost: mając dane 1+M+\ldots+M^{2^k-1} i M^{2^k} łatwo wyliczyć 1+M+\ldots+M^{2^{k+1}-1}=(1+M+\ldots+M^{2^k-1})(1+M^{2k}) i M^{2^{k+1}}=M^{2^k}M^{2^k}, co pozwala na wyznaczenie szukanej sumy używając \log t mnożeń macierzy. Jest to jednak odrobinę naciągen, bo nie do końca wiadomo, jak duże powinno być t. Lepiej więc zauważyć, że (1+M+M^2+\ldots)=(I-M)^{-1}, gdzie I oznacza macierz z jedynkami na przekątnej i zerami wszędzie indziej. Jest to nic innego niż dobrze Wam znany wzór na sumę szeregu geometrycznego!

Chwila. Przecież dzisiaj sumujemy kolejne potęgi macierzy, a nie jakiejś liczby. No tak, ale wzór jest dalej prawdziwy. Łatwo sprawdzić, że (I-M)(1+M+M^2+\ldots)=1, czyli o ile tylko I-M jest macierzą odwracalną, wszystko działa. Okazuje się, że o ile tylko M^t zbiega do macierzy zerowej dla t\rightarrow\infty, to I-M jest macierzą odwracalną. Jest to w sumie ciekawe samo w sobie, spróbujmy więc udowodnić, że faktycznie tak jest. Dla uproszczenia rozważymy tylko sytuację, z którą mamy do czynienia w zadaniu, to jest założymy, że wszystkie liczby w M są nieujemne.

Lemat. Jeśli wszystkie liczby w M są nieujemne, oraz M^t zbiega do macierzy zerowej dla t\rightarrow\infty, to I-M jest macierzą odwracalną.

Dowód. Niech ||M|| oznacza maksymalną sumę wartości bezwzględnych elementów w tej samej kolumnie M. Skorzystamy (bez uzasadnienia) z tego, że ||AB|| \leq ||A|| ||B|| dla dowolnych (niekoniecznie kwadratowych) macierzy A i B, w szczególności B może być tak naprawdę wektorem. Załóżmy, że I-M nie jest macierzą odwracalną. Oznacza to, że istnieje niezerowy wektor x, dla którego (I-M)x=0. Ale wtedy ||x||=||Ix||=||Mx||. Skoro ||Mx||\leq ||M||||x||, dostajemy, że ||x||\leq ||M|| ||x||, czyli ||M||\geq 1. Wiemy więc, że suma wartości bezwzględnych elementów w pewnej kolumnie M to przynajmniej 1, powiedzmy, że jest to i-ta kolumna. Jeśli więc weźmiemy sobie wektor u, którego i-tym elementem jest jedynka (a wszędzie indziej są zera), to uM jest wektorem, którego i-ty element nei jest mniejszy niż 1 (skorzystaliśmy tutaj z nieujemności liczb w M). Bardziej ogólnie, dla dowolnie dużego t mamy, że i-ty element uM^t nie jest mniejszy niż 1. Wynika stąd, że M^t nie może zbiegać do macierzy zerowej, wtedy bowiem mielibyśmy, że uM^t zbiega do wektora zerowego. Otrzymana sprzeczność pokazuje, że rzeczywiście I-M jest macierzą odwracalną.

Fajnie, ale nasze M^t wcale nie musi zbiegać do macierzy zerowej! Wiemy tylko, że uM^t zbiega do wektora zerowego. Wystarczy jednak lekko zmodyfikować oryginalną planszę blokując wszystkie pola, na których nie może się znaleźć kulka startująca z pierwszego wiersza. Wtedy dla każdej pary wolnych pól i,j na pewno M^t[i][j] zbiega do zera, gdyż w przeciwnym wypadku szansa, że cała rozgrywka trwa nieskończenie długo, byłaby niezerowa. No a jeśli i lub j nie jest wolnym polem, ustawiamy M[i][j]=0, więc M^t[i][j]=0.

Skonstruowaliśmy więc dość wolny (lecz poprawny) algorytm, który najpierw konstruuje macierz M, a następnie wylicza (1+M+M^2+\ldots)u. Jest dość prosty, gdyż musimy tylko odwrócić macierz M, na przykład przy pomocy eliminacji Gaussa. Ale, niestety, M może być nawet rozmiaru 200000\times 200000, czyli daleko w ten sposób raczej nie zajedziemy. Trzeba by jakoś sprytniej. Skorzystaliśmy już z tego, że oczekiwana długość rozgrywki jest skończona, więc teraz może trzeba by spróbować wykorzystać to, że w\leq 20?

W dalszym rozumowaniu pomocne będzie nieco inne spojrzenie na całą sytuację. Spróbujemy wyznaczyć prawdopodobieństwo każdego wolnego pola. Wyobraźmy sobie wszystkie sekwencje kolejnych ruchów, podczas których kulka nie wychodzi poza wolne pola. Każdej takiej sekwencji odpowiada w naturalny jakieś prawdopodobieństwo, które jest iloczynem prawdopodobieństw kolejnych ruchów (i początkowego prawdopodobieństwa, że zaczniejmy w konkretnym wolnym polu leżącym w pierwszym wierszu). Teraz prawdopodobieństwo wolnego pola to po prostu suma prawdopodobieństw wszystkich sekwencji, które powodują, że kulka trafia właśnie na to wolne pole. Łatwo zobaczyć, że mając taką informację dla każdego wolnego pola, bez większego problemu wyznaczymy wynik dla każdego celu: wystarczy tylko popatrzeć na jego wolnych sąsiadów i zsumować ich prawdopodobieństwa przemnożone przez prawdopodobieństwo, że w kolejnych ruchu trafimy właśnie w ten cel.

Kuszące wydaje się wyznaczania prawdopodobieństw kolejnych wolnych pól korzystając z programowania dynamicznego. Gdyby na przykład kulka poruszała się zawsze tylko w dół, lewo, lub prawo, pewnie moglibyśmy w miarę łatwo wyznaczyć prawdopodobieństwa dla pól znajdujących się w kolejnych wierszach. Wystarczy bowiem zdefiniować M[i][j] jako prawdopodobieństwo, że kulka startująca w i-tym polu w pierwszym wierszu przejdzie w jednym ruchu na j-te pole (też pierwszym wierszu). Korzystając z opisanej wcześniej sztuczki możemy łatwo wyliczyć 1+M+M^2+M^3+\ldots, co daje nam prawdopodobieństwa wszystkich wolnych pól w pierwszym wierszu. A dalej… jest tak samo. Trzeba tylko wyznaczyć prawdopodobieństwa początkowe wszystkich wolnych pól w drugim wierszu. Jest to jednak proste: trzeba tylko dla każdego wolnego pola w pierwszym wierszu przemnożyć wyliczone prawdopodobieństwo przez prawdopodobieństwo, że kolejny ruch będzie ruchem w dół. Da nam to startowe prawdopodobieństwo sąsiedniego pola w drugim wierszu (o ile jest ono wolne). Czyli tak naprawdę całe rozwiązanie sprowadza się do wyznaczania prawdopodobieństw pól w kolejnych wierszach, w każdym z nich musimy tylko odwrócić macierz w\times w.

No fajnie, ale przecież kulka może poruszać się także w górę. Jest to dość kłopotliwe, gdyż uniemożliwa przetwarzanie pól wiersz po wierszu. Ale może da się to jakoś naprawić?

Wyobraźmy sobie wszystkie możliwe sekwencje kolejnych ruchów. Możemy podzielić je na dwa typy. Sekwencje pierwszego typu zaczynają się od ruchu w dół i nigdy już nie wracają do pierwszego wiersza. Sekwencje drugiego typu prędzej lub później wracają do pierwszego wiersza, i to być może więcej niż raz. Każdą sekwencję drugiego typu można w naturalny (i jednoznaczny) sposób pokroić na maksymalne kawałki, które zaczynają i kończa się w pierwszym wierszu, i które wracają do pierwszego wiersza dopiero na samym końcu. Nazwijmy taki kawałek pętlą. Powiedzmy, że znamy sumaryczne prawdopodobieństwo M[i][j] wszystkich pętli, która zaczynają się w i-tym polu w pierwszym wierszu, a kończą w j-tym polu (też w pierwszym wierszu). Wtedy łatwo możemy wyznaczyć prawdopodobieństwo wszystkich wolnych pól w pierwszym wierszu. Niech bowiem u będzie wektorem prawdopodobieństw początkowych, wtedy interesuje nas wyznaczenie u(1+M+M^2+\ldots), czyli znów trzeba tylko odwrócić macierz w\times w. Następnie można wyznaczyć prawdopodobieństwa początkowe wolnych pól w drugim wierszu (mnożąc prawdopodobieństwa ich sąsiadów w pierwszym wierszu przez prawdopodobieństwo, że kolejny ruch będzie ruchem w dół) i powtórzyć rozumowanie. Po przetworzeniu k pierwszym wierszy, prawdopodobieństwo początkowe i-tego wolnego pola w k-tym wierszu będzie równe sumie prawdopodbieństw wszystkich sekwencji, które kończą się własnie w tym polu, i nie odwiedzają wcześniej żadnego innego pola w k-tym wierszu.

Ale przecież nie znamy M[i][j]! Może jednak da się je łatwo wyliczyć? Jest to tak naprawdę suma prawdopodobieństw wszystkich sekwencji, które zaczynają się w i-tym polu w drugim wierszu, kończą się w j-tym polu w drugim wierszu, i które nie odwiedzają żadnego pola w pierwszym wierszu, przemnożona przez prawdpodobieństwo ruchu w dół z i-tego pola w pierwszym wierszu i ruchu w górę z j-tego pola w drugim wierszu (zakładamy tutaj, że wszystkie te pola są wolne; jeśli nie są, M[i][j]=0). Sugeruje to, że być może należy wyznaczać kolejne M_k[i][j] dla k=h,h-1,\ldots,2, czyli sumy prawdopodobieństw wszystkich sekwencji, które zaczynają się w i-tym polu w k-tym wierszu, kończą się w j-tym polu w k-tym wierszu, i nie odwiedzają żadnego pola w pierwszych k-1 wierszach. Okazuje się, że wyznaczenie M_k mając M_{k+1} sprowadza się znów do odwrócenia macierzy w\times w. Wystarczy bowiem wyborazić sobie, że każda taka sekwencja może zostać pokrojona na kawałki, który zaczynają się i kończą w k-tym wierszu, ale nie odwiedzają wcześniej żadnego innego pola w k-tym wierszu. Każdy taki kawałek albo jest trywialny, to znaczy po prostu przechodzimy w nim do lewego lub prawego sąsiada, lub zaczyna się od ruchu w dół, kończy ruchem w górę, a cała środkowa część to tak naprawdę sekwencja, która zaczyna się w i-tym polu w k+1-tym wiersz, kończy się w j-tym polu w k+1-tym wierszu, oraz nie odwiedza żadnego pola w pierszwych k wierszach. Sumaryczne prawdopodobieństwo wszystkich takich sekwencji to znane już M_{k+1}[i][j], trzeba tylko przemnożyć je przez prawdopodobieństwo początkowego ruchu w dół i końcowego ruchu w górę otrzymując M'[i][j], a następnie wyliczyć 1+M'+M'^2+\ldots.

Jest to już całe rozwiązanie. Najpierw wyliczamy wszystkie M_k idąc z dołu do góry, a następnie wyznaczamy prawdopodobieństwa wolnych pól w kolejnych wierszach idąć z góry na dół. Przetworzenie każdego wiersza wymaga odwrócenia macierzy w\times w, czyli całe rozwiązanie działa w czasie \mathcal{O}(hw^3). Wygląda na to, że autorzy byli skłonni zaakceptować nawet wolniejsze rozwiązania, które przybliżają wynik wyznaczając wystarczającą wysoką potęgę macierzy, ale… to chyba mniej ciekawe, prawda?

Tyle w kwestii pachinko, a w następnym odcinku rozwiążemy zadanie E lub G. A może nawet oba?

Advertisements

4 myśli nt. „Pachinko

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s