Paul, in sursa "luni 29 decembrie 2008 02:50:46" sunt cateva secevnte care nu le inteleg. De ce in bellmanford() ai pus un while(!stop), si de ce returnezi Vmin * Dist[D] ?

imi explicati si mie va rog "La fiecare pas in construirea ciclului, vom alege intotdeauna muchiile de intoarcere inaintea muchiilor de arbore." . Muchiile de intoarcere is alea care formeaza ciclu? Si alea de arbore care nu formeaza? De unde imi pot da seama care muchii is care? Explicatie e putin succinta.
 

Pai adaug un element dupa conditiile care le-am pus mai sus. Eu zic ca e ok. Cum altfel as putea restrictiona adaugarea?Nu prea ar trebui sa iau TLE. Dar ar fi mai bine decat WA pe 4 teste. Am incercat cum ai zis si tu: cu doua cozi. Algoritmul e ceva de genu:

cat timp coada 1 nu este vida{
     verifica vecinii lui a[x1][y1]{
        daca a[x2][y2] == a[x1][y1]

               daca b[x2][y2] > b[x1][y1] || b[x2][y2]  , b[x2][y2] = b[x1][y1] si adaug elementul in coada 1
   
        daca a[x2][y2] != a[x1][y1]
               
               daca b[x2][y2] > b[x1][y1]+1 || b[x2][y2]==-1  , b[x2][y2] = b[x1][y1]+1 si adaug elementul in coada 2
     }
     daca coada 1 este vida
            daca coada 2 nu este vida
                   preia in coada 1 primul element din coada 2
}
Dar iau doar 40 de puncte pe el. Deci era mai bun celalalt.

Interesanta ideea, dar poti sa imi dai un exemplu pentru care algoritmul meu cade?

Am doua matrici de 1000 * 1000(b[][] o initializez cu -1) si o coada de 4000 de elemente. Fac o parcugere din (pl, pc)(pozitia de start din b[][] are valoarea 0 in loc de -1) in toate cele 4 directii. Prima conditie ca un element sa fie introdus in coada este ca sa fie in matrice. Apoi dupa ce trece de aceasta vin doua ramuri mari:

1.daca a[x2][y2] == a[x1][y1]
   daca b[x2][y2] > b[x1][y1] || b[x2][y2]  , b[x2][y2] = b[x1][y1] si adaug elementul in coada
2.daca a[x2][y2] != a[x1][y1]
   daca b[x2][y2] > b[x1][y1]+1 || b[x2][y2]==-1  , b[x2][y2] = b[x1][y1]+1 si adaug elementul in coada

Coada este circulara. Parcurgerea se opreste cand prim == ultim.
Nu inteleg unde e greseala.

Iau incorect pe ultimele 4 teste. Rezolvarea e cea cu coada circulara, in care adauga un element de fiecare data cand se indeplineste o conditie. totusi mi-e nu imi iese din timp, imi da incorect pe ultimele 4. Ajutati-ma!!!

Cu toate ca am rezolvat problema, pe parcurs am intampinat unele dificultati legate de memorie. Daca avem 640 KB, iar 1 INT = 4 bytes, atunci putem folosi (1024 x 640)/4 elemente de tip INT. Sau gresesc?

Ms fain. Acum am inteles si eu care e treaba. Daca exista costuri negative, atunci se poate intampla ca drumul de la un nod i la un nod j sa scada(prin adunare cu o valoare negativa), iar daca nodul j a fost selectat in trecut atunci drumurile care au trecut de la i prin j, nu vor fi actualizate cu noua valoare. Mda.. inca o data ms fain. 

Imi poate explica si mie cineva de ce Dijkstra nu merge pe costuri negative, va rog. Eu l-am implementat si am pus doua muchii negative si mi-a mers de minune. Deci cum e cu asta?

Se poate DFS si iterativ. Si ma chinui acum sa il implementez, dar nu am alte idei decat sa imi creez o stiva care sa o inlocuiasca pe cea din sistem pt functii. A facut careva interativ DFS?

DFS are aceeasi complexitate cu BFS: O(n+m).

daca el vrea sa faca binar,lasa-ti-le sa faca binar.
deci Vlad ti-am zis cautarea ta nu poate fi exacta. Deci tu ai vecotrul 2 3 5 7 11 13 17 19.... Iar daca ai a=2 b = 19. Cate numere prime ai? In cazul asta rezolvarea ta va tiparii 8. La a = 4 si b = 19 va tiparii 7, adik corect. Dar daca ai a=2 si b=18 programul tau va afisa 8, corect fiind 7. Iar pt a=4, b = 18 programul tau va afisa 6, corect fiind 5.

uite cautarea mea binara:

Cod:

 long bs(long x){  
      long s=1,d = h,m,i;  
      while(s+2<d){  
     m = (s+d)/2;  
     if(x == prime[m]) return m;  
   
     if(x>prime[m])s = m+1;  
     else d = m-1;  
      }  
      i=s;  
      while(x>prime[i] && i<=d)i++;  
      return i;  
}  

prime[] e vectorul tau s[]. Am lasat ca marginea inferioara sa fie mai mica cu 3 decat cea superiaora ca sa pot cauta secvential exact nr care ma intereseaza pentru ca imi sarea. Nu pot explica foarte exact pt ca am rezolvat-o anul trecut.

iar afisarea:

