USACO Feb 05

[•bogdan2412]

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?

[•JEULETZ]

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

[•domino]

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

[•JEULETZ]

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.

[•ParrAzitU]

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

Cod:

----- Test Case 2 ------
2 2 2
1 2 1
2 1 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.

Multiple trails might join a pair of landmarks.

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:

[•greco]

Sunt mai multe muchii intre 2 noduri

[•ParrAzitU]

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 ?

[•greco]

Da mah, asa.

[•ParrAzitU]

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 ?

[•Cosmin]

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.

[•ParrAzitU]

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

[•domino]

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

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

[•ParrAzitU]

:lol:  :lol:

Results for program 'secret' (lang='C++'):

PROB: secret

LANG: C++

Compiling...
Compile: OK

Executing...
Test 1 OK [0.01 secs]
Test 2 OK [0 secs]
Test 3 OK [0.08 secs]
Test 4 OK [0.05 secs]
Test 5 OK [0.04 secs]
Test 6 OK [0.29 secs]
Test 7 OK [0.02 secs]
Test 8 OK [0.1 secs]
Test 9 OK [0.2 secs]
Test 10 OK [0.28 secs]
Test 11 OK [0.17 secs]
Test 12 OK [0.26 secs]

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 )

[•domino]

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

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