807 Marmelada

[•wefgef]

Aici puteti discuta despre problema Marmelada.

[•gabor_oliviu1991]

am facut in felul urmator:

am retinut graful prin liste de adiacenta. am facut un lee pt graf pt a determina drumul minim intre x si y. dupa care miam determinat nodurile prin care trece  " drumul preferat ". am sortat valorile costurilor drumurilor, apoi intre x si y am pus primele k valori din vectorul de costuri, iar dupa am pus restul valorilor.

Cod:

           
           lee();
           	k=1;
	drum[k++]=x;

	for(i=x+1;i<=y;i++)
		if(sol[i]==k-1)
			drum[k++]=i;
           
           sort(c+1,c+n+1);
	for(i=1;i<k-1;i++)
		{
		cost[drum[i]]=c[i];
		c[i]=0;
		}
	for(i=1;i<=n;i++)
		if(c[i]!=0)
			{
			for(j=1;j<=n;j++)
				if(j!=i&&cost[j]==0)
					break;
			cost[j]=c[i];
			c[i]=0;
			}
	for(i=1;i<=n;i++)
		g<<cost[i]<<"\n";

in vectorul c[] am retinut costurile drumurilor propuse de firma, in vectorul drum[] mi-am pus nodurile prin care trece individul pentru a ajunge din S in D (desigur drumul minim), iar in cost[] am construit solutia. ce gresesc? multumesc anticipat

[•gabitzish1]

E ok ideea, dar mi se pare cam aiurea ce ai implementat tu acolo.

Cod:

drum[k++]=x;

	for(i=x+1;i<=y;i++)
		if(sol[i]==k-1)
			drum[k++]=i;

Drumul tau incepe cu nodul x, se termina cu y iar intre ele sunt noduri K (x < K < y). Cum functioneaza daca drumul minim de la 3 la 4 trece prin nodurile 1 2 5 6 7 ?

... nici ce e mai jos nu sunt sigur ca e bine.

[•Mishu91]

Cod:

cost[drum[i]]=c[i];

Am impresia ca tu afisezi practic costurile, iar in enunt iti cere indicele costului respectiv

[•gabor_oliviu1991]

m-a cam bagat in ceata problema asta... bun, dupa ce am facut "lee"-ul (ca, cica nu ii zice asa ), cum as putea sa determin drumul min de la x la y?... in sol[] am facut lee-ul. pt exemplul de la prob, dupa executia lee(); vectorul sol[] imi arata: 0 1 1 2  ... adik pornesc din x (care e egal cu 0), si merg pana la y. pot trece prin nodurile 2 sau 3 deoarece sol[2] si sol[3] sunt egale cu nodul actual (nodul x) + 1. dupa care urmatorul nod este 4, aflat la distanta 2 fata de nodul x. deci drumurile mele pot fi 1 2 4 sau 1 3 4. as putea retine muchiile intr-o structura si dupa sa iau fiecare pereche din drum[], adik muchiile (1,2) si (2,4), pentru primul drum (1->2-> 4) si sa atribui unui camp al structrii primele K costuri, K fiind numarul de muchii care leaga X de Y?

Sincer, nici ce trebuie afisat nu prea am inteles. Eu pe linia i afisam costul de la i la i+1 (pt i=n afisa costul de la nodul n la nodul 1)...cam nelamurit totusi

[•stocarul]

totusi....eu nu cred k e nevoie de lee (oricine ar fi) .....ci de o simpla parcurgere in latime din unul din cele doua noduri care marginesc drumul favorit.

[•gabor_oliviu1991]

totusi, determinarea drumului minim intre X si Y l-am facut ok?

[•zbarni]

Pai poti sa faci parcurgerea in latime cu lee (ii cam acelasi lucru). Determinarea drumului minim l-ai facut bine, pe pozitia i din sol[] pui nodul din care ai ajuns in i, adica din nodul sol ai ajuns pe parcursul parcurgerii in nodul i. Eu am numerotat muchiile, si am adaugat in sol[] numarul muchiei prin care am ajuns din sol in i. Ai grija sa numerotezi costurile inainte sa le sortezi, pentru ca cere numarul de ordine (indicele) al costului atribuit fiecarei muchii, si nu costul acesteia. Sper sa te ajute 

Totusi, primesc Killed by signal la testul 3, si nu-mi dau seama de ce. Am alocat dinamic vectorii... nu cred ca e ceva de la test, pt ca am vazut ca in timpul concursului au fost si altii cu eroarea asta, insa la alte teste.

[•sima_cotizo]

"Lee" si BFS sunt acelasi lucru.

In fisierul de iesire trebuie ca nodurile de pe drumul minim sa aiba lungimile in ordine crescatoare, sau asociem pur si simplu primele k lungimi celor de pe drumul minim si apoi in rest ce ramane?

[•gabitzish1]

"Lee" si BFS sunt acelasi lucru.

In fisierul de iesire trebuie ca nodurile de pe drumul minim sa aiba lungimile in ordine crescatoare, sau asociem pur si simplu primele k lungimi celor de pe drumul minim si apoi in rest ce ramane?

