h2(#Inception). 'Inception':problema/inception
 

Autor: stud. Ştefan Negruş, Facultatea de Informatică Iaşi, Universitatea Al. I. Cuza
Descrierea soluţiei (stud. Ştefan Negruş)

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 enunt:

Exemplul din enunţ:

{! problema/inception?incp.png 40% !}

{! moisil-2015/inception?incp.jpg 35% !}

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.

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^)

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^)

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)