h2. 'Obj':problema/obj
Vom porni de la o solutie avand complexitatea $O(N*K)$. Vom calcula $win[ 0 ][i]$ = $1$, daca gramada contine $i$ obiecte, castigatorul trebuie sa stranga un numar par de obiecte, iar jucatorul aflat la mutare are strategie sigura de castig, sau $0$, daca jucatorul aflat la mutare nu are strategie sigura de castig. $win[ 1 ][i]$ va reprezenta acelasi lucru, cu diferenta ca cel care castiga jocul este cel care aduna un numar impar de obiecte. Avem $win[ 0 ][ 0 ] = 1$ si $win[ 1 ][ 0 ] = 0$. Pentru fiecare valoare a lui $i$ de la $1$ la $N$, variem numarul de obiecte pe care le ia jucatorul aflat la mutare si, in functie de paritatea acestui numar, paritatea lui $i$ si paritatea numarului de obiecte ce trebuie luate pentru a castiga jocul, se determina starile in care se poate ajunge; ca orice alt joc rezolvat prin programare dinamica, jucatorul aflat la mutare va avea strategie sigura de castig daca cel putin una din starile in care poate ajunge este o stare de pierdere pentru jucatorul ce se va afla la mutare in continuare (adica adversarul).
Vom porni de la o solutie avand complexitatea $O(N*K)$. Vom calcula $win[ 0 ][ i ]$ = $1$, daca gramada contine $i$ obiecte, castigatorul trebuie sa stranga un numar par de obiecte, iar jucatorul aflat la mutare are strategie sigura de castig, sau $0$, daca jucatorul aflat la mutare nu are strategie sigura de castig. $win[ 1 ][ i ]$ va reprezenta acelasi lucru, cu diferenta ca cel care castiga jocul este cel care aduna un numar impar de obiecte. Avem $win[ 0 ][ 0 ] = 1$ si $win[ 1 ][ 0 ] = 0$. Pentru fiecare valoare a lui $i$ de la $1$ la $N$, variem numarul de obiecte pe care le ia jucatorul aflat la mutare si, in functie de paritatea acestui numar, paritatea lui $i$ si paritatea numarului de obiecte ce trebuie luate pentru a castiga jocul, se determina starile in care se poate ajunge; ca orice alt joc rezolvat prin programare dinamica, jucatorul aflat la mutare va avea strategie sigura de castig daca cel putin una din starile in care poate ajunge este o stare de pierdere pentru jucatorul ce se va afla la mutare in continuare (adica adversarul).
Solutia $O(N*K)$ se poate optimiza la $O(N)$, observand ca, de fapt, pentru starile in care poate ajunge jocul dupa efectuarea unei mutari nu ne intereseaza numarul exact de obiecte ramase, ci paritatea acestui numar. Pe masura ce mergem cu $i$ de la $1$ la $N$ si calculam valorile mentionate anterior, retinem si ultima valoare a lui $i$ ce corespunde unei stari de tip $(x,y,z)$, unde $x$ reprezinta pariatea numarului de obiecte pe care trebuie sa le ia unul din cei doi jucatori pentru a castiga jocul, $y$ reprezinta paritatea numarului de obiecte aflate in gramada, iar $z$ retine daca jucatorul aflat la mutare are sau nu are strategie sigura de castig in conditiile date de $x$ si $y$. Memorand astfel de triplete, problema de decizie pentru un numar de obiecte $i$ se reduce la a verifica daca ultimul numar de obiecte de gramada (ultima pozitie) ce corespunde unei stari de un anumit tip care ar determina existenta unei strategii sigure de castig pentru pozitia $i$, se afla in intervalul $[i-K,i-1]$ (adica acel numar de obiecte in gramada poate fi obtinut dintr-o singura mutare).
Solutia $O(N*K)$ se poate optimiza la $O(N)$, observand ca, de fapt, pentru starile in care poate ajunge jocul dupa efectuarea unei mutari nu ne intereseaza numarul exact de obiecte ramase, ci paritatea acestui numar. Pe masura ce mergem cu $i$ de la $1$ la $N$ si calculam valorile mentionate anterior, retinem si ultima valoare a lui $i$ ce corespunde unei stari de tipul $(x,y,z)$, unde $x$ reprezinta pariatea numarului de obiecte pe care trebuie sa le ia unul din cei doi jucatori pentru a castiga jocul, $y$ reprezinta paritatea numarului de obiecte aflate in gramada, iar $z$ retine daca jucatorul aflat la mutare are sau nu are strategie sigura de castig in conditiile date de $x$ si $y$. Memorand astfel de triplete, problema de decizie pentru un numar de obiecte $i$ se reduce la a verifica daca ultimul numar de obiecte din gramada (ultima pozitie $j < i$) ce corespunde unei stari de un anumit tip care ar determina existenta unei strategii sigure de castig pentru pozitia $i$, se afla in intervalul $[i-K,i-1]$ (adica acel numar de obiecte in gramada poate fi obtinut dintr-o singura mutare).
Uitandu-ne pe valorile obtinute pentru fiecare $i$ de la $1$ la $N$, observam o regula care reduce complexitatea rezolvarii problemei la $O(1)$. Pentru $K$ par, daca $N mod (K + 2) = 1$, castigatorul jocului va fi Ionel (al doilea jucator); in caz contrar, castigatorul va fi Gigel (primul jucator). Pentru $K$ impar, daca $N mod (2 * K + 2) = 1$, atunci castigatorul este Ionel (al doilea jucator); in caz contrar, castigatorul va fi Gigel (primul jucator).
