060 Critice

[nivan]

mersi... inseamna ca metoda mea e eronata

[•pauldb]

Scriu acest post, bazandu-ma pe urmatoarea presupunere: am 70 de puncte + 3 TLE, deci presupun ca am rezolvat problema corect, dar nu optim.

Pentru un graf de genul:
5 5
1 2 3
2 3 2
2 4 1
4 5 100
3 5 100

muchiile critice pe care le returneaza programul meu sunt 1,2,3.

Algorel a observat ca exista anumite tunele care au propietatea ca daca rezistenta lor creste in timp ce rezistenta
celorlalte tunele ramane la fel atunci va creste si numarul maxim de pisici pe care le poate trimite prin retea.

Daca cresc capacitatea pe doar pe muchia 1, iar celelalte capacitati raman neschimbate, atunci numarul de pisici [fluxul] nu se modifica. Nu este gresita definitia muchiei critice sau nu inteleg eu bine problema?

[nivan]

Pentru grafu' de mai sus muchia 1 nu e critica. Cam asta greseste si programul meu, desi nush de unde e. Cred ca-i de la flux, mai verfifca odata si vezi daca in functia de flux cand faci f(b,a) = - f(a,b), iti apare capacitatea lui BA = 0 sau e egala cu capacitatea lui AB.

[•pauldb]

Si atunci de ce iau 70 de puncte? 

[nivan]

Mda, faptul ca programul ia 7 teste si restu TLE (adik nu ia nici un WA).... totusi din cum am inteles eu enuntul muchia 1 nu e critica

[•pauldb]

Interesant...
Acum mi-am modificat algoritmul. Pe testul de mai sus imi da acum doar muchia 1. Si tot 70 de puncte + 3 TLE iau.
Poate cineva sa ma lamureasca?

[nivan]

Probabil ca printre testele de la evaluator nu exista test care sa semene ca structura cu ala.

[u-92]

Interesant...
Acum mi-am modificat algoritmul. Pe testul de mai sus imi da acum doar muchia 1. Si tot 70 de puncte + 3 TLE iau.
Poate cineva sa ma lamureasca?

in legatura cu testul care l-ai postat raspunsul e 0, nu exista nici o muchie critica. Fluxul maxim in retea e 3 (capacitatea muchiei 1->2). Muchia critica e cea care daca ii maresti capacitatea cu o unitate creste si fluxul maxim in retea. cand maresti capacitatea muchiei 1->2 fluxul maxim ramane 3.

[•pauldb]

Multumesc u-92.
Imi cer scuze pentru posturile inutile.

Mai am o singura intrebare [sper]: Pot presupune ca rezistentele sunt > 0? Iau Wa pe testul 9 si daca rezistentele pot si fi si 0, atunci cred ca acesta este motivul.

[•tm_radu]

Hmmm....am facut flux-ul si cele 2 DF()-uri, insa iau TLE pe testul 8. Este vreun caz special?

[•pauldb]

Nu este. Optimizeaza fluxul.

Presupun ca omori fluxul BFS-ul cand ajungi in destinatie cum a scris Silviu mai sus, nu?

[•tm_radu]

Da...si am retinut vecinii in liste de vecini folosind vectori.

[•anouk]

Hmmm....am facut flux-ul si cele 2 DF()-uri, insa iau TLE pe testul 8. Este vreun caz special?

same here  ... would appreciate a hint

[•Marius]

Am rezolvat cu algoritmul lui Dinic si merge mult mai greu decat cu cel al lui Edmonds Karp. E normal ? Totusi, e adusa o imbunatatire ..

[•wefgef]

Cred ca nu faci ceva bine.

Timpii mei sunt destul de buni: http://infoarena.ro/job_detail/84939

[•nash]

Nu imi este clar enuntul .. cum poate sa creasca rezistenta  ?? mi se pare firesc ca cel mult sa ramana aceasi dar nu sa creasca ... "Algorel a observat ca exista anumite tunele care au propietatea ca daca rezistenta lor creste in timp ce rezistenta celorlalte tunele ramane la fel....." , nu vad nimic care ca explice mai clar ce anume vrea se vrea prin acesta fraza ...

