|
Titlul: Problema Cuvinte, ONI 2004 clasa a X-a Scris de: George Popoiu din Martie 04, 2010, 21:41:37 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 : Citat 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 ! :) Titlul: Răspuns: Problema Cuvinte, ONI 2004 clasa a X-a Scris de: Cosmin Negruseri din Martie 06, 2010, 16:10:17 Care parte nu o intelegi? Algoritmul in O(n * m)? Sau imbunatatirea lui la O(n * k)?
Titlul: Răspuns: Problema Cuvinte, ONI 2004 clasa a X-a Scris de: George Popoiu din Martie 06, 2010, 17:40:48 Imbunatatirea ...
Titlul: Răspuns: Problema Cuvinte, ONI 2004 clasa a X-a Scris de: Cosmin Negruseri din Martie 06, 2010, 21:39:54 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)
Titlul: Răspuns: Problema Cuvinte, ONI 2004 clasa a X-a Scris de: George Popoiu din Martie 07, 2010, 08:01:28 Da, acum am inteles, multumesc ! :thumbup:
|