== include(page="template/taskheader" task_id="deque") ==

Se da un sir de $N$ numere intregi. Pentru fiecare subsecventa de lungime $K$, sa se determine minimul, iar apoi sa se calculeze suma acestor minime.

Se da un sir $A$ de $N$ numere intregi. Pentru fiecare subsecventa de lungime $K$, sa se determine minimul, iar apoi sa se calculeze suma acestor minime.

h2. Cerinta

h2. Indicatii de rezolvare

O abordare $brute-force$ in complexitate $O(N^2^)$, ce determina minimele parcurgand pe rand fiecare secventa, obtine $20$ de puncte. Aceasta solutie poate fi imbunatatia, astfel incat cand se trece de la secventa care incepe pozitia $i$ la cea de pe pozitia $i+1$, sa se recalculeze minimul doar daca acesta se afla pe pozitia $i$ (acesta dispare din secventa curenta). Complexitatea ramane $O(N^2^)$ si aceasta idee obtine $30$ de puncte, dar pe teste aleatoare ruleaza comparabil cu solutia in complexitate $O(N)$.
 
O alta idee de rezolvare se bazeaza pe faptul ca pentru a trece de la secventa care incepe pe pozitia $i$ la cea care incepe pe pozitia $i+1$ dispare elementul de pe pozitia $i$ si apare unul nou pe pozitia $i+K$. Pornind de la aceasta observatie, putem folosi un 'heap':problema/heapuri pentru a efectua stergerile si inserarile in complexitate $O(logN)$ si pentru a afla minimul pentru un interval in $O(1)$. In acest caz, complexitatea totala este $O(NlogN)$ si o astfel de abordare ar trebui sa obtina $60$ de puncte. Este posibil ca folosind diverse optimizari, aceasta rezolvare sa obtina $100$ puncte (motivul principal fiind cantitatea datelor de intrare).
 
Solutia optima, in complexitate $O(N)$, foloseste o coada cu doua capete ({$Double ended queue, deque$}). Valorile noi pot fi inserate doar la sfarsitul cozii, in timp ce elementele existente pot fi eliminate atat de la inceputul, cat si de la sfarsitul deque-ului; toate aceste operatii avand loc in timp constant. Se observa ca daca exista doua elemente $A[i] &ge; A[j]$ cu $i < j$, atunci $A[j]$ va fi mereu preferat pentru minim fata de $A[i]$ pentru secventele ce incep dupa pozitia $j$ (inclusiv). Din acest motiv, la fiecare pas $i$, elementul curent $A[i]$ elimina de la finalul $deque$-ului toate elementele &ge; cu el, iar apoi este si el, la ranadul lui, inserat in structura. In acest fel, elementele din $deque$ sunt mentinute in ordine crescatoare, deci minimul se va afla la inceput. Se elimina minimul, cat timp acest nu mai apartine secventei curente (pozitia este $&le; i-K$). In final, se aduna minimul la solutie.
 

h2. Aplicatii
== include(page="template/taskfooter" task_id="deque") ==