Imprimă pagina - 191 Substr

Titlul: 191 Substr
Scris de: ditzone din Martie 03, 2006, 18:24:28

Aici puteÅ£i discuta despre problema Substr (http://infoarena.ro/problema/substr).

Titlul: Raspuns: 191 Substr
Scris de: Rimovecz Ioan Mihai din Iulie 19, 2006, 18:06:33

Imi poate spune si mie cum se fac sufix array-urile in N log N. Nu stiu cum fac sortarea aia in O(n) implementat cu merge sort are complexitate N log^2N si iau 80p dar is curios cum se face in N log N.

Titlul: Re: 191 Substr
Scris de: Valentin Stanciu din Iulie 19, 2006, 19:06:11

Radix sort? Bucket sort? :)

Titlul: Raspuns: 191 Substr
Scris de: Marius Stroe din Decembrie 13, 2006, 18:13:55

Merge si countsort ?

Titlul: Raspuns: 191 Substr
Scris de: Andrei Grigorean din Decembrie 13, 2006, 19:41:15

probabil ca te referi la radix sort (trebuie sa sortezi dupa 2 chestii :P, de aia e radix).

Titlul: Raspuns: 191 Substr
Scris de: Marius Stroe din Decembrie 17, 2006, 20:50:29

Da, e un hibrid intre countsort si radixsort. :)

Am citit in revista GInfo un articol despre Siruri de Sufixe si nu imi dau seama cum cu o sortare in O(N log N) complexitatea totala e O(N^2 log N). Scrie in mai multe locuri, dar presupun ca e o greseala. Corect este O(N log^2 N), nu ? (Pentru cei care au citit numarul 15/7 Noiembrie 2005)

Titlul: Raspuns: 191 Substr
Scris de: Bogdan-Cristian Tataroiu din Decembrie 17, 2006, 21:31:01

Sortarea prezentata in acel articol este N log^2 N.. A fost data o errata la acel articol in urmatorul numar...

Titlul: RÄƒspuns: 191 Substr
Scris de: Sergiu-Ioan Ungur din Martie 20, 2010, 22:11:26

Exista vreun caz particular la testul 10? Chiar nu-mi dau seama ce este gresit la sursa mea si totusi pic testul 10. Daca ma poate ajuta cineva ii sunt recunoscator :).
L.E.
Testul 10 are sirul de caractere pe a doua linie?
Facand citirea:

Cod:

fin >> N >> K;
fin.ignore( 1, '\n' );
fin.getline( A, Dim );

iau 90p.
Facand citirea:

Cod:

fin >> N >> K;
fin.ignore( 10, '\n' );
fin.getline( A, Dim );

iau 100p.

Titlul: RÄƒspuns: 191 Substr
Scris de: Gemene Narcis - Gabriel din Octombrie 08, 2013, 21:48:28

Este vreo cineva care a luat 100 cu hash-uri?

Titlul: RÄƒspuns: 191 Substr
Scris de: Mouse Wireless din August 31, 2017, 16:54:17

Citat din mesajul lui: Gemene Narcis - Gabriel din Octombrie 08, 2013, 21:48:28

Este vreo cineva care a luat 100 cu hash-uri?

Am luat eu (raspuns cu 4 ani intarziere :roll:)

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: ditzone din Martie 03, 2006, 18:24:28