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