1003 Transport2

[•stef2n]

Aici puteți discuta despre problema Transport2.

[•O_Neal]

de ce e limita de timp mai mica decat la moisil? 0.5 si nu 0.6 ? 

[•danimihalca]

Poate ca zic gresit, dar aici se testeaza pe un server de Linux si merge mai repede (cred ).

[•O_Neal]

a! se poate.. da oricum un dijkstra modificat implementat pe set ia 80...    oh well  lasa ca is mai simple celelalte variante nush de ce ma incapatanez eu 

[•Mishu91]

a! se poate.. da oricum un dijkstra modificat implementat pe set ia 80...    oh well  lasa ca is mai simple celelalte variante nush de ce ma incapatanez eu 

Având în vedere că trebuie să extragi minimul la fiecare pas, de ce folosești set (un arbore binar echilibrat), când poți folosi un priority_queue (care este implementat pe un heap)? Constanta operațiilor pentru set este mult mai mare decât pentru un heap, de aici vine ineficiența.

[•O_Neal]

ok mersi, o sa incerc si asa, acuma faceam o binara si ceva mi se pare ca nu e in regula ...
si anume.. am rulat testele la mine pe aceeasi timp ( am rulat si sursa mea si una din sursele oficiale ) ambele iau 100..
daca trimit sursele aici iau pe sursa mea 50 si pe cea oficiala ( data ca si solutie , aia cu binara ) doar 40 ..
eu pe sursa mea iau TLE aici pe infoarena pe unele teste, cea oficiala Killed by Signal ...
as fi recunoscator daca m-ar lamuri cineva, multumesc anticipat

later edit: sursa mea era gresita, never mind ! ) cat despre cea oficiala nush zau
second later edit: merge si dijkstra pe set-uri ( ia 100 ) daca nu memorezi muchiile alea asa cum numa eu am reusit  dar tot o sa incerc cum ai zis tu mai sus, mersi de idee, ca tot e mai eficient asa cred..

[•xtreme]

Am fakut 3 surse care doar citesc( datele de intrare ) si scriu( rezultat 0), una cu functii din C si alta  cu streamuri, ambele iau TLE pe testul 9, iar citirea cu parsare imi da TLE pe testul 8 si 9.

http://infoarena.ro/job_detail/475782?action=view-source
http://infoarena.ro/job_detail/475784?action=view-source
http://infoarena.ro/job_detail/475797?action=view-source

 

[•SpiderMan]

Nu pot vedea programul, imi poti da primul de acolo ? Merci .

[•xtreme]

Nu pot vedea programujkl, imi poti da primul de acolo ? Merci .

Imi lua mult timp cand faceam functia push_back de la vector din STL, am alocat dinamic cu pointeri (c++ clasic) si a mers ok citirea si scrierea in timp.

[•vendetta]

Nu inteleg de ce iau doar 10 pct;
am facut algoritmul lui kruskal doar ca acum sortez muchiile in functie de cost in ordine descrescatoare si apoi iau muchia cu cel mai mic cost din arbore partial...

[•klamathix]

Pai nu e corect sa iei muchia minima din apm-ul ala fiindca nu stii daca are vreo treaba cu un drum de la 1 la n.

1 3 5000
1 2 3000

Raspunsul tau e 3000 aici?

[•vendetta]

da, e 3000.

[•andunhill]

Nu puteti mari limita la timp  ? Am implementat dijkstra cu priority_queue si iau 90  . Vad ca in ultimul timp doar o persoana a reusit sa obtina 100.

[•scipianus]

Nu puteti mari limita la timp  ? Am implementat dijkstra cu priority_queue si iau 90  . Vad ca in ultimul timp doar o persoana a reusit sa obtina 100.

Da,chiar cred ca ar trebui marita  Eu am facut cautare binara dupa rezultat si DFS pentru verificarea unei anumite greutati si iau 80 chiar si cu citire parsata 

