025 Heapuri

[•blue_phoenix]

si sursa oficiala ia tot 40p, tot cu tle pe ultimele doua teste......

[•pauldb]

Am crescut limita de timp la 0.25s. Nici sursa mea nu se mai incadra in limita de timp.

[•blue_phoenix]

Mersi! Tare chestia cu reevaluarea surselor deja trimise
@Dragos: am trimis si o sursa cu ideea ta, cu buffer-ul; a scazut  fff tare timpul, nu ma asteptam sa fie mai rapid parsatul caracter cu caracter decat cititul direct din fisier; pare o chestie f utila, mersi frumos!

[•iolan]

De ce acest program a blocat monitorul de evaluare?

[•Roswen]

Am incercat o implementare cu 3 vectori dar nu reusesc nicicum sa iau 100... iau incorect pe 6 teste dar toate exemplele care le incerc eu dau bine  

daca are cineva putin timp sa se uite peste sursa http://infoarena.ro/job_detail/710752?action=view-source sau stie cateva teste mai cheie pt verificarea greselilor as ramane recunoscator .

Multumesc

LE am rezolvat...dar schimbarea care am facut'o a fost sa scot conditia de urcare a nodului care il inlocuia pe cel proaspat sters (modul descris de articolul InfoArena), de aici ori eu am busit ceva la implementare, ori testele nu sunt chiar in regula. 

[•PetcuIoan]

Daca exista cineva care nu are chef sa implementeze heapuri de mana problema se rezolva
usor cu multiset.

[•wefgef]

Daca exista cineva care nu are chef sa implementeze heapuri de mana problema se rezolva
usor cu multiset.

Merge la fel de usor si cu priority_queue.

[•PetcuIoan]

Merge la fel de usor si cu priority_queue.

Smechera sursa, nu m-am gandit ca nu conteaza ce imi tin in structura atata timp cat afisez ce trebuie...

[•laurion]

Merge la fel de usor si cu priority_queue.

Care e defapt un vector implementat cu push_heap si pop_heap. Daca faci cu vector, poti sa accesezi si elementele din interior (dar nu le poti modifica, evident, ca ar trebui sa reechilibreazi), ce poate fi folositor daca vrei sa gasesti un nod in heap   

[•taigi100]

De curiozitate nu ar trebui programul sa ruleze folosind numai 2 vectori?
un vector Heap in care sa retii Heapul si un vector poz in care sa retii pozitile fiecarui element astfel
initial punem poz[el(el=nr de elemente)]=el;
iar cand schimbam pur si simplu regula paharelor
astfel vom obtine un vector de genul
v=(4,5,6,3,2) (am dat niste valori complet random)
     1 2 3 4 5

asta ne spune ca elementul al 4-lea intrat in vector se afla pe pozitia 1 el intrat la 3-lea se afla pe pozitia 4 and so on
Nu sunt sigur de intra in timp tinand cont ca pentru fiecare stergere vom avea nevoie de un for pentru a gasi elementul respectiv dar imi puteti zice de macar o sursa de genul da reultatele corecte? si daca da unde e greseala in sursa:
http://infoarena.ro/job_detail/758521

[•soriyn]

Nu m-am uitat foarte atent dar sa zicem ca la un moment dat ai in heap 5 elemente. Apoi il stergi pe cel intrat primu si dupa asta adaugi alt numar. Si acum vrei sa il stergi pe cel intrat al 5-lea. Eu cred ca ai doi candidati. Adica in vectoru tau vor fi doi de 5 pentru ca tu ai doar variabila aia el. Practic numarul intrat al 6-lea cronologic tu il consideri ca al 5-lea din cauza ca decrementezi el cand stergi un element.

[•taigi100]

Mersi mult, imi da 7 teste corecte dar la ultimele 3 imi da TLE cum asi putea sa reduc un pic timpul de rulare la alea 3?
ma gandeam de reusesc cumva sa elimin forul ala pentru poziti ( is doar in cls 9-a deci nu prea realizez dak ala e chiar problema de baza in timp dar asa cred)
P.S. urasc faptul ca nu observ chestii cum ai observat tu  kinda the reason i lost the national loot this year:(

[•soriyn]

Poti sa incerci sa schimbi citirea si afisarea. Incearca cu stream-uri poate intra in timp.

[•taigi100]

la fel:( 

[•PlayLikeNeverB4]

Poti face down() si iterativ. Nu iti intra in timp fiindca tu cauti de fiecare data care este elementul intrat al x-lea, ceea ce ar trebui sa faci in O(1).

[•taigi100]

bun si cum asi putea face cautarea in O(1) fara inca un vector?

[•soriyn]

Nu prea cred ca ai cum fara un vector. Iar iterativ poti sa faci ceva de genu

Cod:

do
{
   int son=0;
   //apoi verifici daca vreunul din fii e mai mic si in caz afirmativ son=1 si le interschimbi

}while(son);

P.S. : vad ca intre timp ti-ai editat mesajul. Presupun ca ai reusit sa faci iterativ

[•taigi100]

da numai ca din pacate acu imi greseste testul 5 si 6

Cod:

	int s,d,fk;
	do
	{
		fk=loc;
		s=fk*2;d=fk*2+1;
	if(s<=el && v[s]<v[fk])
		fk=s;
	if(d<=el && v[d]<v[fk])
		fk=d;
	if(fk!=loc)
	{
		swap(fk,loc);
	}
	}while(fk!=loc);

asta am facut desi nus sigur cat e de bine
problema e ca nu inteleg de ce dar pur si simplu nu reusesc sa inteleg la ce miar tb sa am 3 vectori si cum sai folosesc (desi am facut multe probleme cu o gramada de vectori nush cum da mno...)

[•taigi100]

Ar fi tare de asi reusi sa realizez ce miam propus la inceput
poz[1]=locatia elementului care a intrat primul in heap
and so on
si asta mar scuti de cautarea aia and such
dar ink tb sa ma gandesc cum sa schimb valorile lui poz ca sa realizez asta

[•danalex97]

Ca sa faci un max-heap cu priority_queue e suficient sa il declari asa:

Cod:

priority_queue< pair<int,int> , vector< pair<int,int> > > H;

[•Schumi]

Pentru max heap e suficient

Cod:

priority_queue<int> H;

Priority queue face maxheap daca il declari simplu. Daca vrei sa faci min heap trebuie sa schimbi declararea sau poti sa faci max heap si sa inserezi in loc de a -a in heap

[•danalex97]

Multumesc. 

[•DevilShadow]

Diferenta dintre endl la '\n' ii de la 40 la 100 de puncte 

[•pauldb]

endl forteaza golirea buffer-ului, '\n' nu. Din acest motiv, diferenta e sesizabila.

[•Sapientia]

2-se sterge elementul intrat al x-lea in multime, in ordine cronologica.
Exista o operatie speciala de eliminare a unui element dintr-un heap inafara de min/max?