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

Se da un sir $A$ cu $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$ cu $N$ numere intregi. Pentru fiecare subsecventa de lungime $K$ sa se determine minimul, iar apoi sa se calculeze suma acestor minime.

h2. Cerinta

h2. Date de intrare

Pe prima linie a fisierului $deque.in$ se afla numere $N$ si $K$ cu semnificatia din enunt. Pe urmatoarele $N$ linii se afla cate un numar intreg din sirul dat.

Pe prima linie a fisierului $deque.in$ se afla numerele $N$ si $K$ cu semnificatia din enunt. Pe urmatoarele $N$ linii se afla cate un numar intreg din sirul dat.

h2. Date de ieşire

În fişierul de ieşire $deque.out$ se va afla un singur numar intreg reprezentand suma ceruta.

In fisierul de iesire $deque.out$ se va afla un singur numar intreg reprezentand suma ceruta.

h2. Restricţii si precizari

h2. Restrictii si precizari

* $1 ≤ N ≤ 5 000 000$
* $1 ≤ K ≤ N$

* Elementele din sir vor avea valori cuprinse intre $-10 000 000$ si $10 000 000$.
* Pentru rezultat se recomanda folosirea tipurilor intregi pe $64$ de biti.

* Elementele din sir vor avea valori cuprinse intre $-10 000 000$ si $10 000 000$
* Pentru rezultat se recomanda folosirea tipurilor intregi pe $64$ de biti

h2. Exemplu

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 [sursa 'aici':job_detail/229672?action=view-source]. 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 [sursa 'aici':job_detail/229673?action=view-source], dar pe teste aleatoare ruleaza comparabil cu solutia in complexitate $O(N)$.

Un articol care trateaza pe larg subiectul $deque$-ului se gaseste 'aici':deque-si-aplicatii. O prezentare mai succinta a acestei structuri de date se gaseste in continuare.

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).

O abordare $brute-force$ in complexitate $O(N^2^)$, ce determina minimele parcurgand pe rand fiecare secventa, obtine $20$ de puncte. Sursa se gaseste 'aici':job_detail/229672?action=view-source. Aceasta solutie poate fi imbunatatita, astfel incat cand se trece de la secventa care incepe pe pozitia $i$ la cea care incepe 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 astfel de implementare se gaseste 'aici':job_detail/229673?action=view-source.

Solutia optima, in complexitate $O(N)$, foloseste o coada cu doua capete ({$double ended queue, deque$}). In aceasta structura, valorile noi pot fi inserate doar la sfarsitul cozii, in timp ce elementele existente pot fi eliminate atat pe la inceputul, cat si pe la sfarsitul deque-ului; toate aceste operatii avand loc in timp constant. Se observa ca daca exista doua elemente $A[j] &ge; A[i]$ cu $j < i$, atunci $A[i]$ va fi mereu preferat pentru minim fata de $A[j]$, pentru secventele ce incep dupa pozitia $i$ (inclusiv). Din acest motiv, la fiecare pas $i$, elementul curent $A[i]$ elimina de la finalul $deque$-ului toate elementele $&ge;$ cu el, apoi este inserat la finalul cozii. In acest fel, elementele din $deque$ sunt mentinute in ordine crescatoare, deci minimul se va afla la inceput. Se elimina minimul cat timp acesta nu mai apartine secventei curente (pozitia lui este $&le; i-K$). In final, se aduna minimul la solutie. O implementare a acestei structuri de date se gaseste 'aici':job_detail/229406?action=view-source.

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 (sursa bazata pe aceasta idee se gaseste 'aici':job_detail/229674?action=view-source). Este posibil ca folosind diverse optimizari aceasta rezolvare sa obtina $100$ puncte (motivul principal fiind cantitatea datelor de intrare).
 
O solutie de complexitate $O(N)$ foloseste o coada cu doua capete ({_double ended queue, deque_}). In aceasta structura, valorile pot fi inserate sau eliminate atat pe la inceputul, cat si pe la sfarsitul $deque$-ului, toate aceste operatii avand loc in timp $O(1)$ amortizat. Se observa ca daca exista doua elemente $A{~i~}$ si $A{~j~}$ astfel incat $A{~i~} ≤ A{~j~}$ si $i > j$, atunci $A{~i~}$ va fi mereu preferat pentru minim fata de $A{~j~}$, pentru secventele ce incep dupa pozitia $i$ (inclusiv). Din acest motiv, la fiecare pas $i$, elementul curent $A{~i~}$ elimina de la finalul $deque$-ului toate elementele mai mari sau egale cu el, apoi este inserat la finalul cozii. In acest fel, elementele din $deque$ sunt mentinute in ordine crescatoare, deci minimul se va afla la inceput. Se elimina apoi minimul de la inceputul cozii daca acesta nu mai apartine secventei curente (pozitia lui este mai mica sau egala cu $i-K$). In final, se aduna minimul la solutie. O implementare a acestei structuri de date se gaseste 'aici':job_detail/229406?action=view-source.

h2. Aplicatii

Aceasta structura de date poate fi adaptata intr-o larga varietate de probleme. In special, $deque$-ul poate fi aplicat in probleme de programare dinamica, cand trebuie determinat minimul/maximul unei functii pe un interval ce se deplaseaza treptat. De asemenea, pe baza acestei idei pot fi rezolvate si urmatoarele probleme:
 
* 'Secventa':problema/secventa
* 'Vila2':problema/vila2
* 'Sum2':problema/sum2
* 'Drept2':problema/drept2
* "Book Pile":http://acm.sgu.ru/problem.php?contest=0&problem=271
* 'Branza':problema/branza
* 'Struti':problema/struti
* 'Bcrc':problema/bcrc
* 'Copaci2':problema/copaci2
* 'Cover':problema/cover
* 'Gard':problema/gard
 

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

3510