Cod:

  if(a == prime[i] && b != prime[j]){  
             fprintf(out,"%ld \n",j-i);  
           }  
   
   
           if(a != prime[i] && b == prime[j]){  
             fprintf(out,"%ld \n",j-i+1);  
           }  
   
           if(a == prime[i] && b == prime[j]){  
             fprintf(out,"%ld \n",j-i+1);  
           }  
   
           if(a != prime[i] && b != prime[j]){  
             fprintf(out,"%ld \n",j-i);  
           }  

sper ca te-am ajutat. Apropo pe testul initial de pe infoarena iti merge?

hm.. ceva nu e bine pe exemplul lu Bitis. Stiu ca solutia nu este unica. Dar costurile pt fiecare muchie din drum trebuie sa coincida la toti. Adik cum ai tu Bitis drumul 12->20, 20->15, 15->16, 16->8 corect ar fi sa afiseze in dreptul acestor muchii 1,1,2, respectiv 2. Si la tine parca afiseaza pt 12->20 indicele costului 2, iar pt 20->15 indicele costului 1. Sau nu conteaza asta?

frate... problema e la afisare. Pentru i-uri diferite, ai acelasi numar de numere prime. Acolo intervine omica problema la cautarea binara. Stiu ca mi-e nu imi dadea bine la unmoment dat nici pe exemplu pt b=19 sau b=20. La 19 cand se modfica(de la 18 se trece la 19 se mareste numarul de nr prime) nu iti returneaza ce vrei ca nu mai icnrementeaza, iar la 20 se va opri la 19. Ceva de genu era. bafta! daca nu iti iese. iti postez cautarea mea binara.

Mda... si eu avut aceeasi problema cu 2 parca. Dar Prindeam mai cazuri nasoale, pentru ca cautarea binara incrementa ceva in plus.
Oricum trebuie sa modifici afisarea, cum am facut si eu de altfel:

Cod:

         i=bs(a,1);  
         j=bs(b,2);  
  
         if(a == prime[i] && b != prime[j]){  
            fprintf(out,"%ld \n",j-i);  
          }  
  
  
           if(a != prime[i] && b == prime[j]){  
            fprintf(out,"%ld \n",j-i+1);  
          }  
   
          if(a == prime[i] && b == prime[j]){  
            fprintf(out,"%ld \n",j-i+1);  
          }  
  
          if(a != prime[i] && b != prime[j]){  
            fprintf(out,"%ld \n",j-i);  
          }

Oricum te prinzi tu care e faza din afisare ca esti cuprins de problema, eu am mai uitat sustele. Daca iti iese imi dai un ceai la scoala. 

Daca iti da WA pe testul 3 nu are cum sa fie de la limite. Cel mai sigur ca e la cautarea binara. Eu de exemplu nu am stiut sa fac cautarea binara foarte exacta, si dupa fiecare cautare verificam niste treburi. Dar zi cum ai facut tu.

O singura intrebare... prietenul i vien doar daca vine prietenul j. Asat inseamna ca in cazul in care avem, ca si in exemplu de altfel, relatie intre 1->2 si 1->3, preitenul 1 vine daca vine atat prietneul 2, cat si prietenul 3, nu? Sau e suficient sa vina preitenul 2 sau 3.

Cum se rezolva?

ba care mi-ati dat minus la karma? si apropo... rezultatele?

iar s-a -- bip -- evaluatorul? De ce tine asa mult?

alaxandru tu faci brut force. Problema presupun ca se rezolva intr-o complexitate mai mica decat O(n^2).  Tu ai acolo O(n^2). Ma gandesc ca iei TLE.

George pe tine Algoritmiada te duce cu gandul la cruciade. Pe mine personal ma duce cu gandul la o gramada de algoritmi trantiti pe niste tarabe in piata, imagine care ar putea fi descrisa prin "nebunie", ceva haotic, agitatie, graba. Poate daca avea numele de Algoritmics sau Algorimpics sau Algoritmolimpics sau ceva de genu ma ducea cu gandul la olimpiadele grecesti, si aici ar fi mers treaba cu, coiful (si ca nu se prea purta coif la olimpiade, dar putem exagera).

Ideea care vreau sa o expun e ca fiecare face un logo dupa cum doreste, degeaba ne spui cum vezi tu concursul, pentru ca restul mai mult ca sigur nu il vedea ca tine, iar spunand ca vrei sa contina coiful e putin mai subtil decat "Faceti cum vreau eu sa iasa, ca altfel voi face eu unul personal, cu, coif."

Bafta la sigle! Pana acum o votez pe a lui Vlad.

P.S. Scuze oliviu, chiar daca imi esti vecin la o banca distanta, ii place mai mult aia. Ironic ca si tie. )
 

Propun ca fiecare problema sa fie evaluata dupa gradul de dificultate cu un numar de stele sau orice altceva precum sunt evaluate si in unele culegeri.
Astfel, cel care doreste sa rezolve o problema(cel incepator, precum sunt si eu), sa stie unde se baga la creatii.

Ms mult. Am rezolvat-o si eu. Numai ca am facut-o in O(2^m * n). Oricum e acelasi lucru, dar mi s-a parut mai bine sa merg pe coloane, cu permutarile. 

Am revenit la aceasta problema, pentru ca cica se apropie perioada tezelor si tre sa invatz ceva backtrack(glumesc). Am rezolvat-o cu back.
Dar din pacate i-au doar 40 pct pt ca imi iese din timp. Ma gandesc ca greseala e la calcularea sumei.

Algoritmul de back e varianta aia cu stiva de m+n in care generez toate aranjamentele cu repetitie dintre -1, 1. Deci inainte de a ceda tentatiei si a ma uita in sursa, dati-mi si mie o mana de ajutor cu calcularea sumei.