infoarena

Aici puteţi discuta despre problema Note (http://infoarena.ro/problema/note).

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

O(n*m)

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

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

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!

10x am reusit sa iau in sfarsit 100  :yahoo:

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

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

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