Deci, putem aprinde becurile $[0,X-1]$ daca exista un drum de la nodul $0$ la nodul $X$. Raspunsul la problema va fi distanta minima a unui astfel de drum, ceea ce putem afla cu o 'parcurgere in latime':problema/bfs (deoarece toate muchiile au costul $1$).

Solutia are complexitatea $O(N + M)$.
 

h1. 'Raci':problema/raci

Avand un sir de $N$ cuvinte trebuie sa aflam un subsir care sa respecte proprietatile din enunt.
O prima solutie foloseste programarea dinamica si este asemanatoare celei de la aflarea 'celui mai lung subsir crescator':problema/scmax, difera doar conditia de potrivire a sirurilor.
 
Ne definim o stare $dp[i]$ = cel mai lung subsir care respecta conditiile si se termina in cuvantul $i$. Cand calculam $dp[i]$, incercam sa gasim un cuvant $j < i$, $j >= i - K$ astfel incat ultima litera din cuvantul $j$ este egala cu prima litera din cuvantul $i$.
Valoarea lui $dp[i]$ va fi maximul dintre toate $dp[j]$ care respecta conditia, la care adaugam $1$.
 
Din pacate, o astfel de solutie are complexitatea $O(N * K)$, ceea ce depaseste cu mult limita de timp.
 
Putem imbunatati acest algoritm. Notam prima litera a cuvantului $i$ cu $p$. Observam ca atunci cand potrivim sirurile, cautam doar cuvintele care se termina cu litera $p$. O idee ar fi sa creem o lista de indici pentru fiecare litera. Notam lista pentru litera $p$ cu $L[p]$. Vom cauta in $L[p]$ indicii $j >= i - K$ si luam maximul dintre aceste valori. Putem considera aceste liste ca fiind cozi cu doua capete si putem actualiza maximul din toate cele 26 cozi pe masura ce adaugam indicii (vezi descriere 'deque':problema/deque). Actualizarile au complexitatea $O(N)$ amortizat.
 
Acum solutia are complexitatea optima $O(N)$.
 

h1. 'Suma5':problema/suma5
Problema este o aplicatie clasica a arborilor de intervale cu lazy propagation. Fiecare nod al arborelui de intervale va retine informatii legate de: