infoarena

Aici se pot pune întrebări legate de problema Planificare (http://infoarena.ro/problema/planificare) de la Runda 2 (http://infoarena.ro/algoritmiada-2012/runda2) a concursului Algoritmiada 2012.

Timpul alocat întrebărilor este de 1 ora. Întrebările vor fi formulate astfel încât să se poată răspunde cu DA sau NU. În caz contrar sau în cazul în care întrebarea își găsește răspuns în enunțul problemei, răspunsul va fi FARA COMENTARII.

Am adaugat feedback pe testele 1 si 6 si am facut o mica reevaluare :) Re-verificati-va sursele  :banana: Succes!

Cate teste sunt

Fara comentarii.

Timpul alocat întrebărilor s-a scurs. Multă baftă în continuare!

Atunci de ce ai lasat acest comentariu.... :-' :-'

o intrebare care nu are legatura cu problema,
cand trimit sursa la problema triplet imi afiseaza 2 teste ca sunt bune  inseamna ca restu leam gresit? sau imi apar doar 2?va rog raspundeti sa stiu

Doar 2 teste apar. Restul cand se termina proba...

Cum se facea planificarea?

Se poate sa imi dea cineva linkul articolului cu solutii sau sa imi explice cum se facea problema aceasta ? Nu ma prind ce am gresit  ???

Se tinea un multiset cu timpul de final al programului de pe fiecare post TV( initial un multiset cu K de 0). Se sortau cele N programe dupa timpul de final crescator si apoi se parcurgeau in aceasta ordine si se cauta binar postul TV care are timpul de final <= timpul de start al programului curent. Acest post TV era cel pe care se difuza. In cazul in care nu exista => programul curent nu se difuzeaza.

Sper sa intelegeti :).

Mersi, dushmi. :)

Nu ai putea folosit lower_bound (http://www.cplusplus.com/reference/stl/multiset/lower_bound/) in loc de cautare binara?

Se poate folosi si lower_bound.

lower_bound e de fapt cautare binara ;) si da, evident ca se poate folosi. La el m-am referit.

nu inteleg la ce e nevoie de cautare binara, multiset tine oricum minimul in capat, deci poti sa verifici daca acesta e <= timpul de start al programului curent, nu?

eu am facut in concurs cu priority_queue care e tot heap dar ceva mi-a scapat ca tot 10 pct am luat... (nu a mers decat cand k==1)

ce imi scapa?

Nu este bine neaparat sa plasezi programul curent pe postul TV care se termina cel mai repede.

De exemplu pentru:


Daca facem asa cum zici tu avem:


Deci se obtine raspunsul 3. Raspunsul corect pe acel test este 4 si se obtine asezand programele astfel:

Dushmi, ai lucrat cu un singur multiset sau cu un vector de K multiseturi ?  #-o

L.E : Nu inteleg o singura chestie, si anume : daca folosesc lower_bound imi gaseste prima valoare <= decat timpul meu de start la emisiunea curenta, iar eu am nevoie de cea mai apropriata si ajung la o sol greedy gresita

Actually lower_bound iti gaseste prima valoare care nu e < x (deci e = sau > ).
E destul de clar ca daca intorci iteratorul ala cu o pozitie in spate obtii ultima valoare < x, ce-ti trebuie tie.
Nu ai de ce sa folosesti K multiseturi, gandeste-te mai bine la ce faci. Pentru fiecare televiziune tii o singura valoare tot timpul, ora terminarii ultimului spectacol.

Sau poti sa sortezi acel multiset descrescator si atunci lower_bound iti va returna valoare de care ai nevoie.

Concursul s-a incheiat. Acest topic a fost creat pentru a raspunde intrebarilor din timpul rundei.

Pentru a discuta pe marginea problemei Planficare va rog sa folositi acest topic (http://infoarena.ro/forum/index.php?topic=6939.0).