infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Adrian Diaconu din Decembrie 16, 2007, 18:15:42


Titlul: 622 Gather
Scris de: Adrian Diaconu din Decembrie 16, 2007, 18:15:42
Aici puteţi discuta despre problema Gather (http://infoarena.ro/problema/gather).

Titlul: Răspuns: 622 Gather
Scris de: Andrei Homorodean din Decembrie 17, 2007, 15:30:21
Vreun caz special la ultimele 2 teste? Se incadreaza, totusi, rezultatele pe int sau trebuie unsigned?

Titlul: Răspuns: 622 Gather
Scris de: Marius Stroe din Decembrie 17, 2007, 17:49:36
Am o complexitate de O(2^K * K^2 + KNM log N) si tot iau TLE. Trebuie mai putin ?

Titlul: Răspuns: 622 Gather
Scris de: Paul-Dan Baltescu din Decembrie 17, 2007, 17:52:53
Nu stiu daca trebuie, dar se poate mai putin. :) La precalculare poti face O(K^2 * M * log N).

Titlul: Răspuns: 622 Gather
Scris de: Marius Stroe din Decembrie 17, 2007, 17:58:33
Testul 5 nu prea intra in unsigned int. Mie mi-a mers doar cu long long.

Titlul: Răspuns: 622 Gather
Scris de: Stefan-Alexandru Filip din Decembrie 17, 2007, 21:58:08
Toate testele se incadreaza in unsigned int. Si eu m-am incurcat cand am incercat sa evit long long-ul, dar testele sunt corecte.

O( K*N*M ) merge mai repede in practica la precalculare.

Titlul: Răspuns: 622 Gather
Scris de: Andrei Grigorean din Decembrie 17, 2007, 23:12:58
Sa tot faci Bellman-Ford.

Titlul: Răspuns: 622 Gather
Scris de: Sima Cotizo din Ianuarie 05, 2008, 20:30:35
Citat din mesajul lui: Andrei Grigorean din Decembrie 17, 2007, 23:12:58
Sa tot faci Bellman-Ford.

Eu am implementat o sursa cu Bellman-Ford, nu stiu inca daca intra in timp (presupun ca nu), dar in memorie intra? Folosesc un vector de struct pt muchiile de la ei, pt muchiile create de mine folosesc o lista stl... si cam iau sigsev...

Titlul: Răspuns: 622 Gather
Scris de: Andrei Grigorean din Ianuarie 05, 2008, 20:45:06
Prostu a facut Bellman-Ford si a luat 100 cu timpi foarte buni. Poate te lamureste el mai bine.

Titlul: Răspuns: 622 Gather
Scris de: Airinei Adrian din Ianuarie 05, 2008, 20:52:45
Bellman-Fordu` trebuie sa arate ceva de genul (cel putin asa il fac eu)
Cod:
for(i = 1; i <= N; i++) D[i] = INF;
Q.push(src), D[src] = 0;
while(Q.size() > 0)
{
     j = Q.front(), Q.pop();
     for(k = 0; k < G[j].size(); k++)
       if(D[j]+G[j][k].y < D[ G[j][k].x ])
          D[ G[j][k].x ] = D[j]+G[j][k].y, Q.push(G[j][k].x);
}
D e vectorul de distante minime, G[ i ][ j ].x e al j`lea vecin a lui i iar G[ i ][ j ].y este costul muchiei.

Titlul: Răspuns: 622 Gather
Scris de: Sima Cotizo din Ianuarie 06, 2008, 12:23:42
Citat din mesajul lui: Airinei Adrian din Ianuarie 05, 2008, 20:52:45
Bellman-Fordu` trebuie sa arate ceva de genul (cel putin asa il fac eu)
Cod:
for(i = 1; i <= N; i++) D[i] = INF;
Q.push(src), D[src] = 0;
while(Q.size() > 0)
{
     j = Q.front(), Q.pop();
     for(k = 0; k < G[j].size(); k++)
       if(D[j]+G[j][k].y < D[ G[j][k].x ])
          D[ G[j][k].x ] = D[j]+G[j][k].y, Q.push(G[j][k].x);
}
D e vectorul de distante minime, G[ i ][ j ].x e al j`lea vecin a lui i iar G[ i ][ j ].y este costul muchiei.

Faci in ideea de BF, sa nu ai muchii inutil parcurse cum le parcurg eu cand le iau in ordine, nu?... mai era o chestie in Bellman-Ford, daca la un pas nu mai "imbunatatesti" nicio distanta, atunci poti opri algoritmul... cred ca asta ar aduce o imbunatatire in timpul de rulare...

Insa eu am alta problema :( aveam matricea C[ i ][ j ] de 4 mega in care calculam ca in articol, costul minim sa ajung in celula i cu detinutii din scrierea binara a lui j... am comentat-o ca sa vad daca intra doar muchiile, ar nu incap, tot iau MLE pe ultimele 3. Trebuie retinute muchiile in alt fel...

Mai incerc pana iese :D

Titlul: Răspuns: 622 Gather
Scris de: Airinei Adrian din Ianuarie 06, 2008, 12:41:39
Nu trebuie sa te complici, nu inteleg ce vrei sa spui prin muchii inutile, iar cum e scris codul folosind coada aia el se opreste cand nu mai apare nicio imbunatatire. Am vazut ca tu pui variabilele pe long long, lucru care nu este necesar, totul intra pe int.

Titlul: Răspuns: 622 Gather
Scris de: Stefan-Alexandru Filip din Ianuarie 06, 2008, 13:50:46
O optimizare pe care am facut-o este ca calculez la "o rulare" a Bellman-Fordului toate costurile de la un nod u la toate celelalte noduri pentru toate capacitatile.
Cod:
sorteaza muchiile dupa capacitati;
pentru fiecare nod
    initializezi costurile pe infinit;
    pentru fiecare capacitate in ordine descrescatoare
        Bellman-Ford (sau Dijkstra) cu muchiile care au capacitatea peste cea stabilita;
De altfel sunt doar K noduri intre care trebuie sa stii costurile, deci memorie este O(K3 + N)
E greu de spus care este complexitatea la rulare a Bellman-Fordului, dar in practica se descurca bine.

Titlul: Răspuns: 622 Gather
Scris de: Oltean Dorin din Aprilie 02, 2008, 12:12:10
m-am uitat in monitorul de evaluare si am vazut ca mai multa lume a avut la un moment dat probleme cu testul 5, si am si eu aceeasi problema ... imi puteti spune de la ce ar putea veni problema asta ?

Titlul: Răspuns: 622 Gather
Scris de: Toma Radu din Aprilie 02, 2008, 12:46:12
Incearca sa folosesti long long in loc de int.


Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines