|
Titlul: 118 String Scris de: Mircea Pasoi din Septembrie 26, 2005, 13:25:19 Aici puteţi discuta despre problema String (http://infoarena.ro/problema/string).
Titlul: 119 String Scris de: Alb Gabriel din Septembrie 26, 2005, 21:14:22 Care ar fi complexitatea optima?
Titlul: 119 String Scris de: Mircea Pasoi din Septembrie 26, 2005, 21:45:13 Citat din mesajul lui: Gabi Care ar fi complexitatea optima? O solutie O(N*lg N) ar trebui sa intre in timp fara probleme. Titlul: 119 String Scris de: Alb Gabriel din Septembrie 27, 2005, 19:11:32 Mersi.
Titlul: Raspuns: 119 String Scris de: Tabara Mihai din Ianuarie 20, 2007, 22:47:07 Am O(N*lg N) si nu imi intra in timp pe doua teste ( 7 si 8 ) :'(.
Mentionez ca fac cu BST si m-am bazat pe solutia lui Mugurel Ionut Andreica. Ceva idei ? :oops: :sad: Titlul: Raspuns: 119 String Scris de: Airinei Adrian din Februarie 02, 2007, 13:48:44 Probabil folosesti alocare dinamica, recursivitate.. Incearca o solutie iterativa, optimizeaza si memoria folosita, limita de timp e destul de stransa la problema asta.
Titlul: Raspuns: 119 String Scris de: Tabara Mihai din Februarie 02, 2007, 14:44:43 Probabil folosesti alocare dinamica, recursivitate.. Incearca o solutie iterativa, optimizeaza si memoria folosita, limita de timp e destul de stransa la problema asta. E adevarat.Am si alocare dinamica si si recursivitate. :sad: Vroiam numai sa zic o chestie....insusi solutia lui Mugurel Ionut Andreica nu merge de 100.Cam ciudat :sad: Titlul: Raspuns: 119 String Scris de: Filip Cristian Buruiana din Februarie 02, 2007, 17:10:31 Cand s-au pus problemele in arhiva limita de timp s-a micsorat tocmai pentru a-i preveni pe unii useri sa trimita sursele oficiale. 8)
Titlul: Raspuns: 119 String Scris de: Tabara Mihai din Februarie 02, 2007, 17:18:03 Cand s-au pus problemele in arhiva limita de timp s-a micsorat tocmai pentru a-i preveni pe unii useri sa trimita sursele oficiale. 8) Daca stau sa ma gandesc putin e si normal sa procedati asa[ :thumbup:].Numai ca sunt la inceput cu arborii de prefixe si problema asta am inteles-o destul de bine, si mai ales solutia, si deci eram incantat.Insa ai dreptate, deocamdata ma multumesc cu 80 pana ma invat mai bine cu arborii si reusesc o solutie singur. :peacefingers: Titlul: Raspuns: 119 String Scris de: Airinei Adrian din Februarie 02, 2007, 17:29:38 Exista o solutie mult mai simpla care nu foloseste nicio structura de date avansata. Hint: leaga-te de lungimea secventei
Titlul: Răspuns: 118 String Scris de: tester din Octombrie 27, 2008, 21:03:39 stie cineva de ce nu intra o sursa pe 3 teste cu compl: O(|M| * (N + log N)), unde M e lungimea care trebuie afisata si care nu poate fi mai mare decat log N + 1 :) ...... am radix sort + cautare binara
Ce s - a intamplat cu evaluatorul, de ce s-a blocat ? [edit moderator] nu mai posta consecutiv, ci editeaza-ti mesajele Titlul: Răspuns: 118 String Scris de: Marian Darius din Februarie 06, 2013, 20:14:13 Imi poate da cineva un hint legat de cum pot face O(n log n)? Am facut O(n * log^2 n) si iau TLE pe 6 teste. M-am gandit la solutia in care sa adaug fiecare secventa de lungime maxim log2 n intr-un Hash, dar am problema ca abba si bba de exemplu se considera drept acelasi lucru (am transformat secventa in baza 2).
Titlul: Răspuns: 118 String Scris de: Visan Radu din Februarie 06, 2013, 20:26:16 Pentru o lungime L fixata (log N maxim, cum ai zis si tu), iti faci un vector de frecvente pt configuratiile care apar si vezi de iti apar toate sau nu (poti itera pt L ca e mic).
Titlul: Răspuns: 118 String Scris de: Mihai Calancea din Februarie 06, 2013, 20:46:42 Poti sa pui un 'b' in fata tuturor stringurilor si nu mai ai nicio problema de genul asta. De asemenea, poti sa obtii si N log log N fiindca poti cauta binar raspunsul.
Titlul: Răspuns: 118 String Scris de: Marian Darius din Februarie 07, 2013, 18:27:12 Multumesc pentru ideea cu 'b' in fata fiecarei secvente. Am luat 100 :yahoo: :yahoo:
|