infoarena

Aici puteti discuta despre problema Marmelada (http://infoarena.ro/problema/marmelada).

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.


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

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

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.

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

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 :'(

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.

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

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. ](*,)

"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?

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

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

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

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

Scuze de neatentie  :aha:

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

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.

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.

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

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

Uite un test mai mare daca crezi ca te ajuta :
mie mi'a dat
dar nu e solutie unica.

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.

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.

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?

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.

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  ](*,)

Nu am rezolvat problema. Dar vezi ca poti sa iei kbs si daca spargi stiva. Am inteles ca faci un DFS. Daca e recursiv asta ar putea sa fie. Incearca sa il implementezi iterativ.

Nu fac dfs, fac bfs cu coada si respectiv nu am nimic cu stiva, problema e ca la mine se termina elementele din coada inainte de a ajunge la nodul final si respectiv da eroare aceasta ar insemna ca nu exista nici un drum intre orasele preferate de primar, alta idee referitor la situatia asta nu am  :?

Salut.Am luat la problema asta 50 pct cu 3 TLE si 2 WA ](*,)
Procedez astfel:
Fac un BFS din S pt a vedea distanta pana la D
Muchiile din drumul de la S la D le salvez intr-un vector.
Copiez vectorul cu costuri in altul si apoi il sortez .
Pt muchiile drum[i ] ,drum[i+1] cu i<lg traseu le dau costurile corespunzatoare si apoi pt celelalte muchii din fisier dau costurile care au ramas :)
Mi se pare corecta idee si nu stiu de ce iau WA si TLE....
Exista ceva mai optim?
Multumesc Anticipat!!!! :D

Ideea este buna si complexitatea la fel, sortarea este nlogn iar BFS se poate face in O( N ), deoarece poti trece doar o singura data peste un nod, doar ca nu ai implimentat bine, bfs poti sa-l faci pina cind nu ai ajuns in nodul destinatie dar nu pina cind nu mai ai noduri in coada, apoi nu ti se pare ca urmatoarea segventa de program:
Cod:
 for(int i=1;i<mm;i++){
         int poz=-1,costt=cost2[j];
           for(int k=1;k<=m;k++)
             if(cost[k] == costt && !uz[k] ){
                                              poz=k;
                                                uz[k]=1;
                                                  break;
                                                }
           if( poz>=1 && poz<=m  )
       save[++nn]=poz;
}
i-a cam mult timp, daca am inteles corect la tine mm este lungimea drumului minim de la sursa la destinatie care poate fi maxim n-1,
apoi daca costurile pe care tu le cauti se afla aproape de m complexitatea acestei segvente se apropie de n^2, de aceea si ai TLE.
Incearca sa implimentezi ideea de mai sus eficient si sigur o sa ai un timp mult mai mic decit limita.
Vezi ca drumul poti sa-l afli in O ( N ) daca pentru fiecare nod memorezi nodul din care ai venit si numarul la muchia pe care ai venit in nodul respectiv, apoi repartizezi celalalte costuri parcurgind o singura data toate muchiile si complexitatea finala va fi de aproximativ nlogn+n  :ok:

Pierzi mult timp cand atribui muchiilor costuri. Poti sa tii toate muchiile intr-o structura A (cu start, end si indicele initial al costului atribuit muchiei, initial -1). Fiecare muchie care face din drumul de la S la D o cauti in A si ii atribui indicele celui mai mic cost nefolosit (indicele costului in vectorul initial, nu cel de dupa sortare), apoi fiecare muchii ramase (cu A[i ].pos = -1) ii atribui la fel ca mai sus, indicele celui mai mic cost nefolosit.


@catalin: eu am facut BFS pana cand nu mai am noduri in coada si a intrat bine in timp  :wink: e o idee de optimizare, doar ca in cazul lui nu asta ii incetineste cel mai mult programul  :D

Deacord, dar oricum uneori din cauza ca nu faci niste optimizari mici, poti pierde 10, 20 de puncte, iar asta la concursuri deseori te poate clasa primul de sub bara de trecere la etapa urmatoare, ceea ce nu este placut deloc, deaceaa mereu incerc sa fac tot ce e posibil chiar daca nu-mi vine ideea de 100, citeva puncte in plus niciodata nu strica  :)

Salut . Ma poate ajuta cineva?
Am trimis doua surse pentru problema. Prima afisa ca solutie 3 4 2 1 , iar a doua modificata putin afiseaza 3 4 1 2 . Amandoua sunt solutii bune,  de ce nu iau nici un test la borderou  :sad:  ?

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

 :) Salut.In cazul in care avem muchie de la un nod la el insusi (2-2) de exemplu ,ce trebuie afisat in acest caz ? :-k .Eu iau 70 pct cu 2 incorrect si 1 TLE,si cred ca incorectul se datoreaza acestei nelamuriri  :oops: .

Multumesc!!!

Later Edit : Am rezolvat-o pana la urma de 100 pct ,pentru a intra si ultimul test a trebuit sa parsez citirea  :) .

care e faza cu testul 1 (iau KBS11, desi nu folosesc pic de recursivitate xD) iar pe testul 10 iau TLE (Dar acolo e treaba mea sa vad cum mai optimizez)


L.E: am rezolvat cu TLE-ul, acum iau WA pe testul 1, aceasi intrebare: care e faza cu acest test? :)

last edit: am luat 100p.. daca ajuta pe cineva, primul test nu se termina (pentru nu stiu ce motiv) cu caracterul newline ('\n')