cel mai mare cmlsc

[cristi8]

fie A multimea celor mai lungi subsiruri comune dintre 2 siruri.
cum determin cel mai mare (in ordine lexicografica) element din A ?

s-a dat la OJI 2002, clasa 10a. (problema COD)
 
1 <= n,m <= 200
..eu de-abia am scos un program functional de complexitate O(n^3) care nici nu l-am demonstrat (de obosit si lenes ce sunt), dar se pare ca trece toate testele.
se poate mai repede ?
voi cum faceti ?

[•silviug]

Se face algoritmul clasic de CLSC - O(N^2) - vezi Cormen. Sa-l determini pe cel mai mic (in cazul problemei de fata) faci dinamica invers: de la sfarsitul sirurilor catre inceputul lor. Asta iti va permite sa faci decizii astfel incat sa-l scoti pe cel minim. Daca mai vrei detalii mai posteaza, dar gandeste-te .. tre sa iasa

Spor la treaba!

[andreit1]

Nu pare foarte greu in O(n^2). Faci un cmlsc de la coada fiecarui sir si apoi cauti cand reconstituiesti sa ai cea mai mare litera posibila la fiecare pas. Nu ar trebui sa puna probleme...
[later edit] Vad ca a postat Silviu in timp ce scriam eu. Daca apare vrun moderator sa imi stearga si mie postul...

[cristi8]

invers am facut dinamica oricum, sa am la sfarsit cele mai semnificative valori.

eu am zis ca nu stii unde sa te duci cand reconstitui solutia astfel incat sa o obtii pe cea mai mare lexicografic.

sa zicem ca c[0][0] = 5 (lungimea lui).
si a[0] != b[0] (nu e litera comuna pe prima pozitie).
si c[0][1] = c[1][0] = 5.

unde te duci ? in (0,1) sau (1,0) ? poate nici acolo nu e litera comuna, dar tot mergand, in final se ajunge la 2 LCS-uri egale ca lungime, dar unul mai mic ca celalalt.


eu cand am construit c[j], cand
a != b[j] si c[i+1][j] == c[j+1], am verificat ordinea lexicografica a celor 2 subsiruri (O(n), retinand si tatii in alte 2 matrici)

[•silviug]

Nu mai stiu exact ce faceam.. dar probabil daca tii pentru fiecare pozitie in matricea de reconstituire si cel mai mic tata (prima litera comuna la care ajungi luand-o pe acolo) e de ajuns, din moment ce tu iei cifrele in ordine, de la ce mai semnificativa la cea mai putin semnificativa.

Vei obiecta spunand ca si tatii pot fi egali si atunci ce faci ? Intuitia imi spune ca atunci poti lua orice decizie ca tot acolo ajungi la un moment dat

Incearca asa.. poate merge

Silviu