infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Mircea Pasoi din Februarie 19, 2006, 23:45:53


Titlul: 180 Drumuri minime
Scris de: Mircea Pasoi din Februarie 19, 2006, 23:45:53
Aici puteţi discuta despre problema Drumuri minime (http://infoarena.ro/problema/dmin).

Titlul: 180 Drumuri minime
Scris de: u-92 din Februarie 20, 2006, 00:00:36
imi poate recomanda cineva ce functie sa folosesc pt a calcula logaritmul?
in concurs am testat diferite variante si era foarte dubios.. folosind "log" cu tipul double iau 0.. insa daca schimb in "log10" si tipul in long double iau 80, cu "logl" si tipul long double iau 5
 :idea:

Titlul: 180 Drumuri minime
Scris de: Mircea Pasoi din Februarie 20, 2006, 00:06:38
Mie mi-a mers ok cu log() si double.

Titlul: 180 Drumuri minime
Scris de: u-92 din Februarie 20, 2006, 00:20:29
am descoperit greseala  ](*,)  ](*,)  ](*,)
eu comparam pur si simplu.. acum am bagat un eps = 1e-10 si merge de 100

Titlul: 180 Drumuri minime
Scris de: Silviu-Ionut Ganceanu din Februarie 20, 2006, 02:59:49
Asa se invata cel mai bine: gresind in concursuri! ;)

Silviu

Titlul: 180 Drumuri minime
Scris de: Paul-Dan Baltescu din Februarie 20, 2006, 15:27:27
Iau 85 de puncte  ](*,)  (pic testele 16,19,20 cu WA)... Ce e asa de special la testele astea? Are cineva vreo idee unde gresesc? 8-[

Titlul: 180 Drumuri minime
Scris de: Gogu Marian din Februarie 20, 2006, 15:48:19
Incearca sa folosesti o precizie mai mare cand compari egalitatea dintre 2 numere reale. Ar trebui sa mearga cu 1e-8 de exemplu.

Titlul: 180 Drumuri minime
Scris de: Paul-Dan Baltescu din Februarie 20, 2006, 18:35:56
Da, asta era, multumesc.  :)

Titlul: 180 Drumuri minime
Scris de: Iacob Ioan Fanica din Februarie 21, 2006, 22:48:28
Imi spune si mie cineva daca e corect cum calculez nr de drumuri de cost minim?
Eu calculez cu djickstra drumul minim de la 1 la un nod iar daca il gasesc initializez nr de drumuri minime pt. drumul respectiv cu nr. de drumuri de cost minim de la nodul anterior de la care am cautat costul minim.
Daca e egal adun numarul de drumuri prin nodul prin care e egal.
Si iau 5 puncte fara logaritm iar cu 0.
Ma ajuta si pe mine cineva.
Va rog.Multumesc!
Sau daca nu sa imi dea cineva un test mai mare si raspunsul corect sa verific.(nu unul oficial, ca oricum nu se dau :D )
Am reusit sa iau 15 puncte dar nu stiu cum sa fac aproximarea aia cu 10e-10 sau -8.Ce intoarce aia si cum o folosesc?

Titlul: 180 Drumuri minime
Scris de: u-92 din Februarie 22, 2006, 11:44:49
cand lucrezi cu numerele reale apar erori de precizie (de exemplu sqrt(2) nu va intoarce toate zecimalele lui radical din 2).. de aceea (in cazul problemei dmin) iti iei o marja de eroare
Cod:
eps = 0.0000000001 (echivalent cu 1e-10)

acum, daca ai doua numere reale a si b, cand vrei sa testezi daca sunt egale
vei folosi
Cod:
if( abs(a-b) <= eps )
( modulul diferentei lor sa fie mai mic sau egal decat marja de eroare )

ps: sunt probleme in care se cere rezultatul cu o marja de eroare de 0.001 (de exemplu), acolo vei putea alege epsilon = 0.001. (deci 1.445690994 il vei considera egal cu 1.4458906956)

Titlul: 180 Drumuri minime
Scris de: Marius Stroe din Februarie 22, 2006, 12:15:54
Si eu am folosit algoritmul lui The_Godfather mai putin problema aproximarilor si am luat 10 puncte...  =D>

Cred ca gresesc la update-ul numarului de drumuri minime... Ce va da pentru
Cod:
5 7
1 2 1
2 3 1
3 4 1
2 4 1
1 4 1
1 5 1
4 5 1

