Titlul: 833 Cablaj Scris de: Stefan Istrate din Martie 24, 2010, 19:10:05 Aici puteti discuta despre problema Cablaj (http://infoarena.ro/problema/cablaj).
Titlul: Răspuns: 833 Cablaj Scris de: Onicas Mircea din Martie 24, 2010, 19:43:11 ce memorie putina :(
Titlul: Răspuns: 833 Cablaj Scris de: Cosmin-Mihai Tutunaru din Martie 24, 2010, 19:49:59 Această problemă a fost dată la Olimpiada Locală din 2009. Pe atunci se folosea Borland și deci implicit te limita și la memorie.
Titlul: Răspuns: 833 Cablaj Scris de: Onicas Mircea din Martie 24, 2010, 19:53:47 Astept sa o scoata cineva de 100 sa imi zica si mie cum :D :D :banana:
Titlul: Răspuns: 833 Cablaj Scris de: Mihai Calancea din Martie 24, 2010, 20:20:17 That's the spirit !
Titlul: Răspuns: 833 Cablaj Scris de: Onicas Mircea din Martie 24, 2010, 20:33:55 Destul de Grea pentru o locala :D :ok:
Titlul: Răspuns: 833 Cablaj Scris de: Andrei Misarca din Martie 24, 2010, 21:05:19 ce memorie putina :( Nici nu ai nevoie de prea multă :)Titlul: Răspuns: 833 Cablaj Scris de: Onicas Mircea din Martie 24, 2010, 21:29:47 Pai cum :-? adik fac 'Prim', da de fiecare data trebuie sa imi recalculez distanta minima, eu aici pierd timp :-? ](*,)
Titlul: Răspuns: 833 Cablaj Scris de: Andrei Misarca din Martie 24, 2010, 21:32:02 Cam așa se face, cu complexitatea O(N^2).
Titlul: Răspuns: 833 Cablaj Scris de: Onicas Mircea din Martie 24, 2010, 21:42:27 In Q imi tin elementele pe care le-am folosit
Cod: while (sf!=n) Titlul: Răspuns: 833 Cablaj Scris de: Andrei Misarca din Martie 24, 2010, 21:48:42 Citește aici (http://infoarena.ro/problema/apm) despre Algoritmul lui Prim în graf dens. :)
Titlul: Răspuns: 833 Cablaj Scris de: Vlad Eugen Dornescu din Februarie 17, 2011, 12:09:34 As dori sa stiu cum imi construiesc muchiile..
Prima oara am incercat toate combinatiile, dar la N <= 3000 e clar ca nu e avantajos din cauza MLE. Dupa am incercat sa iau pentru fiecare nod i si sa caut nodul j pentru care dist(i, j) sa fie minima. Apoi fac un Kruskal pe muchiile astea. M-am prins ca e incorecta solutia, dar cum sa aleg muchiile pe care sa caut arborele partial de cost minim ? (fiindca in enunt nu e nicio restrictie asupra muchiilor, pot pune muchii intre toate nodurile sau pot avea doar n-1 muchii din start) Titlul: Răspuns: 833 Cablaj Scris de: Mihai Calancea din Februarie 17, 2011, 22:00:15 Pui muchii intre toate nodurile. Nu ai treaba cu MLE pentru ca nu trebuie sa le retii , poti calcula oricand dist( i , j ).
Titlul: Răspuns: 833 Cablaj Scris de: Vlad Eugen Dornescu din Februarie 18, 2011, 14:35:13 Pai eu la Kruskal parcurg un vector de muchii, daca nu le retin inseamna ca nu-s sortate si daca nu-s sortate algoritmul va fi un greedy gresit.Deci?
Titlul: Răspuns: 833 Cablaj Scris de: Mihai Calancea din Februarie 18, 2011, 14:47:56 Cu Kruskal poti actualiza apm-ul dupa ce introduci un nou punct luand in considerare doar muchiile din apm-ul precedent si muchiile noi. Deci poti mentine memoria la O(n).
Dar n-o sa-ti intre timp. Trebuie sa faci Prim in O(n ^ 2). Titlul: Răspuns: 833 Cablaj Scris de: Fake name din Iulie 11, 2014, 17:27:45 ati putea modifica 18.00 in 18.000? :D Adica io m-am luat dupa exemplu si am afisat cu 2 zecimale si luam WA pe 8 teste si nu stiam de ce..E okey oricum doar ca sa nu mai fie confuzie si la altii :)
Titlul: Răspuns: 833 Cablaj Scris de: Mihai Calancea din Iulie 11, 2014, 21:13:31 Dacă afișezi cu 2 zecimale, cel mai des a doua nu e cea reală fiindcă numărul e rotunjit la ultima zecimală. Ceea ce înseamnă că eroarea ta e mai mare de 0.001, cât scrie în enunț. Când enunțul îți vorbește doar de eroare relativa/absolută acceptată, e bine să afișezi cât mai multe zecimale. Le limitezi doar când îți specifică ei numărul fix sau îți spun explicit cum să le rotunjești :)
Titlul: Răspuns: 833 Cablaj Scris de: Andrei Maxim din Martie 13, 2015, 20:21:03 Iau 80 , TLE pe ultimele 2 teste ](*,) ](*,) ](*,)
Am bagat O(n*n) , au ceva special ? Titlul: Răspuns: 833 Cablaj Scris de: Mihai Calancea din Martie 13, 2015, 20:32:31 N-au nimic special. Dacă vrei un sfat pentru optimizare, cred că sqrt()-ul ăla e problema, e o operație costisitoare și o faci foarte des. N-ai nevoie de ea, poți compara distanțele și ridicate la pătrat. Apoi scoți radical la sfârșit doar din muchiile din arbore ca să obții rezultatul.
Titlul: Răspuns: 833 Cablaj Scris de: Andrei Maxim din Martie 13, 2015, 21:46:29 Ai dreptate :shock: , da acu iau 20 puncte cu incorect :)) ( OK doar pe primu si ultimu test ) :angry: :angry:
Gata 100 !! :yahoo: :yahoo: Ms Mihai . Editat de admin: Cu plăcere! Ți-am combinat mesajele, ca să nu facem postări consecutive degeaba :) Titlul: Răspuns: 833 Cablaj Scris de: Geman Dorin Andrei din Martie 06, 2016, 20:10:02 Iau 30p, iar pe restul MLE. :?
Mi-ati putea da o idee referitoare la ce ar trebui modificat? Folosesc o structura de date de care nu am nevoie ? #-o http://www.infoarena.ro/job_detail/1635672?action=view-source Merci anticipat! :ok: Titlul: Răspuns: 833 Cablaj Scris de: Alexandru Valeanu din Martie 06, 2016, 20:13:47 Ar trebui sa o rezolvi fara heap (heap-ul este in plus).
Titlul: Răspuns: 833 Cablaj Scris de: Geman Dorin Andrei din Martie 06, 2016, 21:23:38 Am reusit! :ok:
Merci mult de indicatie! :D Titlul: Răspuns: 833 Cablaj Scris de: FMI-Coteanu Vlad din Martie 10, 2016, 16:35:14 http://www.infoarena.ro/job_detail/1646507
Isi da seama cineva unde gresec? |