807 Marmelada

[•stardust]

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.

[•ctlin04]

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 

[•lucian666]

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!!!!

[•ctlin04]

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 

[•visanr]

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   e o idee de optimizare, doar ca in cazul lui nu asta ii incetineste cel mai mult programul  

[•ctlin04]

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 

[•costi_.-.]

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    ?

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

[•lucian666]

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

Multumesc!!!

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

[•BLz0r]

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')