042 Statistici de ordine

[•Marius]

Aici puteţi discuta despre problema Statistici de ordine.

[•Bogdan_tmm]

Am 2 chesti neclare
1 se zicea ca citirea cu streamuri e mai lenta(cel putin aici nu-i adevarat)
2

Cod:

6	1364ms	16704kb	Time limit exceeded.	0	0
7	1352ms	16704kb	Time limit exceeded.	0	0
8	1276ms	16700kb	Time limit exceeded.	0	0
9	1296ms	16708kb	Time limit exceeded.	0
10	1344ms	16708kb	Time limit exceeded.	

testele 8 si 9 au sub 1300 ms si totusi au tle ...

[•DraStiK]

Cod:

6	1364ms	16704kb	Time limit exceeded.	0	0
7	1352ms	16704kb	Time limit exceeded.	0	0
8	1276ms	16700kb	Time limit exceeded.	0	0
9	1296ms	16708kb	Time limit exceeded.	0
10	1344ms	16708kb	Time limit exceeded.	

testele 8 si 9 au sub 1300 ms si totusi au tle ...

Timpii afisati sunt orientativi, nu sunt foarte precisi. 

[•Mishu91]

Am 2 chesti neclare
1 se zicea ca citirea cu streamuri e mai lenta(cel putin aici nu-i adevarat)

Pe noile versiuni de compilatoare, citirea cu stream-uri este mai rapida decat cea standard.

[•Marius]

Am 2 chesti neclare
1 se zicea ca citirea cu streamuri e mai lenta(cel putin aici nu-i adevarat)

Pe noile versiuni de compilatoare, citirea cu stream-uri este mai rapida decat cea standard.

Totul e un hazard mai degrabă. La problema Huffman, citirea cu fscanf() e mai rapidă decât cea cu streamuri.

[•Mishu91]

Ai luat in calcul doar citirea, sau si afisarea? Pentru ca din ce am vazut afisarea standard este mai rapida.

[•Bogdan_tmm]

Si citirea si afisarea le-am facut cu streamuri....

[•05_Yohn]

Am o nelamurire, algoritmul acela din Cormen cu O(n) pe cazul cel mai defavorabil l-a implementat careva, sau se poate implementa?
Eu am incercat ceva, dar mai mult de 10 n-am luat, probabil ca sigur busesc ceva.. va rog daca l-ati implementat trimiteti-mi si mie un pm cu link catre sursa. Multumesc anticipat!

PS: Random-Select pe fpc nu mi-a mers mai mult de 60 cu tot cu settextbuf 

[•S7012MY]

Am o nelamurire, algoritmul acela din Cormen cu O(n) pe cazul cel mai defavorabil l-a implementat careva, sau se poate implementa?
Eu am incercat ceva, dar mai mult de 10 n-am luat, probabil ca sigur busesc ceva.. va rog daca l-ati implementat trimiteti-mi si mie un pm cu link catre sursa. Multumesc anticipat!

PS: Random-Select pe fpc nu mi-a mers mai mult de 60 cu tot cu settextbuf 

eu am implementat si am luat 100
infoarena.ro/job_detail/450049?action=view-source

[•05_Yohn]

Din ce vad eu, tu ai implementat tot un random-select (alegi ca pivot un element aleator din partitia in care te afli, apoi faci ca la quicksort).. eu ma refer la algoritmul in care sortezi tot cate 5 elemente ca sa gasesti un pivot "bun" intotdeauna.
Uite aicihttp://zhuzeyuan.hp.infoseek.co.jp/ita/chap10.htm 10.3 Selection in worst-case linear time

[•Mishu91]

Am o nelamurire, algoritmul acela din Cormen cu O(n) pe cazul cel mai defavorabil l-a implementat careva, sau se poate implementa?
Eu am incercat ceva, dar mai mult de 10 n-am luat, probabil ca sigur busesc ceva.. va rog daca l-ati implementat trimiteti-mi si mie un pm cu link catre sursa. Multumesc anticipat!

PS: Random-Select pe fpc nu mi-a mers mai mult de 60 cu tot cu settextbuf 

Algoritmul acela este mai mult teoretic și destul de complicat, motiv pentru care doar am menționat existența lui la explicații. Când băgam problema, găsisem (nu mai știu exact unde) că și nth_element este implementat tot în stilul algoritmului cu pivot random.

