infoarena

Aici puteţi discuta despre problema Critice (http://infoarena.ro/problema/critice).

In articolul cu solutii de la Runda 3 se spune complexitate finala O(m^2*n+m) . Eu am aplicat un Edmonds-Karp si dupaia 2 bf-uri.Dar am obtinut doar 60 de puncte. Dupaia am mai imbunatatit un pic si am luat 70.Ce ar trebui sa fac sa iau 100? Sau ce gresesc? Pun sursa mai jos:

...  

In prima versiune de program foloseam si o matrice in care retineam fluxul,dar nu avea rost sa mai fac cateva operatii in plus, astfel doar cu matricea pt capacitati am luat 70.

Poate e o idee buna sa opresti BFS-ul din flux cand atingi nodul final (daca nu faci asta deja)  :idea:

Multumes Silviu. Uitasem,dar in timpul contestului il opream. Oricum a trebuit sa mai fac ceva modificari ca sa intre si asa la limita.(am sters sursa de pe forum)
  :-({|=

Sa vedeti o chestie misto la evaluator
Tot luam 90 pe critice cu TLE pe testu 8...

Asa ca am optimizat multe kestii care le faceam cam brute in cod, ca l-am scris in graba
si am submitat si am luat 100, ce e misto, e ca am depasti 1,03 ala de dinainte si am luat 100.. pana mea vedeti si voi :
Cam care ar putea fi cauza acestei 'intamplari' ?  :-k

Grozav!  :mrgreen: .. Poate prima data scria 1.03 fiindca cam pe atunci a fost oprita sursa ta de evaluator... cat despre faptul ca ambii timpu sunt peste 1s cum explica si in monitor, sunt orientativi, nu sunt timpii adevarati.  :-'

E ceva special la testul 9 de nu-l prind?

Da. E cel mai greu. L-am construit astfel incat sa pice fluxurile neoptimizate (cat de cat) ;)

Nu imi iese din timp, primesc WA (~0.38 sec).

Am si eu niste probleme la implementare....

1.ce algoritm ar trebui folosit pt a calcula fluxul ca mie imi iese din timp la vreo 3 teste si cu ala cu "djikstra" si cu "bfs".
2.nu inteleg totusi o chestie!
din cate inteleg eu, trebuie sa vad pentru fiecare muchie care are capacitatea 0 acuma in graful rezidual, daca exista un drum de la 1 la N care sa treaca prin ea.....si totusi daca facem Bfs de la 1 la unul din capete si apoi de la N la celalalt capat, e posibil sa gasim solutie, dar solutia care o gasim noi nu e in concordanta mereu cu ce ar trebui sa testem (din cate am inteles eu ! )...
ma refer la faptul ca pentru a ajunge un capat la 1 si altul la N ne-am putea folosi la un moment dat de aceeasi muchie...iar daca parcurgem odata de la i la j iar apoi la j la i zic eu ca e aceeasi chestie cu a nu trece prin muchia aia (la fluxuri..)

sper ca a inteles cineva ce am vrut sa spun...
ideea e ca am vazut multi de 100,  si cred ca eu fac ceva gresit, sau am inteles aiurea ceva !

ok, sper sa-mi raspunda si mie careva  ](*,)  ](*,)

E o problema falsa aici :). Sa zicem ca ai muchia (a, b) care este saturata (=capacitate 0 intr-una din cele doua directii in care poate fi orientata). Acum  se pune problema amintita de tine: avem drum (pe muchii nesaturate) de la sursa (nodul 1) la unul din capete si, analog, drum de la celalalt capat la N. Din cate am inteles, tu reclami faptul ca drumurile folosite nu sunt elementare (folosesc o muchie de doua ori). Pai: 1. prin BFS-ul pe care il fac imi garatez faptul ca este elementar si 2. nu prea ma intereseaza aspectul (din moment ce am un drum neelementar am si unul elementar).

Nu stiu daca am inteles exact nelamurirea ta. Daca ti-am raspuns "pe langa" mai posteaza (ceva mai clar).

