025 Heapuri

[•filipb]

Aici puteti discuta despre problema Heapuri.

[•jupanubv92]

Am doua surse care iau 100 de p si am facut un test care da rezultate diferite pe ambele surse . Ar trebui un pic imbunatatite testele sa vad si eu care e sursa gresita (stiu care e gresita dar ar trebui sa fiu atentionat si de evaluator ).Daca nu ma uitam la solutia oficiala eram convins ca prima sursa este corecta si puteam sa o busesc rau in timpul concursurilor.

De exemplu pe testu asta prima sursa imi da 6 si a doua 5 si ambele au obtinut 100 de p .
http://infoarena.ro/job_detail/330396
http://infoarena.ro/job_detail/330423

Cod:

22
1 1
1 6
1 2
1 7
1 8
1 3
1 4
1 10
1 11
1 12
1 13
1 5
2 10
2 3
1 20
2 6
1 30
2 7
1 40
2 1
1 50
3

[•AnDrEwBoY]

Eu primesc pe sursa mea  5 si ma bazez pe acelasi sistem ca la a doua varianta 

Editat de admin: Foloseste butonul "Modifica"

[•jupanubv92]

Pai 5 este raspunsul corect .. doar am vrut sa atrag atentia ca sunt teste pe care unele surse de 100 de p iau incorect . Adica eu cand aveam o operatie de stergere inlocuiam nodul pe care vreau sa il sterg cu ultimul nod si micsoram numaru de elemente din heap si nu sa construit nici un test in care atunci cand trebuie sa sterg un nod sa fiu nevoit sa fac si upheap .

[•robigi]

salut, imi poate da cineva o idee de ce sursa asta :    http://infoarena.ro/job_detail/365422?action=view-source

la testul 7 unde ar trebui sa afiseze 1 2 3 ... 50001   mie mai afiseaza bine doar pana la aprox 33000 dupa care afiseaza gresit, deci ceea ce nu-nteleg eu cum poate merge corect pana la mai mult de jumatate cu acelasi algoritm si acelasi proces doar cu alte numere

in plus in rest ia toate testele corect

[•popoiu.george]

Imi puteti spune cum ar trebui sa retin ordinea in care sunt introduse valorile?...Ca nu reusesc sa inteleg.

[•alexandru92]

Pai sa zic ca in v[ i ] ti minte al i-lea element
In Heap[ i ] <- ti minte pozitia elementului din vectorul v, iar in vectorul Position[ i ] ti minte positia elementului i in Heap. Odata ce adaugi/stergi un element in Heap Position se va schimbat, trebuie sa vezi cum
 

[•popoiu.george]

Iti multumesc mult alexandru ! Chiar am inteles, si iti marturisesc ca daca nu imi explicai tu cred ca mai dura muulta vreme pana aflam ce semnifica acei vectori. 

Cred ca ar trebui comentate sursele oficiale de la problemele din arhiva educationala, deoarece unei persoane care nu are alte surse de informare ii este foarte greu (sau imposibil) sa inteleaga o sursa necomentata.

[•alexandru92]

Cred ca ar trebui comentate sursele oficiale de la problemele din arhiva educationala, deoarece unei persoane care nu are alte surse de informare ii este foarte greu (sau imposibil) sa inteleaga o sursa necomentata.

Da, n-ar strica niste mici comentarii  ale surselor prezentate
Dar din acelasi motiv presupun ca exista forumul

[•johsonsbabi]

ce face assert? e folosit de mai multe ori in sursa oficiala va rog ms

[•alexandru92]

ce face assert? e folosit de mai multe ori in sursa oficiala va rog ms

assert( conditie ) - daca conditia este falsa opreste din exectuie programul returnand o valoare de eroare. Este folosit pentru a vedea daca anumite valori respecta limitele impuse
http://www.cplusplus.com/reference/clibrary/cassert/assert/

[•cezy]

Cum as putea rezolva problema folosind priority_queue din stl ? practic cum pot sterge un el x cu priority_queue exista vreo functie ? caci pop imi sterge doar el de prioritate maxima sau se poate folosi si pt a sterge un el oarecare?

[•blasterz]

Priority Queue este o structura de data abstracta (poate fi implementate in mai multe moduri) ce permite doar operatiile push, pop si top.
Deci nu-l poti folosi pentru ce vrei tu.