[•popoiu.george]

Nu trebuie marita. Am luat 100p cu Dijkstra cu parsare, heap-uri "de mana" si liste "de mana".

[•andunhill]

Nu mi se pare corect faptul ca trebuie sa parsez( adica sa implementez o "bulaneala" cum zic altii) pentru a lua 100  . Nu vad de ce nu ar putea fi marita atat timp cat departajeaza corect solutiile. 

[•klamathix]

Solutia cea mai buna e O(M log*N), vedeti, probabil asta merge.

[•alexalghisi]

Nu trebuie marita. Am luat 100p cu Dijkstra cu parsare, heap-uri "de mana" si liste "de mana".

Intra in timp si Dijkstra cu parsare doar 

[•superman_01]

Buna ziua,
Ma chinui la problema de ceva timp si nu reusesc sa iau decat 90 . Am facut cautare binara +DFS + parsare . Se poate lua 100 cu idee asta  sau trebuie sa o schimb  ?
Multumesc anticipat!

[•SebiSebi]

Incearca sa folosesti BFS in loc de DFS, eu asa am luat 100. Succes! 

[•superman_01]

  a mers. Mersi!

[•FlorinHaja]

Am încercat în toate felurile mai eficiente: DFS iterativ şi căutare binară, BFS şi căutare binară, BFS fără căutare binară (cu formulă), Dijkstra cu set-uri. Citirea o PARSEZ. Dar nicicum nu scap de două TLE-uri . Să fac heap-ul de mână (ar însemna să am sursa în jur de ~3 kB)? :

[•klamathix]

Am marit limita de timp, fiindca era intr-adevar prea stransa. Am reevaluat cea mai recenta sursa si ai luat 100.

Totusi, cateva observatii:

- Set-ul are constanta mare, Dijkstra cu priority_queue se comporta mai bine de obicei.
- Bellman-Ford are complexitate N * M.
- Daca faci cautare binara, trebuie doar sa verifici ca poti ajunge in N, vad ca tu in unele surse calculezi si drumul minim pentru chestia asta.
- Nu ai de ce sa te astepti ca o coada implementata cu array-uri care face modulo la fiecare pas sa se comporte mai bine decat queue<>. Modulo-ul e foarte costisitor. Also, ai pus marimea la coada 66000, ceea ce e o greseala, desi n-au prins-o testele.
- Nu inteleg la ce te referi cu "fara cautare binara (cu formula)".
- Parsarea ta nu e ideala la problema asta fiindca sunt multe linii cu putine numere per linie.
- Cea mai rapida solutie la problema asta asimptotic vorbind (si cred ca si in practica) este sa sortezi muchiile dupa cost, sa le adaugi pe rand si sa te opresti cand sursa si destinatia devin conectate. Ca sa verifici conectivitatea tii paduri de multimi disjuncte.
 

[•FlorinHaja]

Nu inteleg la ce te referi cu "fara cautare binara (cu formula)".

1. M-am referit la relația de recurență ca în soluția oficială, pentru a găsi muchia minimă din lanțul maximal.

- Daca faci cautare binara, trebuie doar sa verifici ca poti ajunge in N, vad ca tu in unele surse calculezi si drumul minim pentru chestia asta.

2. Am trimis și fără să calculez costul minim, dar mi-a dat 50 cu câteva WA-uri.

- Set-ul are constanta mare, Dijkstra cu priority_queue se comporta mai bine de obicei.

3. Nu sunt învățat să folosesc priority_queue. E mai greu de declarat (?)

- Cea mai rapida solutie la problema asta asimptotic vorbind (si cred ca si in practica) este sa sortezi muchiile dupa cost, sa le adaugi pe rand si sa te opresti cand sursa si destinatia devin conectate. Ca sa verifici conectivitatea tii paduri de multimi disjuncte.

4. Soluția cu păduri de mulțimi disjuncte obținea 100 de puncte și înainte de a mări limita de timp?