Urmatoarea problema a fost data la ONI in 2004 si am gasit-o postata pe campion.
http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=922Problema este ca nu reusesc sa imi explic solutia data ( complexitate O(N*K) ), care suna cam asa :
Cu toţii cunoaştem dinamica clasică a distanţei de editare (dacă nu, vezi Cormen). Problema e că rezolvarea clasica este O(N^2) (de fapt N*M, dar N si M sunt foarte apropiate ca valori). Noi trebuie să rezolvam insa in O(K*N).
Pentru aceasta observam ca din toata acea matrice nu ne trebuie decat K elemente in jurul diagonalei principale.
Orice element aflat in afara acestei benzi poate fi considerat infinit, pentru ca ajungerea in colt necesita cel putin K incrementari, deci rezultatul final va fi mai mare decat K.
Daca ati inteles rezolvarea, v-as ruga sa mi-o explicati si mie.
Multumesc !