infoarena

S-a terminat inca o runda din concursul USACO. Si am facut iarasi 2/3 :( si sunt foarte curios cum se face problema cowrig de la Silver. Poate cineva sa ma ajute?

Eu cred ca se face cu backtracking pur!!(ma rog nu chiar atat de pur doar  foarte putine optimizari).
Fiecare pozitie se renumeroteaza cu 0..24 cu formula (i - 1) * 5 + j.
Dupa care aplici algoritmu de generare a combinarilor(unul destul de eficient gasesti si in manualu de Tudor Sorin!!) pentru fiecare pozitie i cu 0 <= i < 25(desi ai putea sa te opresti pe la 19) si numeri solutiile.Mai ramane sa faci o functie destul de eficienta care sa-ti evalueze daca ai ajuns la o solutie valida.Cam la partea asta am bushit eu in concurs(am considerat ca o pozitia curenta din stiva trebuie sa fie legata de o pozitie care se afla mai jos de ea in stiva - programu meu nu prindea cazuri in care solutia avea forma literei "U") si am pierdut o groaza de teste. :oops:
Am inteles ca se poate gasi o solutie si mai eficienta(o programare dinamica) dar inca mai ma chinui sa fac o implementare eficienta.Poate imi dati voi vreo idee!!pls!

Am citit si eu problema si cred ca backtracking ar fi trebuit sa se incadreze fara problema in timp... sunt doar C(25, 7) = 480.700 posibiltati, deci foarte putine... mai ramane doar verificare ca este conexa .. o verificare triviala ar trebui sa fie de ajuns (ar fi O(1) oricum.. cu o constata mica)

Daca pui conditii k-lumea poti sa faci programu sa ruleze in 0.01 sec chiar si daca folosesti lee ca sa verifici legatura dintre blocuri. :D

:shock: Pe mine ma imbata de cap problema secret de la Gold. Cine poate sa ma faca si pe mine sa inteleg exact care e faza cu cararile alea.
Deci o carare e bidirectionala. Atunci ei imi dau lungimea ei , in formatul  x y l
asta inseamna pt mine ca a

• [y] = a[y]
• = l

si mai incolo ei imi dau cararea y x si alt l ...
deci asta inseamna ca invers are alta lungime ??
spre exemplu testul 2



Dar daca mi se da x y -> l nu tot timpul mi se da si y x -> si un alt l.. Lamuriti-ma si pe mine cum sa iau aici..

si inca o kestie.


Asta inseamna ca pot fi mai multe arce intre x si y ?

Oricum alg meu e o cautare binara si un flux.. dar fac numai 2 teste..  :cry:

Sunt mai multe muchii intre 2 noduri

Ah, si  atuncia dc imi dau
x y l 0
..
y x l1

atuncia intre x si y am 2 drumuri de lungime l1 si l0
si intre y si x la fel. nu ?

Da mah, asa.

Ok, acuma am trecut de faza asta si am scris alg, da iau tle pe 6, 9-12 :(
Fac oare ceva in plus la algoritm ? Eu fac o cautare binara pt cea mai lunga poteca
si apoi ii bag un flux sa vad dc am t drumuri pentru acea poteca...
Sugestii de optimizare ? :P

Sunt algoritmi de flux mai buni decat Edmons Karp dar ar trebui sa mearga simplu cu Edmonds Karp ... Tu cum gasesti drumurile de marire a fluxului? Cum iti reprezinti graful? O idee de optimizare e ca in cazul maririi dimensiunii muchiei maxime nu trebuie neaparat sa pornesti de la flux 0 ci poti sa pornesti de la fluxul anterior.

am bagat optimizarea aia sa nu pornesc de la flux 0 cand cresc si am mai luat un test (11)   :lol:
da la restu tot tle.. deci cred ca trebuie sa bag alt alg de flux.

Mai detaliat , graful mi-l tin cu liste de vecini ca sa mearga repede cand caut un drum. si mai tin normal c[j] - cap muchiei, f[j] - fluxul.. si o matrice de pointeri la nod a unde a[j] tine capatul unei liste in care is toate muchiile de la i la j.. si de fiecare data cand pornesc un flux cu o muchie maxima noua, vad cate dintre muchiile din lista lui a[j] sunt mai mici si imi dau seama cat va fi c[j]..  :roll:

Daca tii cu liste probabil folosesti pointeri care merg foarte incet. Ca sa mearga pur si simplu iti trebuie o matrice de C pentru capacitati si F pentru flux... muchiile le tii intr-un vector ca sa construiesti C-ul la fiecare iteratie a cautarii binare. Deci, in primul rand fara pointeri. Apoi, iei valorile muchiilor le sortezi (nu cu qsort, incearca altceva.. sort() din STL sau heap-sort, nu stiu) , elimini valorile egale si faci cautare binara doar pe valorile din vectorul ala. Ah, cand faci flux banuiesc ca incerci sa aflii doar flux de valoare T nu flux maxim. Keep it simple, ca merge in limita de timp... la limita, dar intra :)

:lol:  :lol:


pointers suck ass ... Merge mul mai r/d fara pointeri...
Am scris de la inceput totul cum zicea si domino cu keep it simple si in sfarsit a mers..
( o kestie ciudata era ca dadea kiks pe unele teste daca declaram matricea de vecini char... nush dc ca oricum orice elem din matricea de vecini < 255.. da oricum acuma merge :P )

Pai daca lucrezi in C char este de la -128 la 127.. iti trebuia unsigned char.