Primarul are doua orase preferate, S si D si doreste ca dupa construirea soselelor sa existe cel mai scurt drum posibil intre cele doua orase.
Daca exista mai multe solutii se poate afisa oricare dintre ele.

[•zbarni]

E mai 'sanatos'sa afisezi in ordine crescatoare, insa nu ar trebuie sa conteze.

[•free2infiltrate]

Am citit in solutile oficiale si se pare ca cea ce am aplicat eu e ok, totusi imi spune ca e gresit  . Va puteti uita si peste sursa mea va rog:

http://infoarena.ro/job_detail/260553?action=view-source

[•gabitzish1]

Pentru problema asta nu sunt vizibile sursele. Nu ne putem uita peste a ta.

[•free2infiltrate]

Cod:

...

Scuze de neatentie 

[edit] Ai primit un raspuns la rugamintea ta - poti incerca daca mai ai nevoie sa trimiti mesaj personal utilizatorilor.

[•Florian]

Cod:

for (i=1;i<=m;i++)
{
if (use[X[i]] && use[Y[i]] && X[i]!=Y[i]) printf("%d\n",C[lw++]);
else if (S==D) printf("%d\n",C[lw++]);
     else printf("%d\n",C[up--]);
}

Citeste cu atentie enuntul si incearca sa intelegi ceea ce trebuie afisat. Tu afisezi valorile costurilor respective, dar trebuie afisate indicele lor in vectorul initial ( in ordinea data in fisierul de intrare). S-ar putea sa fie si de la algoritm, insa nu stiu. Asta e ceea ce am observat din prima.

[•sima_cotizo]

E mai 'sanatos'sa afisezi in ordine crescatoare, insa nu ar trebuie sa conteze.

Ideea era ca dupa ce am lucrat cu un map de STL (1 TLE), am incercat si alta metoda care nu imi pune numerele in ordine crescatoare pe drumul minim si iau 3 WA... Si ma indoiesc ca as fi gresit ceva in sursa.

[•free2infiltrate]

Citeste cu atentie enuntul si incearca sa intelegi ceea ce trebuie afisat. Tu afisezi valorile costurilor respective, dar trebuie afisate indicele lor in vectorul initial ( in ordinea data in fisierul de intrare). S-ar putea sa fie si de la algoritm, insa nu stiu. Asta e ceea ce am observat din prima.

Intradevar de la asta era, am facut putine modificari si iata ca a mers  . Multumesc mult 

[•gabor_oliviu1991]

am refacut cu o structura in care retin indicii costurilor pt sosele dar tot nu merge. am facut eu un test pe care imi da bine. ati putea sa-mi dati un test mai mare. 10x

[•gabitzish1]

Uite un test mai mare daca crezi ca te ajuta :

Cod:

20 30 12 18
1 3
1 11
1 13
2 13
3 4
4 6
5 6
5 14
5 20
6 13
6 8
6 9
7 9
8 16
9 16
9 17
9 18
10 20
10 14
12 20
13 19
14 15
15 16
16 18
2 4
2 2
6 4
15 20
18 19
14 14
2 3 54 21 43 76 3 2 6 12 439 1 34 54 12 2 3 54 21 43 76 3 2 6 12 439 1 34 54 12

mie mi'a dat

Cod:

16
23
2
7
17
22
9
24
10
15
25
30
4
19
13
28
5
20
3
8
14
18
27
12
29
6
21
1
11
26

dar nu e solutie unica.

[•gabor_oliviu1991]

prima problema de care ma lovesc ii ca de exemplu eu am drum de la 2 la 2. ce pun in lista de adiacenta ?

[•Florian]

prima problema de care ma lovesc ii ca de exemplu eu am drum de la 2 la 2. ce pun in lista de adiacenta ?

Treci 2 in lista de adiacenta a lui 2. Cu siguranta nu o sa fie luata in calcul muchia (2->2) pt drumul minim dintre S si D, deoarece nu ar ma fi solutie optima. Deci muchia 2->2 nu are cu ce sa te dezavantajeze.

[•astronomy]

Mai bine decat atat, nu pui deloc 2 in lista de adiacenta a lui 2  O muchie de la un x la x nu o sa fie niciodata intr-o solutie optima, deci poti sa nu le iei in considerare.

[•razyelx]

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?

[•gabitzish1]

Nu, Brestin... nu conteaza.. Conteaza ca drumul de la 12 la 18 sa fie cel mai scurt..nu trebuie ca indicii muchiilor sau costurile sa fie in ordine crescatoare pe drum.

[•ctlin04]

Se poate uita cineva pe sursa mea?
Primesc Killed by signal 11(SIGSEGV) pe 2 teste si chiar nustiu de unde poate sa fie, adica din observatiile mele as tine sa cred ca pentru acele teste nu exista nici un drum de la S la D, dar evident nu poate fi de la asta in timp ce alte surse iau 100, dar nici parcurgerea in latime nu prea cred sa fie gresita