infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Stefan Istrate din Martie 24, 2010, 19:10:05



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)
    {
        MM=0x3f3f3f3f;
        int nod;
        for (int i=1;i<=sf;i++)
        {
            if (min[i]==0 || viz[cine[i]]==1)
            {
                min[i]=0x3f3f3f3f;
                for (int j=1;j<=n;j++)
                    if (!viz[j] && Q[i]!=j)
                    {
                        Dist=D(Q[i],j);
                        if (Dist<min[i])
                        {
                            min[i]=Dist;
                            cine[i]=j;
                        }
                    }
            }
            if (min[i]<MM)
            {
                MM=min[i];
                nod=cine[i];
            }
        }
        Rez+=MM;
        viz[nod]=1;
        Q[++sf]=nod;
}
cum fac sa fie mai eficient :-?


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?