140 Adapost

[ditzone]

Aici puteţi discuta despre problema Adapost.

[•unholyfrozen]

Am incercat sa rezolv problema astfel :
1.caut binar valoarea maxima ceruta (formez un graf bipartit , in prima multime = oamenii, in a doua adaposturile si introduc doar muchiile de cost  <=x la un moment dat)
2. pt acea valoare maxima fac flux maxim de cost minim.
Problema este ca pe testele de la 3 in sus mie nu imi gaseste nici prima valoare bine.
Mi se pare clara echivalenta : Daca fiecare nod din prima multime are asociat un nod din a doua multime, iar fiecare nod din a doua multime are asociat un nod din prima atunci exista un flux maxim de valoare N.

[ditzone]

ideea este buna, vezi sa nu fie de la implementare

[ag3nt_junior]

Ce metoda v-a condus la punctajul maxim? Am impresia ca evaluatorul are pretentii mari la zecimale...

[•gogu]

Cred ca metoda folosita de unholyfrozen e singura varianta corecta care intra in timp.
Cautarea binara merge mult mai eficient daca iti dai seama ca primul numar merge cautat prin cele N*N distante posibile si atunci nu mai ai probleme cu precizia.
Oricum, in enunt zice ca se considera ca e bine daca nu te abati cu mai mult de 0.001 de la rezultatul corect.

[ag3nt_junior]

Am calculat pentru fiecare soldat distantele pana la toate cele N adaposturi, pentru fiecare, retinand distanta minima. Acel maxim cerut de problema, nu e maximul dintre minimele calculate de mine? Am impresia ca ma insel aici. In problema spune ca se acorda 40% din punctaj pentru aflarea primului numar. Iar mie nu-mi acorda nimic.

Si.. in ideea de mai sus, cum calculez fluxul? Care este nodul sursa, si care destinatie?

[ditzone]

Te inseli .. nu e maximul dintre minime. Gandeste-te ca pentru doi soldati distincti tu poti obtine minimul in acelasi adapost dar intr-un adapost poate intra doar un soldat. Cat despre surse si destinatii pentru flux din moment ce fiecare soldat trebuie sa ajunga intr-un adapost si in concluzie in fiecare adapost trebuie sa ajunga cate un soldat o sa ai toti soldatii surse si toate adaposturile destinatii...

[•PuMa]

In afara de oprirea bfs-ului cand atinge nodul destinatie ce optimizari ar mai trebui sa fac la fluxul ala, ca imi intra in timp doar pentru testele 1..6 in rest iau TLE kiar daca incerc sa rezolv numai primul punct.    

[andreit1]

Incearca sa faci un greedy inainte sa incepi fluxul. Are complexitate mai mica si te aduce destul de aproape de fluxul maxim.

[VladS]

Pentru al doilea numar a facut cineva cu flux sau doar alg ungar intra in timp ?

[•domino]

Intra si cu flux. Nu cred ca a facut cineva ungar.

[•wefgef]

mi-ati putea spune va rog unde pot citi despre alg ungar? 

[•filipb]

Ori cauti pe google, ori daca nu este un articol la lot: 20 mai 2003 - Slatina

[VladS]

Mi se pare mai usor de citit de aici:
http://www.public.iastate.edu/~ddoty/HungarianAlgorithm.html.
Am inteles ca in general lumea prefera fluxu cu bellman cu coada.
Oricum alg ungar mie nu mi-a intrat in timp la problema asta.

[•Marius]

Greedyu meu are complexitatea O(N^2) si leaga soldatii cu adaposturile aleator. Am oprit BFu cand am ajuns in destinatie iar pentru aflarea distantei minime am implementat un Bellman Ford cu coada, clasic. Am mai folosit double. Voi ce optimizari sau idei aveti pentru ca m-am oprit la 50 p ...

[•Marius]

A incercat cineva un Hopcroft Karp ?   Vreau si eu niste detalii legate de Bellman Ford cu heap. I googled it!   

Eu m-am gandit sa folosesc heapu' pentru a pastra nodul cel mai aproape de sursa la al k-lea pas, 0 < k < N. Algoritmul se termina cand nu mai sunt elemente in heap sau cand un nod a fost introdus in heap de N ori, in cazul acesta existand un ciclu de cost negativ. Pe un drum de cost minim de la sursa la destinatie cresc fluxul.

Eu zic ca e in regula, voi ce ziceti ?

[•pauldb]

Pare bine. Eu cam asa am facut. Ca observatie: nu ai cum sa ai cicluri de cost negativ la problema asta (sper ca nu ma insel).

Off Topic:
Acuma multumita Academiei nici nu mai trebuie sa spui "I googled it", poti zice direct "am gugalit-o"... Unde ajunge si limba romana... 

[•thestick]

se poate face mult mai usor si mai rapid cu http://en.wikipedia.org/wiki/Simulated_annealing

[•devilkind]

esti sigur ca la problema asta merge simulated annealing. Adapost 2 se face asa, asta e topicu de la adapost 1.

[•CezarMocan]

Se poate lua 100 facand fluxul maxim de cost minim cu Dijkstra? Daca da, de ce optimizari e nevoie? (nu reusesc sa intru in timp la mai mult de 9 teste... )

[•wefgef]

Eu am facut Bellman-Ford la problema asta

[•CezarMocan]

M-am prins intre timp de ce imi depasea limita de timp . Mersi oricum.