Poate asa imi dau seama unde gresesc (inclusiv pe hartie)  :P !

Titlul: 180 Drumuri minime
Scris de: Sara Nicolae Bogdan din Februarie 22, 2006, 12:27:49
1 3 2 3

Titlul: 180 Drumuri minime
Scris de: u-92 din Februarie 22, 2006, 13:36:56
Citat
costul energetic al unei legaturi este un numar intreg din intervalul [2, 10^9]

Titlul: 180 Drumuri minime
Scris de: Filip Cristian Buruiana din Februarie 22, 2006, 16:03:07
Citat
Imi spune si mie cineva daca e corect cum calculez nr de drumuri de cost minim?
Eu calculez cu djickstra drumul minim de la 1 la un nod iar daca il gasesc initializez nr de drumuri minime pt. drumul respectiv cu nr. de drumuri de cost minim de la nodul anterior de la care am cautat costul minim.
Daca e egal adun numarul de drumuri prin nodul prin care e egal.
Si iau 5 puncte fara logaritm iar cu 0.
Ma ajuta si pe mine cineva.
Va rog.Multumesc!


In momentul cand afli in djikstra nodul alb (dupa explicatia din Cormen) care are distanta pana la 1 minima, atunci faci numararea: aduni toate numerele de forma P
  • , unde x e un nod a. i. sa existe muchia x - NOD_CURENT_OPTIM, si d
  • + COST_MUCHIE_CURENTA = d[NOD_CURENT_OPTIM]... asa mi se pare cel mai logic si merge usor fara sa iti bati capul pe greseli ( nu faci numararea in timpul relaxarii muchiilor care pornesc din NOD_CURENT_OPTIM, o faci inainte... )

Titlul: 180 Drumuri minime
Scris de: Iacob Ioan Fanica din Februarie 22, 2006, 17:55:02
Multumesc tuturor pentru ajutor!Acu merge si le egaleaza.
Acu iau 10 puncte am sa vad de ce.
Cat da pentru testul asta?
Cod:

50 69 
22 33 1347 
11 43 1710 
5 21 354 
1 11 559 
27 45 1157 
9 29 66 
38 15 1480 
1 23 774 
49 5 1836 
37 36 1179 
39 30 397 
12 49 548 
28 20 815 
10 21 83 
7 48 719 
17 11 1019 
47 27 1803 
32 16 170 
42 6 901 
45 5 205 
47 29 691 
2 25 1317 
39 7 159 
20 9 558 
8 42 1194 
40 13 854 
46 16 1022 
18 48 793 
48 6 1428 
18 28 33 
18 11 1190 
27 36 98 
2 8 1241 
47 5 158 
34 41 193 
21 13 588 
29 12 1195 
44 34 1642 
14 34 1813 
28 17 1659 
21 46 681 
34 39 1554 
7 49 1336 
21 40 396 
34 48 1621 
22 39 1683 
5 6 866 
24 43 3 
37 34 1698 
25 35 955 
43 12 99 
28 45 1493 
2 1 193 
7 48 611 
48 45 567 
3 49 759 
14 42 958 
17 20 224 
42 40 871 
4 9 565 
35 17 86 
43 40 984 
40 10 1553 
48 23 503 
48 38 1276 
9 35 498 
13 36 1897 
31 44 1072 
47 1 1051

Mie imi da:
1 3 1 1 2 1 1 1 1 1 2 1 2 1 1 1 1 0 1 1 1 1 1 1 0 1 2 1 1 1 1 1 1 1 1 2 1 1 3 1 2 1 1 1 1 1 1 3 0

Titlul: 180 Drumuri minime
Scris de: Iacob Ioan Fanica din Februarie 22, 2006, 18:37:47
In momentul cand afli in djikstra nodul alb (dupa explicatia din Cormen) care are distanta pana la 1 minima, atunci faci numararea: aduni toate numerele de forma P
  • , unde x e un nod a. i. sa existe muchia x - NOD_CURENT_OPTIM, si d
  • + COST_MUCHIE_CURENTA = d[NOD_CURENT_OPTIM]... asa mi se pare cel mai logic si merge usor fara sa iti bati capul pe greseli ( nu faci numararea in timpul relaxarii muchiilor care pornesc din NOD_CURENT_OPTIM, o faci inainte... )[/quote]

    Cum o fac inainte. Ca trebuie sa calculez mai intai costul minim pentru nodul respectiv si apoi adun toate drumurile de la nodul anterior x daca is egale si daca nu initializez cu drumurile pt nodul respectiv.
    ceva de forma:
