infoarena

Aici puteţi discuta despre problema Ratina (http://infoarena.ro/problema/ratina).

are careva idee cum sar putea face compararea a doua cuvinte fara parcurgere??mie mi se pare trebuiesc comparate fiecare pereche de cate doua cuvinte....totuji...nu cred ca aceasta este solutia optima....oricum mai muncesc la ea... :weightlift:

Rezolvarea oficiala foloseste un trie.

totusi...parerea mea este ca si parcurgerea trie-ului se face tot liniar...sau poate ma insel.... :-k

A luat cineva 100 cu suffix arrays in O(N log N) ? Eu unul am 20.

LE: Sa modific putin complexitatea: O(L log L + M log L), unde L e suma lungimilor tuturor cuvintelor.

Eu am luat 100 cu o sortare a cuvintelor in O(C*N*logN), unde C este lungimea maxima a unui cuvant. Nu cred ca asta se poate numi bulaneala, pentru ca exploatez la maxim enuntul. Nu pot fi multe cuvinte decat daca sunt scurte si nu pot fi lungi decat daca sunt putine. (1 ≤ suma lungimilor tuturor cuvintelor ≤ 200000) :thumbup:

Dupa ce ai trie-ul construit poti cauta binar nodul care e stramos pentru toate frunzele cuvintelor din query sau poti aplica un algoritm de Lowest Common Ancestor.

Poate sa-mi spuna si mie cineva la ce se poate folosi sortarea cuvintelor pls ? Adik, cu ce ar schimba asta problema si te-ar ajuta sa te incadrezi in timp ?

Sortezi cuvintele si calculezi gradul de asemanare intre oricare 2 cuvinte consecutive. Pe urma, o interogare pentru 2 cuvinte devine un query pentru valoarea minima intre 2 pozitii in vectorul gradelor calculate anterior. La mine s-a incadrat in timp foarte lejer, dar iti sugerez sa implementezi si solutia cu trie. Si asa inveti dublu dintr-o singura problema. :thumbup:

Aveti va rog un test mai nasol... ca pe toate testele mele da bine, dar iau numai 40  ](*,)

L.E : S-a rezolvat  :yahoo:

I`au doar 15 pct cu wa . Am folosit un trie si apoi am cautat raspunsul binar :-?

Cum pot calcula lungimea celui mai lung prefix a n cuvinte dintr-un trie? ](*,).O mica sugestie mi-ar fi de folos...