Cat despre algoritmul de flux: al meu utilizeaza BFS (si ti-l recomand cu caldura in locul celui cu Dijkstra). Eventuale optimizari aduse:

1. Opresc BFS-ul cand ajung cu drumul in crestere in nodul N (nu mai are rost sa explorez restul grafului)
2. Graf pastrat ca lista de muchii dar pastrate pe vectori (si nu cu liste care implica pointeri => timp mare de executie) => O(N + M) timp de executie pentru BFS

Spor la treaba,

Silviu

Am inteles pana la urma ambele metode de rezolvare ca idee, intra in timp (a doua , prima pierde 3 teste ), dar totusi iau Too Bad la cateva teste, inclusiv testul 1!
     Am facut si prima varianta si tot nu a iesit bine (inafara celor 3 teste care imi ieseau din timp) si zic eu ca problema ar fi pe undeva pe la flux..
eu nu am facut niciodata implementari cu grafuri neorientate la fluxuri....as vrea sa stiu daca este vreo diferenta majora pe undeva sa nu (eu doar am "dublat" muchiile, adica am consideram ca daca am la intrare pereche i j c , atunci am si j i c, in rest am facut exact ca pe cazul orientat).
     Si daca ati putea sa ma ajutati sa-mi dati testul 1 sau unul asemanator...


Cippi  :?

nici eu nu stiam flux pe gr neorientate.. dar am stat putin si m-am gandit si nu era chiar asa de greu...
o indicatie ar fi ca pe o muchie nu poti sa ai flux in ambele directii (nu ar fi optim)..

M-am mai gandit si e cam acelasi lucru.....cred ca stiu bine la ce te referi...la urma urmei oricum o sa ai flux pe amandoua directii. Am sa incerc asa sa nu pun pe amandoua la inceput, dar nu cred ca aici e problema.

Ideea e ca eu am precizat, problemea mea nu e timpul de executie, ci faptul ca obtin Too Bad la cateva teste si nu inteleg de ce....de asta as vrea testul 1 :) ..

Cippi  #-o

..intre timp mai verifica daca la gasirea drumului de crestere, parcurgi si muchii in sens invers.. si daca o faci corect..

Exista vre un algortim de flux maxim mai bun decat Edmonds-Karp? Nu inteleg de ce iau TLE la 3 teste pentru ca am urmat sfaturile de mai sus. E pe undeva vreo kestie de "finetze" ?  :-k

Nu prea. Probabil ma repet: implementarea mea foloseste un flux cat se poate de normal optimizat cum am spus mai sus (omor BFS-ul cand ajung in destinatie). Mai gadila un pic codul.. trebuie sa iasa ;)

Silviu

Am patit o chestie ciudata. In enuntul problemei se spune ca N maxim este 1000. Deci, am declarat ceva de genul : lista* a[1001] (listele alea sunt niste banale liste de adiacenta alocate dinamic).
Am luat 30 de puncte iar pe restul testelor "Invalid memory reference". Am pus apoi, "lista* a[10001]" si am luat 50 de puncte, pe restul testelor luand "Invalid memory reference". am pus si mai mult intre parantezele patrate, 500001, si am luat 40 de puncte si pe restul testelor TLE-uri.
Nu prea inteleg, care e faza?

Am facut apoi o varianta cu liste de adiacenta pe vectori si am luat 50 de puncte, si iarasi nu prea inteleg de ce, pt ca pe varianta cu matrice iau 60 de puncte. Macar 10 - 20 de puncte in plus sa fi luat, pt ca teoretic e mult mai rapida rezolvarea asta.

Vreun sfat?

pai cel mai probabil ai implementat gresit vreo chestie minora pe-acolo (se intampla des, [mai ales la OJI  ](*,)] ).. daca nu vezi nimic neobisnuit, incearca sa rescrii codul care lucreaza cu listele si fa-l cat mai clar posibil.. daca tot aceasi problema, poti sa-mi trimiti codul pe [email protected] sa arunc o privire pe el

