Analiza

Dodelimo žetonu na poziciji ~(x, y)~ vrednost ~2^{2-x-y}~. Primetimo da se nakon jednog poteza pri normalnoj igri zbir vrednosti svih žetona neće promeniti, što znači da je potreban (ali ne i dovoljan) uslov da Buba kaže "Stop!" da zbir vrednosti svih žetona bude tačno ~1~. Pošto se dodavanjem novog žetona u _debug_ modu ova vrednost povećava, ovo znači da će u najviše jednom trenutku zbir vrednosti svih žetona na tabli biti jednak ~1~. Ako vrednost table "preskoči" ~1~ ili nikad ne dostigne ~1~, znamo da nema rešenja.

U trenutku kada vrednost dostigne ~1~, pokušaćemo da rekonstruišemo niz poteza koji tablu dovodi u to stanje. Ovo ćemo raditi grabljivim algoritmom odnazad. Posmatrajmo sve žetone u poslednjoj nepraznoj dijagonali (pod dijagonalom podrazumevamo skup polja sa konstantnom vrednošću ~x+y~). Rešenje postoji ako i samo ako se oni mogu upariti tako da svaki par čine dva žetona koji se nalaze na poljima koja imaju zajedničko teme.

Ovo uparivanje se može uraditi na jedinstven način, ako je uopšte moguće, ponovo grabljivim algoritmom redom od žetona sa najmanjom ~x~-koordinatom. Ako smo uspešno uparili sve žetone iz ove dijagonale, za svaki par uparenih žetona na pozicijama ~(x, y+1), (x+1, y)~ kreiramo jedan žeton na poziciji ~(x, y)~. Ovaj postupak ponavljamo sve dok ne dođemo do prve dijagonale ili ne dođemo u situaciju da ne možemo da uparimo žetone.

Ako dođemo do stanja gde je samo jedan žeton u prvoj dijagonali, rešenje štampamo kao obrnuti niz žetona koje smo kreirali tokom obilaska dijagonala.

Smernice za algoritam

Trenutak kada zbir vrednosti svih žetona postane jednak ~1~ možemo pronaći tako što održavamo binarni zapis razlomka koji sadrži trenutni zbir vrednosti. Kada dodajemo žeton na poziciju ~(x,y)~, u pomoćnom nizu ~c~ treba povećati broj ~c_{x+y-2}~ za ~1~. Ako njegova vrednost postane ~2~, onda je postavljamo na ~0~ i isti postupak ponavljamo za cifru na poziciji ~x+y-3~, i tako dalje, do zaustavljanja.

Amortizovanom analizom složenosti se može pokazati da ovaj postupak ima vremensku složenost ~O(N)~. U rešenju dominira vremenska složenost za sortiranje svake dijagonale, pošto će sve one ukupno sadržati ~O(N)~ žetona vremenska složenost je ~O(N \log N)~ dok je memorijska složenost ~O(N)~.