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$:

* $bst[i][j] = Min { bst[i - 1][j - T], bst[i - 1][j - T + 1], ..., bst[i - 1][j], ..., bst[i - 1][j + T - 1], bst[i - 1][j + T] }$.

Metoda directă şi, aparent eficientă, constă în folosirea unui arbore de intervale pentru aflarea acestui minim. Însă, intervalul se deplasează, dacă vom considera indicii $j$ în ordine $1$, $2$, ..., $N$, constant spre dreapta, fiind reprezentat de un şir de valori de lungime constantă în care noile elemente se introduc prin dreapta şi altele se elimină prin stânga. Vom folosi un deque şi vom proceda ca în problemele precedente, eliminând poziţiile care nu sunt candidate la soluţie.

Metoda directă şi, aparent eficientă, constă în folosirea unui arbore de intervale pentru aflarea acestui minim. Însă, intervalul se deplasează, dacă vom considera indicii $j$ în ordine $1$, $2$, ..., $N$, constant spre dreapta, fiind reprezentat de un şir de valori de lungime constantă în care noile elemente se introduc prin dreapta şi altele se elimină prin stânga. Vom folosi un deque de lungime $2 * T$ şi vom proceda ca în problemele precedente, eliminând poziţiile care nu sunt candidate la soluţie.

p=. !deque-si-aplicatii?bcrc.png 40%!