Cod:

for(j=2;j<=n;j++)
  if(s[j]==0)
  if(abs(d[j]-(d[poz]+a[poz][j]))>eps&&a[poz][j]!=0&&j!=poz)
  {
   p[j]=p[poz];
   d[j]=d[poz]+a[poz][j];
  }else
  if(abs(d[j]-(d[poz]+a[poz][j]))<=eps&&a[poz][j]!=0&&j!=poz)
    p[j]+=p[poz];
unde poz este nodul 1-poz-poz-j.

Titlul: 180 Drumuri minime
Scris de: Filip Cristian Buruiana din Februarie 22, 2006, 19:17:02
Mie imi da
Cod:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0

Si cred ca e si bine, din moment ce am luat 100 :?

Mai, dupa ce afli nodul ala, te gandesti care pot fi predecesorii lui in arborele de drumuri minime ( asta inseamna conditiile alea doua ) si aduni valorile corespunzatoare pt. predecesori.

Titlul: 180 Drumuri minime
Scris de: Marius Stroe din Februarie 22, 2006, 20:38:40
Eu unul am determinat distanta minima de la nodul 1 la fiecare dintre celelalte noduri...
Pentru a numara cate drumuri de lungime minima sunt pana la un nod p am facut asa:

Cod:

pentru "fiecare nod q adiacent lui p" executa
     daca "nu se stie cate drumuri sunt pana la q" atunci
          "calculeaza pentru nodul q"
     "actualizez datele nodului p"


Mi-am exprimat din nou parerea, deoarece am incercat si ca filipb si ca The_Godfather si ca mine :D si iau aceleasi 70 de puncte. Precizia e 1e-10... In plus a inceput sa imi placa Dijkstra  :roll: .

Titlul: Raspuns: 180 Drumuri minime
Scris de: Tabara Mihai din Octombrie 01, 2006, 13:56:22
Imi explica si mie de ce cu if() - ul asta merge de 100
Cod:
if ( d[j->vf] - (d[k] + dis ) > eps  )
{
           d[j->vf] = d[k] + dis;
           nr[j->vf] = nr[k]%104659;
}

si cu if-ul asta ia 0 puncte
Cod:
if ( d[j->vf]  > d[k] + dis  )
{
           d[j->vf] = d[k] + dis;
           nr[j->vf] = nr[k]%104659;
}

De ce e asa mare diferenta intre "if ( d[j->vf] - (d[k] + dis ) > eps  )" si "if ( d[j->vf]  > d[k] + dis  )".
Precizez ca am folosit eps = 1e-10.

 :oops: :oops:

Titlul: Raspuns: 180 Drumuri minime
Scris de: Paul-Dan Baltescu din Octombrie 01, 2006, 14:49:38
Pai e evident. La primul if nu folosesti eps ca sa eviti erorile de precizie.

Titlul: Raspuns: 180 Drumuri minime
Scris de: Ivan Nicolae din Ianuarie 05, 2007, 16:57:09
Am definit astea:
Cod:
#define NMAX 1501
#define MMAX 2501
#define INFY 0x3f3f3f3f
#define ALAS 104659
#define eps 1e-10

Apoi in interiorul lui Dijkstra, dupa ce am descoperit nodul in care s-a ajuns cu cost minim.... adica , cand ma duc pe vecinii nodului in care s-a ajuns cu costu' minim.
Cod:
     for (i=1;i<=n;i++)
        if (A[NOD_MAX][i])
          {
           if ((C[NOD_MAX] * A[NOD_MAX][i] / C[i]) < eps)
             {
              C[i] =C[NOD_MAX] * A[NOD_MAX][i];
              D[i] = D[NOD_MAX] % ALAS;
             }
             else
           if (C[NOD_MAX] * A[NOD_MAX][i] == C[i] )
             {
              D[i]+=D[NOD_MAX];
              D[i]=D[i] % ALAS;
             }
          }

Asa iau 10 puncte, daca scot eps-ul si fac fara iau 5 puncte.
Nu vad ce alte erori de precizie pot aparea dupa ce includ si eps-ul in program.

Titlul: Raspuns: 180 Drumuri minime
Scris de: Airinei Adrian din Ianuarie 06, 2007, 18:50:28
mi-a sarit in ochi al doilea if cand verifici egalitatea.. nu mai iei in considerare eps

