294 Zeap

[ditzone]

Aici puteţi discuta despre problema Zeap.

[Chris]

Salut!

Ai grija la memove :

Cod:

memove(dest, source, bytes_to_move);

nu numarul de elemente (cu exceptia datelor pe 1 byte - acolo e numarul de elemente ).

Si clar ca nu o sa se incadreze in timp daca faci o operatie in timp liniar. Eu am facut toate operatiile in O(logN) cu arbori binari de cautare (red-black trees din STL) si am luat 80p.

[•peanutz]

memove, in sursa asa am scris.... neatentie, silly me
mda, ai dreptate.... am inteles gresit.... e nr_elemente*sizeof(type)....   

[•wefgef]

.... la min era mai nasol ca mi se pare ca parcurgeam vectorul

Pai nu ar trebui sa ti se incadreze in timp .

Gandeste-te ce structura ai putea folosi pentru a efectua toate operatiile eficient.

[•pocaitu]

    Stiu si eu cum s-ar face toate operatiile de mai sus in O(nlog(N)) da nu stiu cum se face la min dif . Daca ar fi sa retin toate diferentele dintre numere mi-ar iesi un ditamai arborele . Imi scapa ceva  ? Poate da cineva un hint  ? 

[u-92]

ai putea folosi un arbore de intervale pentru operatia min dif.
pentru detalii despre cum functioneaza aceasta sctructura de date este si aici un articol http://info.devnet.ro/download.php?page=cat&cat=35

[•peanutz]

Eu am downloadat chestia aia, dar nu avea nicio extensie... Am pus pdf, doc... nimic.... Ce format e?

[Tabara Mihai]

Eu am downloadat chestia aia, dar nu avea nicio extensie... Am pus pdf, doc... nimic.... Ce format e?

Mie imi merge ok cu .doc

[•StTwister]

Pare a fi .doc, apare undeva in fisier 'arbori de intervale.doc', dar nici mie nu-mi merge cu .doc.

Cu ce versiune ai incercat?

[•peanutz]

Oh, well, eu trec pe linux.... Tre sa-l vada acolo...

[•pocaitu]

 Merge cu ".doc" la office 2007

[•Dorin]

de fapt ii o arhiva pui extensia zip la fisier si apoi il extragi 

[•gabor_oliviu1991]

Fisierul de intare va contine maxim 300 000 linii

o mica gresala

[•PetcuIoan]

  Cat de inceata este citirea
cod: string s;
       cin >> s;
fata de
cod: char s[20];
       gets(s);
?
Am complexitatea buna dar nush de ce imi iese asa de rau din timp...

[•stardust]

Imi poate spune si mie cineva cum sa folosesc un arbore de intervale pentru operatia min-dif ? 

[•danalex97]

Raspunsul meu pentru tine vine cam tarziu... Uite un hint , incearca sa stochezi mai multe informatii in acelasi arborele de intervale. Gandeste-te la proprietatile arborelui de intervale si o sa te prinzi.  App , sorteaza datele de intrare. 

O alta solutie ar fi una cu arbore de intervale + hash. Implementarea mea nu e buna , insa teoretic ar trebui sa functioneze.
http://infoarena.ro/job_detail/773038?action=view-source

Succes. 

[•stardust]

Pai la arbori de intervale + hash ma gandeam si eu. Dar cum faci operatia de min-dif ? Poti sa explici putin ideea ca nu ma prind din sursa

[•danalex97]

Fac mai multi arbori. In unul retin maximul , in unul minimul , in unul dif maxima , in unul dif min. Dif min este valoarea minima dintre: fiul stang , fiul drept , diferenta dintre maximul stang si maximul drept , diferenta dintre minimul stang si minimul drept. Cred ca mergea bine ( nu sunt sigur , dar cred ca de la implementare iau incorect ). Daca nu incearca pe alta idee. Succes. 

[•vendetta]

Fac mai multi arbori. In unul retin maximul , in unul minimul , in unul dif maxima , in unul dif min. Dif min este valoarea minima dintre: fiul stang , fiul drept , diferenta dintre maximul stang si maximul drept , diferenta dintre minimul stang si minimul drept. Cred ca mergea bine ( nu sunt sigur , dar cred ca de la implementare iau incorect ). Daca nu incearca pe alta idee. Succes.  

Cum adica doar crezi ca mergea? (din moment ce tu ai 100 de puncte ?)

stardust : uite cum m-am gandit eu sa fac operatia Min-dif(la celelalte presupun ca te descurci) : Tin un set in care pun diferenta dintre 2 termeni consecutivi; acum trebuie sa fi atent(sa vezi cum modifici set-ul cu diferentele) cand elimini un element si cand introduci un element; cu aceasta idee iau 60 de pct : 2 tle-uri si 2 Killed by signal 11

[•danalex97]

Cu hash+aint am facut o solutie , dar am si alta care ia 100. Si ai dreptate , merge bine. ( ma gandeam ca am schimbat ceva la cealata sursa insa nu am schimbat  )

App vendetta , la set din STL te referi , nu ? Unde pot gasi la ce se foloseste si cum functioneaza ?

[•visanr]

http://www.cplusplus.com/reference/stl/set/ ?