Problema se rezolvă prin programare dinamică. Soluţia se bazează pe observaţia de mai jos. Considerăm $P$-ul fixat şi notăm cu $stare(X, Y)$ poziţia de start în care avem $X$ pietre şi numărul maxim de pietre care se pot lua la prima mutare este $Y$.

_Observaţia 1_: Dacă există strategie sigură de câştig pentru $stare(X, Y)$ atunci există şi pentru orice $stare(X, T)$ cu $T ≥ Y$.

_Observaţia 1_: „Dacă există strategie sigură de câştig pentru $stare(X, Y)$ atunci există şi pentru orice $stare(X, T)$ cu $T ≥ Y$.”

De ce? Pentru că orice mutare validă pentru $stare(X, Y)$ este validă şi pentru $stare(X, T)$. Având această observaţie notăm cu $MinY[X] = Y$, $Y$ minim astfel încât avem strategie de câştig pentru $stare(X, Y)$.

_Observaţia 2_: $stare(X, Y)$ este pierzătoare dacă şi numai dacă $Y < MinY[X]$.

_Observaţia 2_: „$stare(X, Y)$ este pierzătoare dacă şi numai dacă $Y < MinY[X]$.”

Aceasta reiese din definiţia lui $MinY[X]$.

De aici se naşte prima soluţie, care este implementarea directă a recurenţei. Deşi complexitatea acesteia pare a fi $O(N^2^)$ ea se comportă foarte bine pentru $N ≤ 500 000$. Aşadar, această soluţie acoperă aproximativ $50%$ din testele de intrare. Printr-o rafinare a acestei soluţii se obţine un algoritm de complexitate $O(N)$. Rafinarea se bazează pe:

_Observaţia 3_: Să presupunem că dorim să calculăm $MinY[X]$. Facem următoarea afirmaţie: orice poziţie "rea" pentru $X$ (în care dacă mutăm pierdem) va fi "rea" şi pentru $X + 1$.

_Observaţia 3_: „Să presupunem că dorim să calculăm $MinY[X]$. Facem următoarea afirmaţie: orice poziţie "rea" pentru $X$ (în care dacă mutăm pierdem) va fi _rea_ şi pentru $X + 1$.”

Acest lucru este simplu de observat dacă privim ce înseamnă că o poziţie $Q$ e rea pentru $X$:

h3(#problema-6). Problema 6: 'Bcrc':problema/bcrc (Stelele Informaticii 2006)

(deque la programare dinamica)
...

bq. Se consideră $N$ camere, numerotate de la $1$ la $N$, aşezate în cerc. Iniţial (la momentul de timp 0), ne aflăm în camera $1$. În fiecare moment de timp, putem alege să rămânem în camera în care ne aflăm sau să ne deplasăm într-o cameră vecină într-o unitate de timp. Se dă o listă de $M$ cutii ce conţin bomboane prin $T$, $C$ şi $B$: cutia apare la momentul $T$ în camera $C$ şi conţine $B$ bomboane. Cutia va dispărea la momentul $T + 1$.
Cerinţă: Cunoscând numărul de camere din labirint şi momentele de timp la care apar cutiile cu bomboane, determinaţi care este numărul maxim de bomboane pe care le putem culege.
Restricţii: $3 ≤ N ≤ 2 048$, $0 ≤ M ≤ 50 000$, $1 ≤ T ≤ 1 000 000 000$, $1 ≤ C ≤ N$, $1 ≤ B ≤ 9 999$.
 
h3. Soluţie:
 
Soluţia foloseşte metoda programării dinamice.
 
 

h2(#concluzii). Concluzii