291 Roy-Floyd

[•sima_cotizo]

pai .. solutia e simpla ...
 aplic royfloyd ... si caut sa micsorez distantele ... in cazul in care am gasit acesi distanta... caut sa maximizez numarul de muchii in cazul in care am gasit un drum mai mic... micsorez drumul si reactolizez numarul de muchii ....

Daca vrei neaparat poti sa faci un fel de roy-floyd in O(N^2 log N) folosind dijkstra cu arbori de intervale / heapuri... dar merge O(N^3)... fii atent la dimensiunile matricii... daca e prea mica poti sa dai peste alte variabile si sa le strici... eventual rescrie toata sursa, poate e un bug greu de sesizat!

[•nash]

 O sa o rescriu .. chestia este ca imi iese din timp .... asta ma enerveaza ... daca ar zice ca gresesc .. ar fi altceva ... insa .. iese din tim cu foarte putin ... matricea e dimensionata bine ... daca nu era .. apareau probleme de citire in afara locului unde a fost alocata .. sau aparea raspuns gresit ...

[•sima_cotizo]

O sa o rescriu .. chestia este ca imi iese din timp .... asta ma enerveaza ... daca ar zice ca gresesc .. ar fi altceva ... insa .. iese din tim cu foarte putin ... matricea e dimensionata bine ... daca nu era .. apareau probleme de citire in afara locului unde a fost alocata .. sau aparea raspuns gresit ...

Iese din timp cu foarte putin la absolut orice problema la care trimiti - asta pt ca la putin timp dupa ce depasesti iti este oprit programul

Legat de dimensiuni, e posibil ca tu sa accesezi ceva in afara matricii si acel ceva sa fie din intamplare adresa vreunui indice, pe care il modifici si sa iti iasa din timp... e foarte putin probabil, dar daca altceva nu e...

[•nash]

Cod:

for(k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++) {
				if(roymin[i][j]==roymin[i][k]+roymin[k][j])
					roymax[i][j]=max(roymax[i][j],roymax[i][k]+roymax[k][j]);
				else
					if(roymin[i][j]>roymin[i][k]+roymin[k][j]) {
						roymin[i][j]=roymin[i][k]+roymin[k][j];
						roymax[i][j]=roymax[i][k]+roymax[k][j];
					}
			}

eu nu vad nimic ne in regula ... tu vezi ?

[•sima_cotizo]

Pare corect... am dubii daca acel max e corect, parca trebuia o  banala adunare, dar... e foarte posibil sa gresesc.

Bun, am descoperit pana acu ca for-urile merg bine... sa fie de la citire? Eu unul am citit cu scanf si am luat 100 cu n^3... si din cate stiu sunt stream-urile mai incete... pe urma daca ai facut si tu cu scanf & printf ti-as fi zis ca poate ai niste matrici mult prea mari pe care el pierde timp sa le aloce, sau daca le initializezi tu pierzi timp pretios...

  altceva nu stiu de la ce poate fi, dar cea mai buna rezolvare este sa il rescrii peste vreo 2 zile, dupa ce ti-a iesit din cap problema... o sa fii mai relaxat atunci 

PS: daca vrei o sa iti dau PM cu sursa mea...

[•nash]

matricile le-am declarat global .. deci ele sunt initializate de la inceptu cu 0 ...
citirea am facut-o cu fscanf si scierea fprintf  .... matricile .. sunt la limita  roymax[257][257] ( cu 1 mai mult .. dar .. nu cred ca asta e problema .. )
initializarea pe care o fac eu .. este legata de roymax[][] , care reprezinta numarul de muchii dintre doua drumuri ... si care pentru i!=j este 0 in rest 1 .... si o fac la citirea matricei de costuri roymin ....
in ceea ce priveste pe max() .. e corect .. daca nu ar fi .. nu mi-ar da raspuns corect ... pe 50% din teste ... pe restul mie imi iese din timp .. nu da raspuns gresit ..+ .. am folosit max() din STL .. si apoi am si implementat un max .. acelasi punctaj  ... am incercat chiar si cu un if() ...ca mam gandit ca sunt prea multe apeluri .. tot degeaba.... iese din timp

[•Darth_Niculus]

 Si totusi are dreptate sima_cotizo ... dc e max-ul ala acolo? adica ar trebui direct roymax[j] = roymax[k] + roymax[k][j];  Stiu ca n-ar trebui sa infuenteze, dar.... n-ai de unde sa stii ce se intampla daca il scoti.... (pan la urma max insemna o operatie in plus).