Am si eu o intrebare. Nu-mi iese testul 9.  ](*,)  Am vazut pe forum ca nu sunt singurul care a avut aceasta problema. Nu iau TLE, ci W.A. Vreau sa intreb daca greseala mea este la algoritmul meu de flux. Este primul pe care l-am implementat pana acum si am vazut ca testul asta este facut tocmai sa fice fluxurile neoptimizate. Eu fac in felul urmator:

1. Tin 2 matrici, 1 de capacitati, 1 de ce capacitate reziduala mai am pe ramura i j
2. Aceasta a 2-a matrice este initial initializata cu -1.
3. Fac Edmonds-Karp. Adica fac un BF.
4. Iau drumul de la BF fac o functie update care imi schimba in matricea reziduala. Astfel daca in matrice drumul de la i la j != -1, pur si simplu scad sau cresc dupa cum trebuie. Daca drumul este chiar -1. Atunci fac asa:


Cam atat. Ma gandesc ca poate problema e undeva aici. Daca cineva poate sa ma ajute i-as fi recunoascator ca nu stiu ce sa mai fac.  :(  :(

 Imaginea corespunde expemplului din problema.

 In exemplu zice ca numai muchiile: (1,2) (1,4) sunt critice.

 Totusi muchia (4,5) e si ea critica... nu?   Am inteles eu enuntul gresit? Desi am citit de cateva ori problema.

Fluxul maxim in graful din exemplu este 9. Asta inseamna ca vei pompa pe muchia 1-2 2 unitati de flux, iar pe muchia 1-4 restul de unitati. Daca maresti capacitatea muchiei 4-5 de la 7 la 8, fluxul tot 9 ramane, nu poate fi mai mult pentru ca din nodul sursa 1 nu pornesc decat 2 muchii ( 1 2 si 1 4 ) cu suma capacitatilor 9, deci in retea sigur nu exista un flux mai mare de 9. In concluzie, daca maresti capacitatea muchiei 4 5, nu creste si fluxul maxim, deci muchia nu e critica.

 Ai dreptate.... ms  :D  nu mi-am dat seama ca graful e neorientat lucram cu el orientat si imi iesea fluxu maxim 8.  ](*,)

 Exista vreo diferenta majora intre fluxul pe graf neorientat si cel pe graf orientat. Pe graf orientat e banal.... da pe graf neorientat nu-mi prea dau seama decat de asta:  :oops:

 Daca am trimis un flux prin (U -> V) atunci prin (V -> U) nu mai las sa se mai intoarca decat fluxul din (U -> V) chiar daca capacitatea lui (V -> U) poate e mult mai mare.

 Eu fac cu Edmonds-Karp si 2 BFS-uri. Problema e ca imi ia niste too bad-uri.... am vazut ca a mai avut si cippi problema asta. Cred ca e de la flux... probabil fac ceva gresit.... graful fiind neorientat, algoritmul meu lucreaza ca si cand ar fi orientat. De la BFS-uri nu e sigur.  :?

 Singura concluzie la care am ajuns e ca: Mai exista si alte diferente, inafara de aia de mai sus, intre fluxurile pe graf orientat si neorientat.
 Daca am scris vreo prostie mai sus  :oops: ... desi imi pare foarte logic totul.

 Deja mi-e rusine ca ma chinui de 3 zile la un flux si 2 BF-uri.  ](*,)

Nu e mare diferenta intre cum se face fluxul pe un graf orientat si unul neorientat. Singura diferenta este ca in timp ce la un graf orientat, daca ai muchia x->y, pe y->x pui capacitatea 0, la graful neorientat si x->y si y->x vor avea aceeasi capacitate. In rest e la fel.

mersi... inseamna ca metoda mea e eronata :D

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.


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?

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.

Si atunci de ce iau 70 de puncte?  :eyebrow:

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

Interesant... :-k
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?

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

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.

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.

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

Nu este. Optimizeaza fluxul. :)

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

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

same here  :sad:... would appreciate a hint

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 ..

Cred ca nu faci ceva bine.

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

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 ...

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).

ok , am intales .. merci :)

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 ?

Vedeti ca s-a blocat evaluatorul la Dorin Oltean

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 !

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

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

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

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  :-k

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?