622 Gather

[•DITzoneC]

Aici puteţi discuta despre problema Gather.

[•peanutz]

Vreun caz special la ultimele 2 teste? Se incadreaza, totusi, rezultatele pe int sau trebuie unsigned?

[•Marius]

Am o complexitate de O(2^K * K^2 + KNM log N) si tot iau TLE. Trebuie mai putin ?

[•pauldb]

Nu stiu daca trebuie, dar se poate mai putin. La precalculare poti face O(K^2 * M * log N).

[•Marius]

Testul 5 nu prea intra in unsigned int. Mie mi-a mers doar cu long long.

[•Prostu]

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.

[•wefgef]

Sa tot faci Bellman-Ford.

[•sima_cotizo]

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

[•wefgef]

Prostu a facut Bellman-Ford si a luat 100 cu timpi foarte buni. Poate te lamureste el mai bine.

[•astronomy]

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.

[•sima_cotizo]

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

[•astronomy]

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.

[•Prostu]

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(K³ + N)
E greu de spus care este complexitatea la rulare a Bellman-Fordului, dar in practica se descurca bine.

[•Dorin]

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 ?

[•tm_radu]

Incearca sa folosesti long long in loc de int.