[•Dastas]

Daca ai un graf cu 4 noduri si urmatoarele muchii + capacitati:

1 2 3
2 3 100
3 4 100

Capacitatea de la 1 la 4 este 3. Dar daca maresti capacitatea pe muchia 1 2 la 10, capacitatea de la 1 la 4 va fi 10. Daca in schimb maresti capacitatea pe muchia 2 3, capacitatea de la 1 la 4 tot 3 va ramane. Problema cere gasirea acestor muchii (cum e 1 2 - critica).

[•nash]

ok , am intales .. merci

[•anna_bozianu]

Am implementat fluxul in doua moduri -> Dinic si cu preflux. E drept cu Dinic a mers un pic mai repede dar implementarea cu preflux mi se pare mult mai usoara si destul de rapida. Imi poate spune cineva la date mai mari  performantele celor doi algoritmi ar putea sa difere mult ?

[•ciprianf]

Vedeti ca s-a blocat evaluatorul la Dorin Oltean

[•marcelcodrea]

Probabil a fost oprit din cauza concursului preONI ! Nu cred ca ii vor da drumul mai devreme de duminica ora 9, cand e trecuta in program evaluarea surselor, desi nu ar strica sa se faca o evaluare diferentiata a surselor trimise la problemele din arhiva !

[•wefgef]

Din pacate nu se poate face o evaluare diferentiata...

Evaluatorul va fi pornit maine dimineata cand vom face evaluarea live pentru runda finala preONI.

[•ooctav]

in rularea programului pe exemplu muchia 4 - 5 are flux 6
dar daca fluxul ar fii
4 - 5  -> 5
4 - 3  -> 2
3 - 5  -> 4

vreau sa spun ca vectorii obtinuti prin parcurgerile DFS nu ar mai duce la rezultatul corect desi fluxul ar fii bun

[•Bogdan_tmm]

Tocmai m-am lovit si eu de problema asta. In functie de cum gaseste fluxul, solutia poate fi buna sau nu ....  
Probabil trebuie facui fluxul intr-un anume fel 

[•mouse_wireless]

Se intampla ceva interesant la problema asta.

Am luat 100 de puncte pe ea dar timpii mei sunt mult mai slabi decat cei obtinuti de alte surse. Adica cel mai prost timp pe care l-am obtinut e de 124 ms, iar altii s-au incadrat in 30-40... problema e de la fluxul meu pe graf neorientat care se misca foarte incet.

Dar partea dubioasa e ca algoritmul meu de flux pe graf orientat (implementat pentru /problem/maxflow), ia timpi foarte buni. Cel mai prost timp pe care il obtin acolo e 8 ms iar din ce vad timpii obtinuti de alte surse se duc undeva la 20-30 ms. Si singura schimbare intre cei doi algoritmi e ca daca am muchia x->y de capacitate C, atunci capacitatea muchiei y->x e tot C (nu 0 asa cum era la graf orientat).

M-am uitat prin alte surse si vad ca majoritatea au tinut o matrice pentru flux si capacitate. Eu nu am facut asa ci le-am tinut minte in listele de adiacenta (mi s-a parut mai eficient din punct de vedere al memoriei si intr-adevar vad ca memory-wise sursa mea sta bine comparativ). Ma gandesc ca poate de asta iau timpi atat de slabi dar then again daca asta e problema de ce iau timpi foarte buni pe graf orientat?

EDIT: surca aici http://www.infoarena.ro/job_detail/1466457?action=view-source
o sa incerc sa fac si eu o implementare cu matrici sa vad daca asta e problema

E vreo optimizare de care ar trebui sa stiu? Ma tot framanta asta 

EDIT2: Am implementat cu matrici si am mai facut niste mici optimizari si am ajung la ~80 ms.. dar e still de doua ori mai mult ca alti timpi. Totusi ramane ciudat faptul ca implementarea initiala tot scoate timpi mai buni pe grafuri orientate; are cineva o explicatie?