infoarena

Aici puteţi discuta despre problema Virus (http://infoarena.ro/problema/virus).

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

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

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).

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

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

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

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 (http://infoarena.ro/forum/index.php?topic=3005.0).

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 " .

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 :D

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

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

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?  :?

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.

Mersi fain, am rezolvat-o  =D>

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.

Nici eu nu stiu sa implementez suffix tree :P.

Problema se poate rezolva cu suffix array. Poti citi un articol foarte bun, care contine si implementarea algoritmului, aici (http://infoarena.ro/siruri-de-sufixe).

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