Revizia anterioară Revizia următoare
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 operatii necesar pentru a ajunge de la vectorul
