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