911 Ghizi

[•silviug]

Aici puteti discuta despre problema Ghizi.

[•zoopp]

Pic toate testele cu exceptia nr. 2 si al exemplului.. Am facut si cateva teste cu date de intrare facute de mine si le-a trecut.

Nu vad nici o scapare in logica care am adoptat-o..codul sursa de asemenea e flawless

Se poate sa primesc datele de intrare/iesire de la unul din teste ?  

[•S7012MY]

Pic toate testele cu exceptia nr. 2 si al exemplului.. Am facut si cateva teste cu date de intrare facute de mine si le-a trecut.

Nu vad nici o scapare in logica care am adoptat-o..codul sursa de asemenea e flawless

Se poate sa primesc datele de intrare/iesire de la unul din teste ?  

Problema a fost data la oni 2003-baraj. Gasesti testele aici http://infoarena.ro/downloads?action=download&file=oni03.zip&safe_only=false

[•devilkind]

Ai putea sa ne zici cum faci si abia apoi o sa putem sa te ajutam.

Vad ca a inceput o miscare de ceva vreme sa se tot dea linkuri pe forum catre arhive cu testele oficiale. Ei bine acest lucru nu e tocmai ok, ideea nu e sa treci toate testele, ideea e sa rezolvi problema corect. Nu vrei sa stai 2 zile pe un bug? Bine i-ati testele si vei descoperi imediat acel bug insa e foarte probabil sa repeti acel bug. Sa stiti ca si statu 2 zile pe un bug ajuta, pentru ca odata ce l-ai gasit iti va ramane in minte si nu il vei mai repeta. Incercati de acuma sa dati hinturi de rezolvare si sa nu mai trimiteti oameni direct la teste sau la solutia oficiala, exista un motiv pentru care echipa infoarena nu a facut testele si sursele publice la toate problemele.

[•zoopp]

Hmm...inteleg ce vrei sa spui...

Bine..am sa sterg arhiva de mai sus pe care tocmai am descarcat-o si am sa explic metoda mea de rezolvare.

Eu am gandit asa:

Un ciclu complet este o multime de intervale care reunite formeaza un intreval de forma [0, 100).
Eu caut sa formez cicluri complete pana cand nr. de cicluri corespunde cu nr. echipelor.

Implementarea se afla aici http://infoarena.ro/job_detail/488926?action=view-source

Am sa continui sa ma uit peste codul sursa..poate intr-adevar este un bug

[•devilkind]

Din cate imi aduc aminte parca problema asta se facea cu flux. E posibil sa mearga si greedy-uri dar nu stiu daca sunt corecte.
Gandeste ca momentele de timp de la 1 la 100 sunt noduri intr-un graf iar cei N voluntari reprezinta muchii intre aceste noduri, practic daca un voluntar poate sa fie ghid in intervalul a b, ai muchie de la a la b. Iar acum problema s-a redus la gasirea a K drumuri distincte de la nodul 1 la nodul 100, problema care se rezolva cu flux.

[•popoiu.george]

Fac cu flux si iau 10 puncte. Nu inteleg unde gresesc  .

Eu iau nodurile de la 1 la 101 nu de la 0 la 100 (le incrementez cu 1 la citire).

Destinatia e 101 si sursa nodul 102. M-am uitat de mai multe ori pe sursa si pare ok. E gresit algoritmul ?

Sursa : http://pastebin.com/D0GvS9BA

[•Fayed]

Si eu am aceeasi problema ca a lui George, algoritmul este le fel gandit, si iau 10 pcte si chiar nu stiu ce sa mai fac .
Idei ?

[•misino]

Aveti grija ca o muchie poate aparea de mai multe ori.
Trebuie sa inlocuiti if(fl[j]) cu while(fl[j]){--fl[j];...}
E