test

Autor: stud. Ştefan Negruş, Facultatea de Informatică Iaşi, Universitatea Al. I. Cuza
Descrierea soluţiei (stud. Ştefan Negruş)
 
Iniţial avem nevoie de câteva observaţii ce ne vor ajuta în descrierea soluţiilor următoare: din faptul că nu se folosesc poziţiile [i][j] în care sunt visate elementele iar un element nu poate fi visat de mai multe ori, putem deduce că nu avem nevoie să reţinem matricele sub forma de tablou bidimensional si nici să reţinem elementele care s-au modificat. Astfel, orice matrice este reprezentată doar prin id-ul şi coeficientul sau (informaţii suplimentare în soluţi).
 
Astfel, problema se reduce la forma următoare: fiecare matrice este echivalentul unui element într-o listă simplu înlănţuită. Unele liste se pot intersecta cu alte liste.
 
Exemplul din enunţ:
 
 
Totodată trebuie să ţinem cont de operaţiile de update. O operaţie de adăugare a unei valori la coeficienţii a nr matrici este echivalentă acum cu adăugarea unei valori la fiecare element dintr-o secvenţă, de lungime nr, de elemente inlănţuite.
 
Listele pot fi reţinute static: next[i] = indicele elementului ce urmează dupa elementul cu indice i
 
Sau pot fi reţinute dinamic: next[i] = pointer la primul element din secvenţa de elemente care începe la elementul cu indice i şi se termina la elementul cu indice 1.
 
Solutie – 20p – Complexitate(N)
Observăm că daca am avea o singură listă care nu este intersectată de o altă listă, elementele sunt numerotate crescător de la 1 şi putem face update-ul pe secvenţa în O(1): coeficient[id] += val, coeficient[id – nr] –= val. Iar la sfârşit calculăm valoarea finală pentru fiecare matrice.
 
Solutie – 40p – Complexitate (N^2)
La o operaţie de adaugare de element se adaugă/creează elementul şi se face legatura necesară. Operaţia de tip update pe secventaţă este echivalentă cu parcurgerea secvenţei ce începe cu elementul id şi adaugarea valorii val la nr elemente. Coeficientul fiecărui element, obţinut dupa efectuarea tuturor operaţiilor, este final.
 
Solutie – 60p – Complexitate(N^2)
Putem combina foarte usor soluiile precedente pentru a prinde mai multe cazuri. Trebuie să ştim dacă avem cel puţin o matrice în care există mai mult de 1 element visat. Iniţial folosim strategia de la soluţia de 20p descrisă mai sus şi memorăm într-un vector pentru fiecare element câte elemente sunt visate în matricea respectivă. Dacă în urma unui eveniment de tip 1 o matrice conţine cel puţin 2 elemente putem calcula valorile parţiale ale coeficienţilor pentru toate elementele până în acel moment şi în continuare aplicăm strategia descrisă la soluţia ce obţine 40p.
 
Solutie – 80p – Complexitate(N*sqrtN)
Atunci când avem mai multe liste trebuie să accesam eficient elementul la distanţa nr fata de id. Putem face asta dacă din fiecare element reţinem elementul la distanţa sqrt(N) faţă de elementul curent. Atunci când trebuie să găsim elementul la distanţa nr facem nr/sqrt(N) paşi “mari” de la un element la altul, înspre elementul 1, elemente care sunt la distanţa sqrt(N) între ele. La sfârşit mai facem maxim sqrt(N)–1 paşi “mici” de distanţa 1 până la elementul căutat. Numărul total de paşi va fi de ordinul O(sqrtN).
 
Solutie – 100p – Complexitate(N*logN)
Putem îmbunătăţi soluţia de mai sus memorând pentru fiecare element al 2^k (k din [1,20]) element înspre elementul cu indicele 1. Astfel numărul de paşi va fi de ordinul numărului de biţi cu valoarea 1 din reprezentarea binară a numărului nr care este de ordinul O(logN).
 
De menţionat că pentru ultimele 2 soluţii calcularea valorilor finale ale coeficienţilor se face la sfârşit. Trebuie să procesăm mereu elementele de la capetele listelor spre elementul 1. Echivalent cu a parcurge matricile începând cu cele care nu au alte matrice formate în interior. Putem face asta cu o coadă în care punem iniţial capetele listelor şi procesăm fiecare element pe rând astfel: adăugam valoarea din elementul curent la următorul element din lista şi dacă acel element a devenit capătul unei liste (nu se află în interiorul niciunei liste) îl adăugăm în coadă. Afişăm răspunsul pentru fiecare id cerut în O(1).