infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Andrei Grigorean din Februarie 15, 2009, 13:35:00



Titlul: 805 Gminmax
Scris de: Andrei Grigorean din Februarie 15, 2009, 13:35:00
Aici puteti discuta despre problema Gminmax (http://infoarena.ro/problema/gminmax).


Titlul: Răspuns: 805 Gminmax
Scris de: Andrei Misarca din Martie 05, 2009, 11:30:34
Am rezolvat problema folosind arbori de intervale, dar solutia cu N liste nu am prea inteles-o. Ce tin defapt in acele liste si cum le actualizez la fiecare pas. Puteti detalia putin, va rog :D


Titlul: Răspuns: 805 Gminmax
Scris de: Gheorghe Cosmin din Martie 05, 2009, 12:43:45
Am modificat. Sper ca acum se intelege mai bine


Titlul: Răspuns: 805 Gminmax
Scris de: Andrei Misarca din Martie 05, 2009, 12:54:34
Mersi :D


Titlul: Răspuns: 805 Gminmax
Scris de: Ionescu Robert Marius din Mai 04, 2009, 20:38:09
e ceva special cu testu 7? ](*,)


Titlul: Răspuns: 805 Gminmax
Scris de: Dragos Oprica din Februarie 19, 2010, 19:58:47
Am o întrebare, asupra unei soluții alternative:

Țin un heap ordonat după gradele nodurilor, și la fiecare pas scos din heap nodul cu grad minim, ii actualizez vecinii, si apoi verific dacă gradul nodului din vârful heap-ului este o îmbunatățire a soluției.

Este greșită soluția asta?


Titlul: Răspuns: 805 Gminmax
Scris de: Andrei Misarca din Februarie 19, 2010, 20:46:57
Ai grijă să refaci heap-ul pentru fiecare vecin actualizat. Dacă folosești priority_queue sau heap din STL nu va merge treaba.


Titlul: Răspuns: 805 Gminmax
Scris de: Dragos Oprica din Februarie 19, 2010, 21:07:33
Poți sa îmi explici mai pe larg de ce priority_queue din STL nu merge?

Chiar îmi place structura asta. Și chiar vroiam sa întreb cum exact își face update-ul.


Titlul: Răspuns: 805 Gminmax
Scris de: Andrei Misarca din Februarie 19, 2010, 21:14:04
Ideea este că el își face update-ul doar dacă inserezi un element, dar dacă modifici valorile heapul nu se va reface, iar vârful heapului nu este garantat cel mai mic element. Sper să nu greșesc.


Titlul: Răspuns: 805 Gminmax
Scris de: avram florin constantin din Aprilie 11, 2011, 15:16:22
imi poate spune si mie cineva ce e gresit in rezolvarea mea.
Cod:
for( i = 1 ; i <= N ; i++ )
update(1,1,N,i,gr[ i ]);
int nod,grmax,noduri,nrn;
noduri = N;
grmax = Arb[1].grad;
nrn = N;
while( noduri-- )
{
nod = Arb[1].nod;
update(1,1,N,nod,INF);
if( Arb[1].grad > grmax )
{
grmax = Arb[1].grad;
nrn = noduri;
}
vector<int>::iterator it;
for( it = G[nod].begin() ; it != G[nod].end() ; ++it )
update(1,1,N,*it,--gr[*it]);
}
printf("%d %d\n" , grmax , nrn );
Foloseste tagul [ code ] ... [ / code ]


Titlul: Răspuns: 805 Gminmax
Scris de: Denis Mita din Decembrie 02, 2014, 21:24:10
http://www.infoarena.ro/job_detail/1281129

"user.cpp:65:21: warning: unused variable ‘c***t’ [-Wunused-variable]"

Asa se vorbeste?  [-X


Titlul: Răspuns: 805 Gminmax
Scris de: patrutoiu andrei din Decembrie 06, 2015, 16:46:39
a luat cineva 100 pct cu solutia cu heapuri? eu am implementat manual si am MlogN dar iau tle pe 4 teste