[•sima_cotizo]

Dubios, matricea in care ai valoarea drumului dintre doua puncte nu o initializezi cu o val foarte mare?... Eu asa stiu ca trebuie

In rest e bine... foarte ciudat... inca o data te intreb, citesti cu streamuri? e foarte putin probabil sa fie de la asta... dar merita sa incerci si cu scanf...

Woops, de fapt chiar trebuie nr max de laturi pe care le parcurgi... e bine asa... ar fi dubios sa fie nevoie de o rearanjare a instructiunilor de genul

Cod:

if ( lungimea e mai mica) actualizeaza lungimea si nr de muchii = 0;
if ( lungimea e egala si nr de muchii e mai mare ) actualizeaza nr muchii;

[•nash]

 Este nevoie de max() pentru ca atunci cand ai gasit un drum de aceasi lungime maximizesi numarul de muchii necesare parcurgerii drumului .. adica ei maximul dintre nr muchii actuale .. si cea noua gasita .. 

Initializarea de care vorbesti e facut la inceput ... cand se da graful .. daca intre ori si ce doau noduri se da o muchie nu mai este nevioe sa initializez cu ceva foarte mare ...

 Daca interschimbi .. nu ajungi nici unde .. am incercat
 Am mai spus .. citesc cu fscanf() si scriu cu fprintf()

[•sima_cotizo]

Da, ai dreptate... n-am citit toata problema ... daca nici una din problemele astea nu e... atunci nu stiu. Daca vrei neaparat fa dijkstra cu heapuri / arbori de intervale ... sau rescrie toata sursa. Mie mi-a mers cu n^3... daca vrei iti dau diseara pm cu sursa mea / imi dai tu cu a ta, ca sa vedem... [acum plec la scoala ]

[•astronomy]

Nu se merita sa faci dijkstra cu heap sau arbori de intervale fiindca ai O(N^2) muchii. Nu imi dau seama de iei TLE, poate ai pus matricile alea pe long long? (merge mai incet long long si int e de ajuns)

[•nash]

 Gata .. acum merge .. intradevar .. aveam declarata matricea de elemente long long .. eu citisem ca fiecaer muchie are lunfimea intre 1 si 100 000 si de fapt scria ca fiecare drum este mai mic decat 100 000 deci ... asta era ..
         Multumesc

[•DonPushme]

Cod:

roymax[i][j]=max(roymax[i][j],roymax[i][k]+roymax[k][j]);

de ce la actualizarea nularului de drumuri minime apare suma drumurilor de la "i" la "k" si de la "k" la "j" in loc sa se faca produs .... adica ..nu trebuia

Cod:

roymax[i][k]*roymax[k][j]

?
 

[•tm_radu]

Nu, deoarece se cere numarul maxim de muchii ce le poate avea un drum de la i si j. Produs se foloseste, de exemplu, la numarul total de drumuri disjuncte de lungime minima de la i la j.

[•p1ccolino]

Aplic roy floyd, actualizez matricea costurilor, daca am gasit drum mai mic sau daca noul drum este egal cu cel din matricea costurilor, verific daca nr de arce este mai mare si actualizez daca trebuie.
nu inteleg unde gresesc...
Cine m-ar putea ajuta?

[•samuel91]

Din ce cauza apare "Killed by signal 11(SIGSEGV)"

[•Mishu91]

Citeste documentația. Probabil ieși din limitele unui vector sau ai declarat prea mult.

[•hulparuadrian]

Mi-a tocat nervii vreo 3 ore problema asta.  :aha:In mintea mea, in loc sa calculez numarul de maxim muchii calculam numarul de drumuri de lungime minima. Trebuia sa casc ochii mai bine inainte sa ma apuc de lucru  .

PS: intra cu Roy-Floyd foarte usor in timp

[•lessan]

presupun ca greseala e la cum calculez lungimea maxima dar nu vad unde

Cod:

 if(i!=k && j!=k && a[i][j] >= (a[i][k]+a[k][j]))
                {
                    if(a[i][j] == (a[i][k]+a[k][j]))
                        v[i][j] = max(v[i][j],v[i][k]+v[k][j]);
                    else v[i][j] = v[i][k]+v[k][j];
                    a[i][j]=a[i][k]+a[k][j];
                }

[•ioan32]

Cine poate lasa o solutie la problema ?

[•ioan32]

Cine poate lasa o solutie la problema ?