Din păcate, volumul de date este foarte mare și probabil citirea consumă foarte mult timp(chiar și cu parsare). Mai treci la C++.

[•SpiderMan]

@Oogway, se poate lua 100 in pascal cu timpi foarte buni ( look HERE ) . Am folosit SetTextBuff ( bufferul merge declarat orice, longint, byte, char, boolean, intra oricum ) si cu citire parsata. Am vazut ca char-ul ca si buffer merge mai repede si daca pui limita superioara o putere a lui 2 .

[•05_Yohn]

@SpiderMan - mersi mult

@Mishu91 - o sa trec in cele din urma la C++, ca nu se mai poate   

[•andreifirst]

Folosesc ideea de rezolvare prezentata la explicatie, dar nu reusesc nici cum sa iau 100 pct.

Aici sunt 2 surse ale mele cu punctaje de 70 cu implementari usor diferite de Qsort
http://infoarena.ro/job_detail/575373?action=view-source
http://infoarena.ro/job_detail/575301?action=view-source

M-am uitat putin prin surse si am vazut ca majoritatea celor scrise in C++ merg pe ideea mea, iar in FPC sunt doar 2 de 100 pct si au abordari ciudate.

Sunt curios, e vreo greseala in sursa mea sau pur si simplu a venit timpul sa trec in C++?
Multumesc anticipat!

[•Mishu91]

Din păcate, după ce am schimbat testele, se pare că este foarte greu să se ia 100 în Pascal.

Părerea mea este că ar fi mai bine să treci la C++, nu doar pentru a lua 100 la problema asta, avantajele lui C++ faţă de Pascal au ai fost dezbătute în câteva topicuri.

[•andreifirst]

okay, Mishu, ms. Cred ca nu este cel mai bun moment sa fac schimbarea acum, cu o saptamana inainte de nationala, deci o sa zic pas problemei asteia. Daca totusi se uita cineva de curiozitate in sursa si observa o neregula, astept cu tot dragul comentarii.

Edit: Am rezolvat. Se pare ca doar citirea din FPC era de vina. Am schimbat citirea normala cu citire string si transformare ulterioara in numar. Asta si fara sa schimb nimic mi-a scazut timpul de executie de la 1200 ms la 400 ms pe testul 7, deci de 3 ori mai repede. Multumesc pascalistilor pentru idee

[•tzipleatud]

Salut! De ce sursa asta: http://infoarena.ro/job_detail/609325?action=view-source ia mai putin decat aceasta: http://infoarena.ro/job_detail/609324?action=view-source si de ce niciuna nu ia punctaj maxim? Multumesc anticipat!

[•Magnus]

"rand" este o functie care returneaza o valoare aleatorie(ma rog, pseudo-aleatorie: http://www.cplusplus.com/reference/clibrary/cstdlib/rand/).
Deci este normal sa nu-ti returneze de fiecare data aceeasi valoare si prin urmare sa ai timpi de executie diferiti.

[•dany123]

In functia sel:

Cod:

int q = part(li, lf);
int t = q-li+1;

Din cate imi dau seama q este statistica de ordine a elementului ales aleator, dar t ce este? nu-mi dau seama care-i logica, dar vad ca fara el nu merge.

[•vlad.doru]

Mai exista si o alta rezolvare de 100 de puncte la problema asta care se bazeaza pe o functie de partitionare in bucketuri si care ia 100 de puncte. Am implementat-o cu succes si timpul maxim este mai bun decat cel obtinut cu functia nth element din STL.

[•Teodor94]

am reusit sa iau tle pe testul 3, dintr-un motiv sau altul... desi pare a fi un test mic. folosind streamuri la citire iau 90 puncte cu tle pe testul 3. folosind stdio, iau tle pe testul 1 si 3..
http://infoarena.ro/job_detail/695302

[•Mishu91]

In functia sel:

Cod:

int q = part(li, lf);
int t = q-li+1;

Din cate imi dau seama q este statistica de ordine a elementului ales aleator, dar t ce este? nu-mi dau seama care-i logica, dar vad ca fara el nu merge.

q este pozitia pivotului, iar t retine cate numere sunt mai mici decat pivotul in intervalul [li..lf]

[•mihai995]

Ar trebui redus timpul ... am luat 100p cautand binar solutia, in O(30 N)

[•https]

Ma puteti ajuta va rog si pe mine? Nu imi dau seama de ce nu merge http://www.infoarena.ro/job_detail/1111373?action=view-source Multumesc