833 Cablaj

[•stef2n]

Aici puteti discuta despre problema Cablaj.

[•Marker]

ce memorie putina

[•stocarul]

Această problemă a fost dată la Olimpiada Locală din 2009. Pe atunci se folosea Borland și deci implicit te limita și la memorie.

[•Marker]

Astept sa o scoata cineva de 100 sa imi zica si mie cum

[•klamathix]

That's the spirit !

[•Marker]

Destul de Grea pentru o locala

[•Mishu91]

ce memorie putina

Nici nu ai nevoie de prea multă

[•Marker]

Pai cum adik fac 'Prim', da de fiecare data trebuie sa imi recalculez distanta minima, eu aici pierd timp

[•Mishu91]

Cam așa se face, cu complexitatea O(N^2).

[•Marker]

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

[•Mishu91]

Citește aici despre Algoritmul lui Prim în graf dens.

[•dornescuvlad]

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)

[•klamathix]

Pui muchii intre toate nodurile. Nu ai treaba cu MLE pentru ca nu trebuie sa le retii , poti calcula oricand dist( i , j ).

[•dornescuvlad]

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?

[•klamathix]

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).

[•marcelP]

ati putea modifica 18.00 in 18.000? 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

[•klamathix]

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 

[•andreey_047]

Iau 80 , TLE pe ultimele 2 teste 
Am bagat O(n*n) , au ceva special ?

[•klamathix]

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.

[•andreey_047]

Ai dreptate   , da acu iau 20 puncte cu incorect ) ( OK doar pe primu si ultimu test )

Gata 100 !!  
Ms Mihai .

Editat de admin: Cu plăcere! Èši-am combinat mesajele, ca să nu facem postări consecutive degeaba  

[•dorin31]

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 ? 
http://www.infoarena.ro/job_detail/1635672?action=view-source
Merci anticipat! 

[•AlexandruValeanu]

Ar trebui sa o rezolvi fara heap (heap-ul este in plus).

[•dorin31]

Am reusit! 
Merci mult de indicatie! 

[•sicsic]

http://www.infoarena.ro/job_detail/1646507

Isi da seama cineva unde gresec?