|
Titlul: 725 Desen Scris de: Andrei Grigorean din Mai 25, 2008, 22:11:36 Aici puteţi discuta despre problema Desen (http://infoarena.ro/problema/desen).
Titlul: Răspuns: 725 Desen Scris de: Paul-Dan Baltescu din Decembrie 07, 2008, 13:37:30 Aceasta problema a fost reevaluata, deoarece a fost gasita o greseala in evaluator.
Titlul: Răspuns: 725 Desen Scris de: Taloi Bogdan Cristian din Iunie 05, 2009, 14:32:15 Poate cineva sa-mi dea si mie un test mai mare? #-o Nu stiu de ce nu imi merge. :oops:
Titlul: Răspuns: 725 Desen Scris de: Andrei Misarca din Iunie 05, 2009, 16:08:12 Cod: 100 Si mie imi da cu sursa de 100 Cod: 0.0000 Titlul: Răspuns: 725 Desen Scris de: Pripoae Teodor Anton din Iunie 05, 2009, 16:50:30 Citat Poate cineva sa-mi dea si mie un test mai mare? d'oh! Nu stiu de ce nu imi merge. Embarassed Solutia nu e unic determinata :). Mai bine iti faci un program care compara raspunsul tau cu testul de aici, si verifica sa dea acelasi cost. Titlul: Răspuns: 725 Desen Scris de: Dragos Oprica din August 24, 2009, 10:41:01 Cu o complexitate de O (n^2 log n) se poate lua 100?
Eu cred ca am complexitatea asta si iau doar 40, cu 6 TLE. Any help? :D Titlul: Răspuns: 725 Desen Scris de: Andrei Misarca din August 24, 2009, 12:01:06 Da, se poate lua 100 cu O(N2 logN)
Titlul: Răspuns: 725 Desen Scris de: Gabriel Bitis din August 24, 2009, 12:10:43 Eu luam 40 + TLE cu O(N2 logN) pt ca greseam la functia de comparare cand sortam.
Titlul: Răspuns: 725 Desen Scris de: Dragos Oprica din August 24, 2009, 12:37:05 Eu luam 40 + TLE cu O(N2 logN) pt ca greseam la functia de comparare cand sortam. Sortez crescator dupa costuri. Doar atat. LE: Structura mea arata cam asa, iar functie de comparare (pentru sort din STL) Cod: struct muchie {int x,y;Titlul: Răspuns: 725 Desen Scris de: Gabriel Bitis din August 24, 2009, 12:49:13 Eu luam 40 cu asta :
Cod: struct muchie si 100 cu asta: Cod: struct muchie Titlul: Răspuns: 725 Desen Scris de: Dragos Oprica din August 24, 2009, 13:03:05 Multumesc mult, Gabi. :yahoo:
Totusi, poate sa imi explice cineva de ce merge mai repede: Cod: int cmp (const muchie &a,const muchie &b) decat: Cod: int cmp (muchie a,muchie b) Multumesc anticipat. :D Titlul: Răspuns: 725 Desen Scris de: Mircea Dima din August 24, 2009, 13:22:27 Multumesc mult, Gabi. :yahoo: Totusi, poate sa imi explice cineva de ce merge mai repede: Cod: int cmp (const muchie &a,const muchie &b) decat: Cod: int cmp (muchie a,muchie b) Multumesc anticipat. :D Defapt cel mai rapid e asa: struct cmp { bool operator()(const muchie &a, const muchie &b)const { if(a.c < b.c) return 1; return 0; } }; Faza e ca STL-ul foloseste functori (chestia de mai sus) si daca tu nu ii dai functor el in timpul rularii face transformarea din functia ta intr-un functor ( cu ptr_fun sau ceva de genu asta) si de asta e mai lent. A si inca un motiv: tu i-ai dat o copie a unei muchii (adica se apeleaza un constructor) pe cand in functorul meu ii dau referinta. PS. sort-ul il apelezi asa: sort(a, a+N, cmp()); //observa cele 2 paranteze de dupa cmp :P Titlul: Răspuns: 725 Desen Scris de: Alexandru-Iancu Caragicu din Martie 20, 2010, 15:06:16 "Ea defineste notiunea de arbore partial pentru un set de S puncte ca fiind o submultime de exact S-1 segmente avand capetele printre punctele date, astfel incat sa se poata ajunge dintr-un punct in oricare altul mergand pe segmentele alese."
In exemplu, dupa ce se creeaza punctul 2 2, solutia ar fi trebuit sa fie 5.656854, nu 6, pt ca poti ajunge in orice punct si cu aceeasi configuratie de mai jos, cand se adauga pct 1 1 (mergand jumatati de segmente). Ar trebui sa spuna in cerinta ca se merg segmente intregi. Titlul: Răspuns: 725 Desen Scris de: abcd efgh din Noiembrie 09, 2011, 19:50:57 Evaluatorul e setat bine?
Pentru ca iau 40p cu O(n^2*logn) si cu functia de comparare facuta cum trebuie. Titlul: Răspuns: 725 Desen Scris de: Andrei Grigorean din Noiembrie 09, 2011, 22:20:43 Am modificat limita de timp la 0.3 secunde.
Titlul: Răspuns: 725 Desen Scris de: theo .c din Aprilie 30, 2012, 14:51:00 hm...ma ajuta cineva cu un pont? Eu tin intr-o structura toate muchiile(segmente) posibile, adaugand inca i - 1 la punctul i, dupa care le sortez dupa indice cu STL si fac un APM , cu arbori (adica NU verific ciclurile cu DFS), iau 30 de puncte, in rest TLE. :(
Titlul: Răspuns: 725 Desen Scris de: Oncescu Costin din Iunie 29, 2012, 15:19:36 Eu am facut cu set.La fiecare moment cand inseram o noua muchie fata de muchiile folosite la APM-ul precedent foloseam set
am declararea struct-lui asa cod: struct str { int x,y; double c; str(){ x=y=0; c=0; } str (int xx,int yy,double cc) { x=xx; y=yy; c=cc; } inline bool operator <(const str &p)const{ return c<=p.c; } }; Am complexitatea tot n^2logn si iau 40.Am vazut ca mai sunt unii care au luat 40 si apoi 100 datorita functiei de comparare. Ma poate ajuta cineva? :'( Titlul: Răspuns: 725 Desen Scris de: Alghisi Alessandro Paolo din Decembrie 09, 2012, 21:06:04 Citat Poate cineva sa-mi dea si mie un test mai mare? d'oh! Nu stiu de ce nu imi merge. Embarassed Solutia nu e unic determinata :). Mai bine iti faci un program care compara raspunsul tau cu testul de aici, si verifica sa dea acelasi cost. De ce nu ? Titlul: Răspuns: 725 Desen Scris de: Dan H Alexandru din Decembrie 10, 2012, 15:51:18 Sa iti dau un exemplu ... Ai 3 puncte care determina un triunghi echilateral. In cazul asta ai 3 APM-uri. :wink:
Titlul: Răspuns: 725 Desen Scris de: Alghisi Alessandro Paolo din Decembrie 10, 2012, 18:45:28 Da , dar valoarea apmului nu e aceeasi ? :D
Titlul: Răspuns: 725 Desen Scris de: Dan H Alexandru din Decembrie 10, 2012, 21:38:47 El se referea la APM , nu la costul sau. Nu s-a exprimat corect. :ok:
Titlul: Răspuns: 725 Desen Scris de: Zait Teodor Antonio din Decembrie 13, 2012, 15:59:28 Salut !
Eu folosesc o functie Kruskal , pe care o apelez de N - 1 ori ( ma folosesc de paduri de multimi disjuncte pentru kruskal ). Iau 30p TLE cu sursa mea.. Ar putea sa imi dea cineva un hint pentru ideea de 100p va rog ? L.E : Am reusit ! Multumesc mult pentru idee :) :yahoo: Titlul: Răspuns: 725 Desen Scris de: Heidelbacher Andrei din Decembrie 13, 2012, 17:48:30 Nu e nevoie sa faci Kruskal de la 0, cu toate muchiile posibile (ca asa ai complexitate O(N^3 logN)). Cand adaugi un punct nou i, el vine cu i-1 muchii noi pe care le vei lua in considerare pentru APM, si mai trebuie sa vezi ce muchii de la pasul precedent merita sa le iei in considerare. Complexitatea buna e O(N^2 logN). Succes!
Titlul: Răspuns: 725 Desen Scris de: Stratulat Alexandru din Februarie 27, 2013, 21:08:50 Eu am o nelamurire. La un momentdat in exemplu, arborele de cost minim era 6, apoi cand s-a mai adaugat un nod costul in loc sa creasca a scazut la 5.656854. Daca adaug un nod nou nu trebuie sa gasesc distanta minima la unul din nodurile arborelui deja construit si sa o adaug la suma de cost minim a arborelui?
Titlul: Răspuns: 725 Desen Scris de: theo .c din Februarie 28, 2013, 00:18:52 Gandeste-te daca ai 4 puncte care formeaza un patrat. Daca pui un punct in centru atunci poti forma un APM cu diagonalele, cu un cost evident mai mic. Parca asta era si in exemplul problemei.
Titlul: Răspuns: 725 Desen Scris de: Stratulat Alexandru din Februarie 28, 2013, 13:24:42 Ok am inteles, thanks man
Titlul: Răspuns: 725 Desen Scris de: zzz zzz din Mai 18, 2013, 17:40:41 APM-ul de la pasul i este APM-ul de la i-1 la care se adauga o muchie intre noul punct si unul dintre punctele citite astfel incat lungimea noului segment sa fie minima?
Titlul: Răspuns: 725 Desen Scris de: Paul-Dan Baltescu din Mai 18, 2013, 17:54:30 Nu neaparat.
Titlul: Răspuns: 725 Desen Scris de: Tudor-Stefan Berbinschi din Februarie 12, 2016, 13:21:52 Salut, am si eu o problema cu complexitatea la problema asta. Nu am nicio idee cum scap de sortarea muchiilor la fiecare nou nod introdus. Imi poate impartasi cineva vreo idee? Iau 30p si pe restu' numa TLE ???
http://www.infoarena.ro/job_detail/1597847 |