725 Desen

[•wefgef]

Aici puteţi discuta despre problema Desen.

[•pauldb]

Aceasta problema a fost reevaluata, deoarece a fost gasita o greseala in evaluator.

[•taloibogdan]

Poate cineva sa-mi dea si mie un test mai mare? Nu stiu de ce nu imi merge.

[•Mishu91]

Cod:

100
18733 15798
13229 18540
3097 27112
16584 7868
8871 20257
7962 13301
22743 18219
2683 20106
8691 28757
22454 25322
2193 21549
25034 15551
18074 9982
21336 6040
5094 3096
4394 11760
18894 17623
18232 9923
2667 4815
17791 11538
13004 13685
12772 23679
1902 3387
13785 10593
20076 24171
23847 10202
15719 18880
25753 3792
28863 5020
9832 21889
8116 14226
21581 27010
19782 9813
24865 22449
2560 587
21919 15565
14273 22623
9243 4107
26011 10960
2632 16086
5130 26479
14220 20849
15358 27905
12573 14220
2924 10337
24042 11040
12496 15622
25982 2277
13367 20846
12658 15928
21434 4576
1492 23639
27200 28668
27746 11142
27561 377
15160 20623
14788 29381
29405 145
27285 11977
2298 209
22315 26340
11249 4810
29894 25164
25020 13261
16009 7677
29189 25375
185 18613
6945 15317
17280 22623
26459 2772
23000 11619
23396 7787
28932 22800
25866 26216
4776 28164
14357 15023
12435 13539
19833 260
8702 2784
13521 12643
10461 641
25951 28580
19254 2895
13896 24467
25519 28288
15171 6450
27839 8566
2170 26770
1365 28036
10917 24075
14131 13207
27030 14498
26746 4795
14758 23380
7579 16212
23955 18041
4785 19905
4552 24040
10733 18448
6438 6251

Si mie imi da cu sursa de 100

Cod:

0.0000
6149.1934
19420.8402
27636.8673
28011.9690
35027.1110
39711.2695
43956.6269
49787.4811
56896.3580
57038.0345
60554.6955
60778.2131
65869.6852
76470.0365
78448.4715
79080.8160
79129.1678
80567.5434
80658.7613
83068.1191
88227.3991
89847.4019
91696.4953
93751.7355
98612.5343
99680.2020
104636.3490
107980.0122
108156.7042
108955.6820
110856.0696
110742.0677
112702.8851
115579.1611
117256.1427
118419.9496
122690.3502
124983.2654
127484.8195
128010.5252
128246.9545
133201.3942
133427.5630
133844.9658
134383.0640
134432.9255
135965.1350
136615.5856
136626.8500
137527.5599
137921.9468
143728.8593
145473.3790
147943.8528
148266.4205
149848.6582
151707.1952
152546.6242
153006.5460
152731.8599
154857.4763
159277.3916
159910.6573
160277.4612
160250.1203
162657.5646
163967.9867
165346.0061
165689.3670
166881.4262
167958.7201
169372.1178
171189.2647
172495.4941
174398.3480
174902.0739
179505.4485
180285.8517
180326.8785
183099.3377
183925.5712
184772.9059
184927.1171
185183.8735
185392.8342
187271.8251
187637.5362
189137.7965
190033.0004
190790.9356
193047.6644
193296.6807
193466.4219
194436.2559
195259.9576
197091.6606
199480.8083
201598.3650
204936.7852

[•toni2007]

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.

[•DraStiK]

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?

[•Mishu91]

Da, se poate lua 100 cu O(N² logN)

[•gabitzish1]

Eu luam 40 + TLE cu O(N2 logN) pt ca greseam la functia de comparare cand sortam.

[•DraStiK]

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;
               double c;} a[DIM];

inline int cmp (muchie a,muchie b)
{
    return a.c<b.c;
}

[•gabitzish1]

Eu luam 40 cu asta :

Cod:

struct muchie
{
	int x, y, c;
} v[100004];

int cmp (struct muchie x, struct muchie y)
{
	return x.c < y.c;
}

si 100 cu asta:

Cod:

struct muchie
{
	int x, y, c;
} v[100004];

int cmp (const muchie &x, const muchie &y)
{
	return x.c < y.c;
}

[•DraStiK]

Multumesc mult, Gabi.

Totusi, poate sa imi explice cineva de ce merge mai repede:

Cod:

int cmp (const muchie &a,const muchie &b)
{
    return a.c<b.c;
}

decat:

Cod:

int cmp (muchie a,muchie b)
{
    return a.c<b.c;
}

Multumesc anticipat.

[•blasterz]

Multumesc mult, Gabi.

Totusi, poate sa imi explice cineva de ce merge mai repede:

Cod:

int cmp (const muchie &a,const muchie &b)
{
    return a.c<b.c;
}

decat:

Cod:

int cmp (muchie a,muchie b)
{
    return a.c<b.c;
}

Multumesc anticipat.

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

[•Bit_Master]

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

[•balakraz94]

Evaluatorul e setat bine?
Pentru ca iau 40p cu O(n^2*logn) si cu functia de comparare facuta cum trebuie.

[•wefgef]

Am modificat limita de timp la 0.3 secunde.

[•Theory]

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.

[•geniucos]

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?

[•alexalghisi]

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 ?

[•danalex97]

Sa iti dau un exemplu ... Ai 3 puncte care determina un triunghi echilateral. In cazul asta ai 3 APM-uri. 

[•alexalghisi]

Da , dar valoarea apmului nu e aceeasi ? 

[•danalex97]

El se referea la APM , nu la costul sau. Nu s-a exprimat corect.

[•antonioteo]

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  

[•a_h1926]

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!

[•Fayed]

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?

[•Theory]

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.