h2(#operatii). 'Operatii':problema/operatii
Problema admite multe rezolvari si a fost propusa pentru o departajare a concurentilor. Un prim algoritm ar fi selectarea la fiecare pas a secventei de lungime maxima ce contine numai elemente nenule si decrementarea cu o unitate a tuturor elementelor secventei. Procedeul se repeta cat timp exista o secventa cu elemente nenule (cat timp vectorul nu este nul). Deoarece la fiecare pas s-a selectat secventa de lungime maxima, numarul final de operatii va fi minim posibil. Aceasta solutie obtine 20-40 de puncte, in functie de prezenta optimizarilor.

Complexitatea optima in care se poate rezolva problema este {$O(N)$} si exista mai multe rezolvari diferite ce au aceasta complexitate. Una din rezolvari este urmatoarea: fie $MAX$ maximul elementelor din vectorul {$v$}. Retinem $MAX$ liste, in a $i$-a lista avand memorate pozitiile din vector pe care apare numarul $i$. Pornim de la vectorul nul si inseram pe rand numerele {$1$}, {$2$}, ... {$MAX$}. Calculam la fiecare pas $i$ numarul de intervale in care impart primele $i$ numere vectorul {$v$}, rezultatul final fiind suma numerelor de intervale de la fiecare pas.
De exemplu, pentru vectorul {$v = (0 1 4 2 4 1 3)$} se procedeaza in felul urmator: plecam de la vectorul nul cu $7$ elemente. Introducem valoarea $0$ pe pozitia $1$ si s-a format un "interval" cu pozitii care nu au fost inca completate ( pozitiile $2-7$ ). Introducem numarul $1$ pe pozitiile $2$ si $6$ si se formeaza $2$ intervale: pozitiile $3-4-5$ si $7$. Introducem elementul $2$ pe pozitia $4$ si se formeaza $3$ intervale, cate un interval pe pozitiile {$3$}, $5$ si {$7$}, etc. In final se aduna numarul de intervale de la fiecare pas si se afiseaza rezultatul obtinut. Procedand in acest fel, vom sti sigur ca numarul de operatii folosite este minim, la pasul $i$ incrementandu-se cu o unitate toate intervalele obtinute.
Ca sa aflam in {$O(1)$} la fiecare pas cate intervale avem, tinem un vector caracteristic {$uz$}, unde {$uz{~i~}$} este $1$ daca si numai daca numarul de pe pozitia i a fost marcat. Fie $nr_interval$ numarul curent de intervale. Distingem 4 cazuri:

Problema se poate rezolva in complexitate liniara si exista mai multe rezolvari diferite ce au aceasta complexitate. Una din rezolvari este urmatoarea: fie $MAX$ maximul elementelor din vectorul {$v$}. Retinem $MAX$ liste, in a $i$-a lista avand memorate pozitiile din vector pe care apare numarul $i$. Pornim de la vectorul nul si inseram pe rand numerele {$1$}, {$2$}, ... {$MAX$}. Calculam la fiecare pas $i$ numarul de intervale in care impart primele $i$ numere vectorul {$v$}, rezultatul final fiind suma numerelor de intervale de la fiecare pas.
De exemplu, pentru vectorul {$v = (0 1 4 2 4 1 3)$} se procedeaza in felul urmator: plecam de la vectorul nul cu $7$ elemente. Introducem valoarea $0$ pe pozitia $1$ si s-a format un "interval" cu pozitii care nu au fost inca completate ( pozitiile $2-7$ ). Introducem numarul $1$ pe pozitiile $2$ si $6$ si se formeaza $2$ intervale: pozitiile $3-4-5$ si $7$. Introducem elementul $2$ pe pozitia $4$ si se formeaza $3$ intervale, cate un interval pe pozitiile {$3$}, $5$ si {$7$}, etc. In final se aduna numarul de intervale de la fiecare pas si se afiseaza rezultatul obtinut. Procedand in acest fel, vom sti sigur ca numarul de operatii folosite este minim: daca la pasul $i$ avem un anumit numar de intervale, aplicam operatia specificata in problema o data pentru fiecare interval.
Ca sa aflam in {$O(1)$} la fiecare pas cate intervale avem, tinem un vector caracteristic {$uz$}, unde {$uz{~i~}$} este $1$ daca si numai daca numarul de pe pozitia $i$ a fost inserat (marcat). Fie $nr_interval$ numarul curent de intervale. Distingem 4 cazuri:

* marcam pozitia $i$, si pozitiile $i-1$ si $i+1$ sunt nemarcate => $nr_interval$ creste cu o unitate
* marcam pozitia $i$, pozitia $i-1$ nemarcata si $i+1$ marcata => $nr_interval$ nu se modifica
* marcam pozitia $i$, pozitia $i+1$ nemarcata si $i-1$ marcata => $nr_interval$ nu se modifica
* marcam pozitia $i$ si pozitiile $i-1$ si $i+1$ sunt marcate => $nr_interval$ scade cu o unitate

Aceasta solutie este foarte simplu de implementat si obtine 100 de puncte.

Aceasta solutie este foarte simplu de implementat si obtine 100 de puncte.
 
O solutie alternativa si cu o implementare mult mai concisa a fost oferita de "Bitis Gabriel":http://infoarena.ro/utilizator/gabitzish1. Aceasta se bazeaza pe urmatoarea observatie: capetele stangi ale secventelor ce vor fi selectate pentru incrementare vor fi doar acele pozitii cu valoare strict mai mare decat pozitia precedenta. Evident, celelalte pozitii vor fi acoperite de secvente care pornesc mai in stanga. De exemplu, pentru vectorul de mai sus, se vor selecta doar secvente ce incep cu valorile {$1$}, {$4$}, {$4$}, {$3$}. Pentru a afla numarul minim de operatii, vom tine un contor pe care il vom creste de fiecare data cand {$v[i]>v[i-1]$} cu valoarea {$v[i]-v[i-1]$}, pentru fiecare {$i$} cuprins intre {$1$} si {$N$}. Conventional {$v[$}{$0]=0$}. Solutia poate fi optimizata (desi nu este necesar pentru 100 de puncte) pentru a nu retine tot vectorul, ci numai ultimii 2 termeni. Complexitatea obtinuta este {$O(N)$}.