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