p.s: scapa si de modulo, consuma foarte mult timp de executie

Titlul: Răspuns: 180 Drumuri minime
Scris de: Andrei Homorodean din Iunie 23, 2007, 20:16:43
Pe testul pus de Marius mie imi da un raspuns diferit de cel al lui sarabogdan si anume 1 1 3 4. Cine are dreptate?(cu sursa de 100)

Titlul: Răspuns: 180 Drumuri minime
Scris de: Bondane Cosmin din Iunie 23, 2007, 20:22:01
Si mie imi da 1 1 3 4...tot cu sursa de 100 pcte.

Titlul: Răspuns: 180 Drumuri minime
Scris de: Ionescu Vlad din Iulie 07, 2007, 22:16:20
Mie imi da 5 4 3 4 cu sursa de 100... care-i raspunsul pana la urma?

1 1 3 4 eu zic ca sigur nu-i corect. De la nodul 1 pana la 2 sunt clar mai multe drumuri ( 1 - 2, 1 - 4 - 2, 1 - 5 - 4 - 2, 1 - 5 - 4 - 3 - 2, 1 - 4 - 3 - 2, daca am facut bine )

Nici mie nu imi da bine pentru celelalte noduri.. oricum nu cred ca are importanta, ca se precizeaza ca nu poate exista un cost mai mic ca 2.

Titlul: Răspuns: 180 Drumuri minime
Scris de: Mihai Leonte din August 09, 2007, 10:41:41
Pai in primul rand, testul lui Marius nu e bun  :P. (ala, primul... cu muchiile de cost 1). De ce? Pentru ca orice drum intre 1 si X e minim (orice produs e 1, sau altfel spus, orice suma de logaritmi e 0).
De altfel spune si in enunt, ca dimensiunile sunt intre 2 si 10^9.

Raspunsul ar fi
5 6 4 4                        - daca drumurile sunt elementare
infinit infinit infinit infinit - daca drumurile nu sunt elementare

Nu scrie nicaieri daca drumurile sunt sau nu elementare, pentru ca reiese din conditia de drum minim (din nou, daca costul fiecarei muchii >1)

Cat despre precizie... sa ma dau cu capul de pereti, nu alta  ](*,)  :roll:

Titlul: Răspuns: 180 Drumuri minime
Scris de: Andrei Misarca din Ianuarie 09, 2010, 17:11:29
Testele nu cred că sunt foarte puternice, pentru că iau 100 cu Belman-Ford, care teoretic nu ar trebui să ia maxim, pentru că nu generează întotdeauna soluția corectă.

Titlul: Răspuns: 180 Drumuri minime
Scris de: Farcasanu Alexandru Ciprian din Ianuarie 30, 2010, 12:22:21
@ Mishu91
Ce vrei sa spui prin faptul ca Bellman ford nu genereaza intotdeauna solutia corecta?

Titlul: Răspuns: 180 Drumuri minime
Scris de: Andrei Misarca din Ianuarie 30, 2010, 13:45:28
Uite pe exemplul următor (lungimile sunt deja logaritmate, să zicem).
Cod:
4  5
1 3 3
1 2 2
2 3 1
2 4 2
3 4 1
Tu când faci Bellman-Ford ai în coadă 1, mergi la 3 și 2. Apoi din 3 mergi în 4 cu costu 4 (deci un drum de cost 4). Din 2 mergi în 4 și în 3, deci o să ai 2 drumuri de cost 4 în 4, dar pe 3 îl updatezi, dar nu îl mai bagi în coadă (cel puțin eu așa am făcut), prin urmare pierd un drum de lungime 4 între 1 și 5(1-2-3-5)

Titlul: Răspuns: 180 Drumuri minime
Scris de: Farcasanu Alexandru Ciprian din Ianuarie 30, 2010, 18:42:56
Pai atunci baga-l iar in coada dar ai grija ca sa nu aduni de mai multe ori acelasi drum.
Dupa ce relaxezi vecinii unui nod, NR[nod] = 0 (avand grija sa pastrezi in alt vector valoare NR[nod])

Titlul: Răspuns: 180 Drumuri minime
Scris de: Andrei Misarca din Ianuarie 31, 2010, 09:25:09
Ai dreptate, pare a merge așa, dar testele tot slabe sunt. :)


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