infoarena

Aici puteţi discuta despre problema Cuplaj maxim de cost minim (http://infoarena.ro/problema/cmcm).

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  :-# se intampla?

STL contine functii foarte rapide care au fost optimizate la maxim si asta, desigur, va duce  la o performanta mai buna

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.

Salut,

Mi se pare putin dubioasa limita de timp la aceasta problema. Nici macar solutia oficiala http://infoarena.ro/job_detail/633177 (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

Da, limita e prea stransa, incearca citirea din c++ sau citirea parsata.

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


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

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.

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

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.

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  ](*,)
Cel mai interesant este faptul ca pe calculatorul meu ea merge mai repede decit solutia oficiala  :'(

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?

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.

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 (http://www.infoarena.ro/job_detail/1871384?action=view-source)