260 Note

[•filipb]

Aici puteţi discuta despre problema Note.

[•cos_min]

cam ce complexitate ar trebui pt problema asta ? eu am scos O(n*m*v)  si scot 70 de pcte, restul testelor TLE

[u-92]

O(n*m)

[Tabara Mihai]

Si eu iau tot 70 cu O( n*m*v ).

Imi poate explica cineva cum a facut in O( n*m )? 

[•sims_gl]

Faci o dinamica in c[ i ][ j ] in care tii numarul de transformari necesare ca sa obtii un sir de lungime i, care se brodeaza peste primele i note ale partiturii, din primele j note ale solfegiului.
O sa ai nevoie de o matrice binara [n*v], ca sa afli repede daca o anumita nota de pe o pozitie din solfegiu exista pe aceeasi pozitie si pe partitura. Apoi incerci sa obtii c[ i ][ j ] din:
c[ i ][ j - 1 ] - in cazul in care adaugi o nota
c[ i - 1 ][ j ] - in cazul in care scoti o nota
c[ i - 1 ][ j - 1 ] - in cazul in care modifici o nota (sau daca nota j din solfegiu exista pe pozitia i in partitura)

Sper ca intelegi . Succes!

[•cos_min]

10x am reusit sa iau in sfarsit 100 

[•stefys]

http://en.wikipedia.org/wiki/Levenshtein_distance

[•ctlin04]

Cei care au trecut de la 40 la 100, va rog frumos un hint 

LE: S-a rezolvat uitasem sa fac initializarea pe linia si coloana 0 

[•mihai.alpha]

Are idee cineva ce au testele 2 si 10, pt ca sunt singurele pe care iau Incorect.

Edit: Am reusit sa iau 100p. Nvm oricum nu ma asteptam sa raspunda cineva (Forumul pare mort).