717 Virus

[•DITzoneC]

Aici puteţi discuta despre problema Virus.

[•savim]

Evaluatorul sigur e reglat la aceasta problema? Am vazut o sursa care ia TLE cu mai putin de 1001ms.

http://infoarena.ro/job_detail/191772

[•maria_d]

salut.....iau TLE pe 2 teste cu KMP si nu stiu ce sa ii mai fac. ma poate ajuta cineva? va rog

[•pauldb]

KMP-ul nu este solutia optima. Ai putea sa faci un automat (solutia optima) sau hashuri (neoptime, dar merg mai bine ca automatele la problema asta).

[•maria_d]

poti sa imi dai vreun link de unde pot sa invat automatele?

[•CezarMocan]

Aici gasesti un articol despre automatele finite: http://infoarena.ro/automate-finite-si-kmp

[•maria_d]

automatul ala finit e mai lent decat KMP...si KMP nu imi intra in timp pe 2 teste

[•pauldb]

Articolul respectiv nu e prea grozav la partea cu automatele. Aici gasesti unul mai bun: http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf . S-a mai discutat pe infoarena despre automate aici.

[•anna_bozianu]

Mie mi s-a parut foarte bine ilustrat algoritmul Aho-Corasick aici : http://www-sr.informatik.uni-tuebingen.de/~buehler/AC/AC.html . In orice caz, ca si cum nu ar fi fost suficient de complicata problema se mai si repeta virusii (     abia cand mi-am dat seama de asta am reusit sa rezolv problema complet). Am ridicat aceasta problema la rangul de " cea mai grea problema pe care am rezolvat-o pana acum " .

[•sima_cotizo]

Mie imi seamana a problema de arhiva educationala, nu pare ca ar trebui sa faci mai mult decat sa aplici algoritmul mi-a placut, mai ales ca asa am inteles si cum merge KMP dpdv al automatelor... Oricum a fost interesant in concurs pt cei care nu stiau Aho sa scoata la iveala idei ciudate

[•blasterz]

Intra in timp si Suffix Arrays in O(nlogn)  si cautare binara

[•Dastas]

Merge si trie simplu in O(L*k)... si inca foarte rapid: http://infoarena.ro/job_detail/192070

Cred ca testele sunt cam slabe...

[•Mishu91]

Merge si trie simplu in O(L*k)... si inca foarte rapid: http://infoarena.ro/job_detail/192070

Cred ca testele sunt cam slabe...

Cata memorie ai folosit? Ca de ex pt O(L*K) memorie io iau MLE in veselie

[•Dastas]

Memorie nu-ti trebuie O(L*K) pentru trie. Iti trebuie O(K²).

[•Mishu91]

Memorie nu-ti trebuie O(L*K) pentru trie. Iti trebuie O(K²).

Pai eu folosesc O(L * K) pt ca in trie bag toate subsirurile de lungime K ale lui L. Tu cum faci? 

[•Dastas]

In trie bagi toate cele N cuvinte care ti se dau, iar apoi pentru fiecare sufix al lui L, vezi daca vreun prefix (de lungime maxim K bineinteles) al acelui sufix se gaseste in trie. Trebuie sa fii atent la cazul in care ai mai multi virusi identici, sa stii sa incrementezi pentru amandoi raspunsul. Poti sa tii o lista pentru asta.

[•Mishu91]

Mersi fain, am rezolvat-o 

[•vlasceanu]

Din pacate nu reusesc deloc sa implementez un suffix tree si am facut problema cu algoritmul de potrivire a sirurilor Knuth-Morris-Pratt as dori sa stiu si eu cum as putea optimiza acest algoritm sa imi intre pe toate testele(daca e posibil) iar daca nu este posibil as fi recunoscator sa primesc un PM cu o implementare care a luat 80-90 puncte sau chiar 100.

[•wefgef]

Nici eu nu stiu sa implementez suffix tree .

Problema se poate rezolva cu suffix array. Poti citi un articol foarte bun, care contine si implementarea algoritmului, aici.

[•vlasceanu]

Multumesc foarte mult. Acum ma simt prea obosit pentru a citi articolul o sa il citesc maine.10x again