[•vladtarniceru]

imi spune cineva va rog ce as mai putea optimiza la sursa asta http://infoarena.ro/job_detail/514478?action=view-source

multumesc

[•PlayLikeNeverB4]

Cred ca e (si mai mult decat probabil) de la modalitatea in care afli "elementul intrat al x-lea in multime".
Tu lucrezi in Heap direct cu valoarea elementelor si strici pozitia lor cronologica.
Ceea ce trebuie sa faci e sa memorezi pentru fiecare element din sir pozitia lui in Heap si pentru fiecare element din Heap pozitia lui in sir.

[•vladtarniceru]

da dar cum, nu vad cum ar putea intra in memorie (nr sunt pana la 1000000000) deci nu pot lua un vector in care fac ap[v] = i;

[•pauldb]

Te poti folosi ca informatie intermediara de numarul de ordine al operatiei de insert. Poti introduce aceste valori in heap, sa le compari in functie de valoarea efectiva (pe care o retii in alt vector) si sa mai tii un vector care iti spune pentru fiecare operatie pozitia curenta din heap.

[•vladtarniceru]

paul, tu vrei sa zici ca iau un vector v[] in care v[ i ] e al i-lea inserat si mai iau un vector t[] in care t[ i ] este pozitia in heap a celui de-al i-lea inserat?

si daca e asa, ca sa fac elementul al 2-lea inserat sa zicem fac:
int element = v[2];
int pozitie = t[2];  

[•pauldb]

M-am exprimat putin prost. Fie faci cum ai scris, dar atunci in heap tii al indicele operatiei la care a fost un element si compari elementele din heap folosindu-te de vectorul v. Fie folosesti vectorul v pe post de heap, dar atunci ca sa accesezi valoarea celui de-al i-lea inserat element, faci element = v[t[2]].

[•vladtarniceru]

acum am inteles ideea, dar iau 10 puncte cu sursa implementata asa 
i-am mai dat teste si ies toate, am facut si cu debuggerul ca sa fiu sigur ca trece bine in t[] si intr-adevar e bine , iar testele de la atasamente sunt cam mari ..
as ramane recunoscator celui care m-ar ajuta

multumesc

[•PlayLikeNeverB4]

Eu asa am facut:
v[ i ]= elementul intrat al i-lea in multime (deci, practic sirul pe care il citesc)
H[ i ]= pozitia in sirul v a elementului de pe pozitia i in heap
poz[ i ]= pozitia in heap a elementului de pe poztia i in sirul v
v[H[ i ]]= valoarea elementului de pe pozitia i in heap

Si de aici lucrezi cu v[H[ i ]] cand compari valorile. Vectorul poz il folosesti ca sa stii instant care element il stergi.

Nu poate fi chiar atat de greu daca si eu am inteles )

[•vladtarniceru]

mi-a iesit in cele din urma, multumesc tuturor pentru ajutor

totusi, cautarea aceea (sa cauti al i-lea elem intrat) nu se poate face si cu hashing? 

[•blasterz]

mi-a iesit in cele din urma, multumesc tuturor pentru ajutor

totusi, cautarea aceea (sa cauti al i-lea elem intrat) nu se poate face si cu hashing? 

Nu cred ca se poate cu hashing... intr-un hash nu ai o ordine ...sunt random asezate in memorie

[•blue_phoenix]

Salut!

Am tot incercat sa fac o sursa de 100p, dar iau TLE pe ultimele doua teste.
sursa mea e aici http://infoarena.ro/job_detail/632209 . Nu-mi dau seama ce ar trebui sa fac s-o imbunatatesc. (am schimbat si citirea, acum e cu freopen, ca in sursa oficiala)
Oarecum legat de subiect, intr-o prima versiune a programului heap-ul meu continea struct-uri (deci pentru push si pop, interschimbam obiecte de tip nod). Ia mai mult timp sa interschimbe doua struct-uri decat doua int-uri? sau totul se face la nivel de pointeri si deci ia la fel?
Multumesc anticipat!

[•DraStiK]

E cam stransa limita de timp.

Ca sa iti raspund la intrebare, teoretic lucreaza mai bine cu un tip cunoscut decat cu o structura.

Ca sa obtii 100 de puncte poti incerca sa parsezi citirea.