Problema Cuvinte, ONI 2004 clasa a X-a

[•popoiu.george]

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=922

Problema 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 ! 

[•Cosmin]

Care parte nu o intelegi? Algoritmul in O(n * m)? Sau imbunatatirea lui la O(n * k)?

[•popoiu.george]

Imbunatatirea ...

[•Cosmin]

Ideea e ca orice solutie pentru edit distance corespunde unui drum de la 0,0 la n-1,m-1. La fiecare pas poti ajunge de la i,j la i+1,j; i,j+1 sau i+1,j+1 cu un anumit cost. Acum un drum ce trece prin i,i + k + 1 va avea costul mai mare decat k, incearca sa vezi de ce, la fel si pentru i, i - k - 1. Astfel poti sa nu mai calculezi valorile respective si iti vor ramane de calculat pe fiecare linie i valorile de la indicele i - k pana la i + k. Asa obtii un algoritm de complexitate O(n * 2k)

[•popoiu.george]

Da, acum am inteles, multumesc !