Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 038 Cuplaj maxim de cost minim  (Citit de 7516 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« : Decembrie 07, 2009, 14:33:31 »

Aici puteţi discuta despre problema Cuplaj maxim de cost minim.
« Ultima modificare: Decembrie 21, 2009, 12:10:12 de către Marius Stroe » Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
Goten
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 6



Vezi Profilul
« Răspunde #1 : Martie 03, 2010, 18:43:01 »

La problema asta am facut solutii fara STL (cu Bellman-Ford si Dijkstra) si iau pe ele TLE pe ultimele 5 teste (si sunt corecte, comparate cu cea de 100). Cu STL am luat 100.
Treaba e ca la mine pe calculator, in MinGW, o solutie fara STL e de vreo doua ori mai rapida decat cu STL.  Aha
Luminati-ma, va rog, ce  Silenced se intampla?
Memorat
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #2 : Martie 03, 2010, 19:14:15 »

La problema asta am facut solutii fara STL (cu Bellman-Ford si Dijkstra) si iau pe ele TLE pe ultimele 5 teste (si sunt corecte, comparate cu cea de 100). Cu STL am luat 100.
Treaba e ca la mine pe calculator, in MinGW, o solutie fara STL e de vreo doua ori mai rapida decat cu STL.  Aha
Luminati-ma, va rog, ce  Silenced se intampla?
STL contine functii foarte rapide care au fost optimizate la maxim si asta, desigur, va duce  la o performanta mai buna
Memorat
toni2007
Nu mai tace
*****

Karma: 160
Deconectat Deconectat

Mesaje: 663



Vezi Profilul
« Răspunde #3 : Martie 03, 2010, 23:56:19 »

Nu-i adevarat. Vectorii stl de exemplu consuma memorie mai multa decat cei standard (aloca bucati de lungime puteri a lui 2), si merg mult mai incet din cauza claselor. Stiu ca era o problema aici pe infoarena care nu mergea facuta cu vectori stl ci doar cu alocare dinamica din cauza faptului ca stl-ul mergea incet. In rest, e adevarat, merge sa codezi mult mai repede folosind stl. Daca timpul sau memoria nu conteaza asa mult nu vad de ce nu ai folosi stl.

Si nu imi spuneti ca pt vectori merge cu reserve. Daca faci asa, trebuie sa citesti de 2 ori fisierul de intrare si e acelasi lucru ca si cu alocarea dinamica.
Memorat
claudiumihail
Strain
*

Karma: 5
Deconectat Deconectat

Mesaje: 33



Vezi Profilul
« Răspunde #4 : Noiembrie 13, 2011, 01:38:04 »

Salut,

Mi se pare putin dubioasa limita de timp la aceasta problema. Nici macar solutia oficiala http://infoarena.ro/job_detail/633177 nu pare sa ia punctaj maxim. Iar toti cei care au punctaj maxim au pe limita de timp veche. Asa ca....ce-i de facut?

Claudiu
Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #5 : Noiembrie 13, 2011, 11:29:36 »

Da, limita e prea stransa, incearca citirea din c++ sau citirea parsata.
Memorat
claudiumihail
Strain
*

Karma: 5
Deconectat Deconectat

Mesaje: 33



Vezi Profilul
« Răspunde #6 : Noiembrie 13, 2011, 17:57:53 »

Cand zici citire parsata, vrei sa spui sa fac ceva de genul asta:

Cod:

int x, y, cost;
char str[32];
fstream fin("cmcm.in", fstream::in);

....
fin.getline(str, 32);
sscanf(str, "%d %d %d", &x, &y, &cost);
....


Chiar asa de mult conteaza citirea aia la problema asta, cand eu folosesc oricum citirea din C++? Sau vrei sa spun ca modul in care o fac eu cu fin >> x >> y >> cost; nu e asa bun?

Claudiu
Memorat
svalentin
Nu mai tace
*****

Karma: 88
Deconectat Deconectat

Mesaje: 704



Vezi Profilul
« Răspunde #7 : Noiembrie 13, 2011, 19:37:57 »

Limita era mult prea mica. Era 0.55s desi implementarea oficiala rula in ~1.05s. Probabil limita a fost modificata dupa ce s-a schimbat evalul.
Am crescut limita la 1.2s.
Memorat
ioalexno1
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 2



Vezi Profilul
« Răspunde #8 : Martie 23, 2012, 12:13:58 »

Imi poate spune cineva de ce sursa http://infoarena.ro/job_detail/721120?action=view-source nu ia 100 de puncte?

LE : @Stefan Tot 50 de puncte imi da.
LE2: Never mind. Am folosit vector din STL si am luat 100
« Ultima modificare: Martie 28, 2012, 01:26:02 de către Alexandru Bunget » Memorat
Prostu
Nu mai tace
*****

Karma: 134
Deconectat Deconectat

Mesaje: 323



Vezi Profilul
« Răspunde #9 : Martie 23, 2012, 13:06:17 »

Imi poate spune cineva de ce sursa http://infoarena.ro/job_detail/721120?action=view-source nu ia 100 de puncte?

Testeaza sa vezi cum merge daca tii liniile din matricea drumurilor intr-un bloc continuu, adica sa folosesti vector sau un tablou bidimensional. Listele alocate dinamic sunt destul de incete pentru ca pointerii sunt imprastiati prin memorie si salturile de la un element la altul sunt costisitoare.
Memorat
ctlin04
Nu mai tace
*****

Karma: 23
Deconectat Deconectat

Mesaje: 207



Vezi Profilul
« Răspunde #10 : August 25, 2012, 18:40:06 »

As fi recunoscator daca cineva mi-ar spune de ce sursa mea i-a doar 60 p. restu TLE, http://infoarena.ro/job_detail/782071  Brick wall
Cel mai interesant este faptul ca pe calculatorul meu ea merge mai repede decit solutia oficiala  Cry
Memorat
CosminRusu
De-al casei
***

Karma: 77
Deconectat Deconectat

Mesaje: 104



Vezi Profilul
« Răspunde #11 : Martie 12, 2014, 15:26:38 »

Buna!

Am rezolvat problema Atac2 care se bazeaza pe cuplaj maxim de cost minim si initial luam 60 de puncte fiindca pentru o muchie x -> y nu adaugam costul -z muchiei y -> x. Poate sa imi explice cineva de ce se introduce acea muchie de cost invers?
Memorat
SRadu
Client obisnuit
**

Karma: 31
Deconectat Deconectat

Mesaje: 74



Vezi Profilul
« Răspunde #12 : Martie 12, 2014, 16:23:57 »

Pentru ca tu poti ajunge in urmatoarea situatie:
Poti creste cardinalitatea cuplajului, insa faci asta mergand si pe muchii inverse. Daca bagi flux pe muchia inversa, inseamna ca il scazi de pe muchia directa, deci trebuie sa bagi -z la cost.
Memorat
borcanirobert
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 3



Vezi Profilul
« Răspunde #13 : Februarie 07, 2017, 12:29:34 »

Hei, eu nu inteleg de ce iau doar 80 de puncte. Zice ca numar muchii incorect la testul 6 si 9, dar am descarcat testele si mie imi da bine pe toate. Imi poate spune cineva care e problema? Aici e sursa mea: http://www.infoarena.ro/job_detail/1871384?action=view-source
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

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