Tester

Vom transforma graful rezultat din starile si tastele date astfel: fiecarei taste i ii vom asocia un nod i in noul graf. Oricare doua taste i si j ce pot aparea una dupa alta (sunt de forma ( x, y ) si ( y, z ) ) le vom lega in noul graf cu o muchie orientata de la i la j. Se observa ca in noul graf un combo este reprezentat de o muchie. Faptul ca dorim sa obtinem o secventa cu toate combourile exact odata, adica ce contine toate muchiile exact odata, ne duce cu gandul la o parcurgere euleriana a noului graf. Inainte de a incerca sa construim o parcurgere euleriana a grafului trebuie sa transformam graful intr-unul eulerian. Pentru aceasta procedam in felul urmator. Fie GINi numarul de muchii care intra in nodul i si GOUTi numarul de muchii care ies din nodul I. Stim ca intr-un graf eulerian GINi trebuie sa fie egal GOUTi. Cream un nou nod R din care si spre care tragem cate muchii sunt necesare pentru a satisface conditia de egalitate intre GINi si GOUTi pentru fiecare nod i. Acum putem sa construim un ciclu eulerian incepand din nodul R. Secventa creata este exact secventa de taste ce vor fi apasate de Paraschiva. Orice trecere prin nodul R va reprezenta o resetare a jocului (ea denota trecerea printr-o muchie inexistenta din graf), mai putin prima si ultima care nu sunt treceri ci doar marcheaza inceputul si sfarsitul secventei. Secventa rezultata respecta conditia ca fiecare muchie sa fie parcursa exact odata (fiecare combo sa apara exact odata) si numarul de resetari al jocului va fi minim (nu se poate obtine o secventa cu mai putine resetari din cauza naturii grafului).

Solutia are complexitate N * M.