118 String

[•domino]

Aici puteţi discuta despre problema String.

[•Gabi]

Care ar fi complexitatea optima?

[•domino]

Care ar fi complexitatea optima?

O solutie O(N*lg N) ar trebui sa intre in timp fara probleme.

[•Gabi]

Mersi.

[•Tabara]

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 ? 

 

[•astronomy]

Probabil folosesti alocare dinamica, recursivitate.. Incearca o solutie iterativa, optimizeaza si memoria folosita, limita de timp e destul de stransa la problema asta.

[•Tabara]

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. 

Vroiam numai sa zic o chestie....insusi solutia lui Mugurel Ionut Andreica nu merge de 100.Cam ciudat

[•filipb]

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.

[•Tabara]

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.

Daca stau sa ma gandesc putin e si normal sa procedati asa[ ].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.
 

[•astronomy]

Exista o solutie mult mai simpla care nu foloseste nicio structura de date avansata. Hint: leaga-te de lungimea secventei

[zombie_tester_2]

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

[•dariusdarius]

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

[•visanr]

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

[•klamathix]

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.

[•dariusdarius]

Multumesc pentru ideea cu 'b' in fata fiecarei secvente. Am luat 100