|
•filipb
|
 |
« : Martie 26, 2007, 13:45:07 » |
|
Aici puteţi discuta despre problema Ratina. |
|
|
|
|
Memorat
|
|
|
|
•vanila0406
De-al casei
Karma: -174
 Deconectat
Mesaje: 107
Be wise,be smart,be like me!
|
|
« Răspunde #1 : Martie 27, 2007, 11:14:38 » |
|
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...  |
|
|
|
|
Memorat
|
Only one thing I know:Death is the best way to a better life.
|
|
|
|
•filipb
|
|
« Răspunde #2 : Martie 27, 2007, 11:18:07 » |
|
Rezolvarea oficiala foloseste un trie.
|
|
|
|
|
Memorat
|
|
|
|
•vanila0406
De-al casei
Karma: -174
Deconectat
Mesaje: 107
Be wise,be smart,be like me!
|
|
« Răspunde #3 : Martie 27, 2007, 13:55:21 » |
|
totusi...parerea mea este ca si parcurgerea trie-ului se face tot liniar...sau poate ma insel....  |
|
|
|
|
Memorat
|
Only one thing I know:Death is the best way to a better life.
|
|
|
|
•Marius
|
|
« Răspunde #4 : Martie 27, 2007, 13:57:14 » |
|
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.
|
|
|
|
« Ultima modificare: Martie 27, 2007, 20:35:00 de către Marius Stroe »
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
|
•stef2n
|
|
« Răspunde #5 : Martie 27, 2007, 17:18:20 » |
|
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)  |
|
|
|
|
Memorat
|
Exista 10 categorii de oameni: cei care inteleg sistemul binar si cei care nu il inteleg.
|
|
|
|
•filipb
|
|
« Răspunde #6 : Martie 27, 2007, 17:20:18 » |
|
totusi...parerea mea este ca si parcurgerea trie-ului se face tot liniar...sau poate ma insel.... Think 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. |
|
|
|
|
Memorat
|
|
|
|
•Bluedrop_demon
Client obisnuit
Karma: -3
Deconectat
Mesaje: 66
|
|
« Răspunde #7 : Aprilie 02, 2007, 04:03:08 » |
|
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 ?
|
|
|
|
|
Memorat
|
|
|
|
|
•stef2n
|
|
« Răspunde #8 : Aprilie 02, 2007, 08:38:30 » |
|
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. |
|
|
|
« Ultima modificare: Aprilie 02, 2007, 08:44:47 de către Stefan Istrate »
|
Memorat
|
Exista 10 categorii de oameni: cei care inteleg sistemul binar si cei care nu il inteleg.
|
|
|
|
•Mishu91
|
|
« Răspunde #9 : Noiembrie 13, 2008, 23:53:14 » |
|
Aveti va rog un test mai nasol... ca pe toate testele mele da bine, dar iau numai 40  L.E : S-a rezolvat  |
|
|
|
« Ultima modificare: Noiembrie 14, 2008, 00:35:08 de către Andrei Misarca »
|
Memorat
|
|
|
|
|
•vendetta
|
|
« Răspunde #10 : Martie 13, 2012, 22:25:30 » |
|
I`au doar 15 pct cu wa . Am folosit un trie si apoi am cautat raspunsul binar  |
|
|
|
|
Memorat
|
|
|
|
•Sapientia
Strain
Karma: 0
Deconectat
Mesaje: 29
|
|
« Răspunde #11 : Martie 19, 2014, 16:56:20 » |
|
Cum pot calcula lungimea celui mai lung prefix a n cuvinte dintr-un trie? .O mica sugestie mi-ar fi de folos... |
|
|
|
|
Memorat
|
|
|
|
|
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena