10012 - How Big Is It?

[Adrian Kuegel]

I think my solution for this problem is correct; I calculate the distance between two circles with pythagoras and check all permutions of the circles. My program gives the right answer for the sample input. Can someone please give me a difficult input line?

[Adrian Kuegel]

I found my problem. Consider this input line:
3 2.0 0.4 2.0
The correct output is 8.000, not 7.578

[Revenger]

Why I get WA?

[pascal]Program p10012;

Const MaxM = 7;

Var N,M,i,j : Integer;
R : Array[1..MaxM]of Extended;

Procedure Solve;
Var Ans : Extended;
O,U : Array[1..MaxM]of Byte;
Procedure GetSize;
Var i,j,k : Integer;
a,b : Extended;
d : array[0..MaxM,0..MaxM]of Extended;
begin
for i:=0 to MaxM do
for j:=0 to MaxM do
d[i,j]:=-10;
for j:=1 to M+1 do
for i:=0 to M-j+1 do begin
if (i=0)and(j<=M) then d[0,j]:=R[O[j]] else
if (i+j=M+1)and(i>0) then d[i,M+1]:=R[O] else
if (i>0)and(i+j<=M) then begin
a:=Abs(R[O]-R[O[i+j]]);
b:=R[O]+R[O[i+j]];
d[i,i+j]:=sqrt(b*b-a*a);
end;
for k:=i+1 to i+j-1 do
if d[i,i+j]<d[i,k]+d[k,i+j] then
d[i,i+j]:=d[i,k]+d[k,i+j];
end;
if d[0,M+1]<Ans then Ans:=d[0,M+1];
end;
Procedure Rec(Step : Integer);
Var i : Integer;
begin
if Step=M+1 then begin
GetSize;
Exit;
end;
for i:=1 to M do
if U=0 then begin
U:=1;
O[Step]:=i;
Rec(Step+1);
U:=0;
end;
end;
begin
Ans:=10E10;
FillChar(U,SizeOf(U),0);
Rec(1);
Writeln(Ans:0:3);
end;

begin
Read(N);
for i:=1 to N do begin
Read(M);
for j:=1 to M do Read(R[j]);
if M>0 then Solve else Writeln('0.000');
end;
end.[/pascal]

Please, help me !

[Revenger]

It is very strange. Then I wrote

Code: Select all

MaxM = 7

or

Code: Select all

MaxM = 8

my program gets WA. But then I wrote

Code: Select all

MaxM = 10

it get Accepted!

Very Strange

[Trickster]

Hi everyone,

i

[david]

Your solution, 7.58, is based on putting the big 2.0 circle, then the small one and then the big one again. The problem is that the two big circles overlap in such a layout.

[ditrix]

Can anybody check these input/output. please?

Input:

Code: Select all

100
8 1.344 0.852 0.269 1.472 3.170 1.329 0.579 2.847
3 0.196 0.009 0.735
7 0.030 3.821 1.368 1.545 5.434 0.934 0.105
3 0.467 0.889 0.461
7 0.744 1.173 1.035 0.354 0.300 1.102 0.708
6 1.419 5.220 1.208 0.714 1.741 8.151
7 0.453 2.879 1.834 3.639 1.361 0.558 1.280
8 10.519 0.553 4.513 0.911 1.170 0.293 0.678 1.463
2 1.069 0.616
5 1.780 3.458 2.220 0.659 0.750
8 0.146 1.085 7.379 0.992 4.334 3.427 0.608 2.375
1 0.155
5 0.119 2.052 0.379 2.150 0.693
4 63.499 0.249 3.666 0.322
5 1.890 4.796 0.583 0.187 0.347
1 1.079
4 0.209 1.862 1.430 5.867
8 3.265 0.590 0.054 1.583 0.074 1.585 0.525 0.989
4 2.232 7.205 150.375 1.467
1 11.740
6 10.779 3.807 1.716 0.428 0.536 1.224
4 1.071 2.685 0.794 0.117
4 0.608 0.486 0.135 4.533
1 0.469
8 2.294 0.756 10.556 3.538 2.250 0.383 0.858 1.160
3 2.463 1.446 1.809
5 2.174 0.154 0.322 0.539 0.847
7 0.429 1.694 2.170 0.214 0.369 0.275 8.182
5 2.159 0.739 1.132 0.733 0.328
3 7.906 3.212 1.724
1 3.759
4 2.750 1.045 1.434 19.391
2 0.241 12.710
4 0.900 0.978 0.568 0.968
7 1.056 0.084 1.089 3.910 0.114 1.221 2.411
3 2.301 1.375 0.298
2 0.376 0.532
4 2.275 0.261 0.087 2.705
5 0.605 1.057 0.257 0.706 0.861
3 0.203 0.627 0.848
1 4.048
5 3.357 0.641 4.038 0.864 0.667
8 0.252 0.416 1.932 0.365 0.621 0.502 8.299 0.318
2 40.436 3.087
7 0.682 2.496 0.322 0.786 0.128 0.625 0.438
4 1.042 2.291 0.724 1.504
8 1.460 5.581 0.001 25.125 1.713 2.704 0.342 0.716
6 0.102 0.469 0.859 4.451 2.170 1.602
8 1.830 14.377 0.517 0.685 1.184 0.001 1.011 1.385
6 0.855 0.000 1.823 0.768 0.426 1.157
5 0.647 2.051 0.537 1.676 0.339
3 3.623 0.364 0.994
8 0.947 1.024 0.263 0.773 1.279 4.074 49.961 0.065
2 6.345 16.925
5 4.651 0.156 1.075 0.480 2.629
5 1.256 0.227 0.054 0.035 1.912
2 1.203 0.751
7 5.175 0.518 1.108 8.091 0.274 1.003 0.555
6 0.291 0.175 0.370 7.216 0.554 1.628
7 0.847 0.676 0.577 0.492 1.407 0.868 10.257
2 0.812 1.108
6 1.286 19.802 0.499 0.333 0.598 13.306
3 0.688 0.263 21.964
1 0.748
8 0.203 1.499 23.346 1.314 2.114 0.833 1.757 14.082
7 7.280 0.942 0.389 1.521 1.467 0.963 2.634
6 0.588 0.239 0.647 2.450 1.536 0.291
8 22.087 1.160 10.010 0.527 1.168 0.720 0.184 0.670
7 3.225 1.402 1.486 2.549 1.023 1.008 2.263
2 0.955 1.202
5 3.073 7.774 6.587 8.906 1.282
6 0.301 0.835 4.213 0.848 5.414 1.315
4 0.731 2.590 2.308 0.235
1 1.250
8 0.383 3.919 0.738 0.429 0.663 0.698 1.331 1.531
7 1.280 0.356 0.686 1.039 0.680 0.058 0.490
6 1.031 0.174 1.945 0.773 0.680 0.466
8 0.413 0.689 4.510 0.694 1.453 3.161 0.971 0.283
3 0.781 1.030 1.666
3 0.061 1.953 1.654
3 0.036 0.741 0.477
3 1.826 2.268 2.851
7 0.319 2.537 1.363 35.278 0.172 6.054 4.533
2 5.517 1.447
2 0.226 0.493
8 2.559 0.443 4.470 1.445 1.162 0.258 0.193 1.644
4 0.563 3.274 1.186 0.803
8 0.303 7.870 17.105 0.734 1.000 6.424 3.592 2.105
7 1.028 2.475 1.486 0.505 0.480 0.133 1.702
2 0.528 1.190
4 8.753 0.326 0.944 0.843
2 0.870 1.001
4 0.324 0.899 0.772 5.190
8 0.182 2.026 12.486 2.303 1.066 4.099 0.923 1.286
7 2.644 0.931 0.367 0.779 0.618 0.190 11.166
8 1.903 0.002 1.174 3.766 0.789 1.874 7.221 0.830
8 0.579 0.657 0.518 0.567 19.806 0.080 0.186 2.428
6 0.778 3.006 5.973 8.024 0.042 0.268
7 0.148 0.226 3.190 0.146 1.708 0.398 0.317
5 2.595 0.559 0.306 1.292 1.908

My output:

Code: Select all

20.334
3.170
21.870
3.497
9.809
28.015
20.397
28.812
3.308
14.987
32.716
0.608
9.063
126.998
12.707
2.158
15.695
14.333
300.750
150.375
27.398
8.177
9.066
0.938
31.701
11.251
10.556
19.737
8.877
22.398
7.518
38.782
25.420
6.718
17.124
7.233
2.301
9.941
6.453
3.018
8.096
14.976
18.239
80.872
8.694
10.299
54.389
15.754
28.754
14.377
8.777
8.412
99.922
43.996
15.114
6.267
3.855
26.208
15.699
20.514
3.817
65.572
43.928
1.496
73.691
23.309
9.041
61.835
23.824
4.300
49.918
20.044
10.248
2.500
15.232
8.357
8.829
18.325
6.712
7.202
2.407
13.743
70.560
12.615
1.387
20.281
9.581
61.570
13.133
3.303
17.506
3.737
10.409
34.572
24.677
27.367
39.612
32.294
9.566
11.336

[little joey]

Code: Select all

knoppix@ttyp0[p10012.cpl]$ diff test2.joa test2.out
2c2
< 1.690
---
> 3.170
12c12
< 0.310
---
> 0.608
20c20
< 23.480
---
> 150.375
27c27
< 6.269
---
> 10.556
37c37
< 1.802
---
> 2.301
50c50
< 9.145
---
> 14.377
knoppix@ttyp0[p10012.cpl]$

[ditrix]

Thank you! Your data was very helpfull, I found the bug and got accespted.
It was a some particular interference with previously calculated values...

[ImLazy]

This is my algorithm which gets WA:

Code: Select all

First, put the biggest circle in the box.
Then put the 2th biggest circle into the box, insert it at the place which makes the smallest width of the 2 circles.
Then put the 3rd biggest circle into the box, insert it at the place which makes the smallest width of the 3 circles.
Then...... Until All circles are in the box.

But I get WA.
This is my test IO. I think my output is wrong.
Input

Code: Select all

5
8 1.344 0.852 0.269 1.472 3.170 1.329 0.579 2.847
7 0.030 3.821 1.368 1.545 5.434 0.934 0.105
7 0.744 1.173 1.035 0.354 0.300 1.102 0.708
4 0.900 0.978 0.568 0.968
7 1.056 0.084 1.089 3.910 0.114 1.221 2.411

Output

Code: Select all

20.632 (the sequence of circles: 6 8 7 4 3 2 5 1)
22.188 (7 1 6 2 4 5 3)
10.082 (6 5 1 4 2 7 3)
6.733 (4 1 3 2)
17.265 (5 2 1 7 6 4 3)

Must I use exhaustive search? Is there any non-exhaustive algorithm?

[ImLazy]

What about your algorithms? Do you use exhaustive search?

[chunyi81]

Hi, you will have to use exhaustive search. notice that since all circles have to touch the bottom of the box, and there are a maximum of 8 circles, for 8 circles the number of permutations is at most 8! = 40320. you can prune this by half due to symmetry, or ceil(0.5 * number of permutations of the circles). Note the ceil, because, suppose there are 3 circles with diameters 1.0, 1.0, 2.0, then number of permutations = 3! / 2! = 3, or the orders 1.0, 1.0, 2.0 and 1.0, 2.0, 1.0 and 2.0, 1.0, 1.0. Considering 1.0, 1.0, 2.0 and 2.0, 1.0, 1.0 is the same, we are left with 2 orders to consider or ceil(3/2) = 2.

Example input:

3 1.0 2.0 3.0

Considering the order 1.0 2.0 3.0 is the same as considering the order 3.0 2.0 1.0.

Hope this helps. Do look for test cases to this problem using the search option. There is one particular tricky one.

[chunyi81]

Ok. Now I am really stuck. In the given sample IO:

Sample input:

3
3 2.0 1.0 2.0
4 2.0 2.0 2.0 2.0
3 2.0 1.0 4.0

Sample output:
9.657
16.000
12.657

I can understand why outputs for the first two cases are 9.657 and 16.000.

But after reading the problem description many times, I couldn't understand why output for the third case is 12.657.

Because the total area of the three circles in the third case is: pi*2/2*2/2 + pi*1/2*1/2 + pi*4/2*4/2 = 5.25*pi where pi = 3.14159... and 5.25*pi > 12.657. But the size of the rectangular box required should be greater than the total area of the circles right? Then how come the output for the third case is 12.657? Could anyone explain please? Thanks for any help.

[chunyi81]

Finally found the problem. The input data is indeed the radii of the circles.

From the output description:

For each data line of input, excluding the first line of input containing n, your program must output the size of the smallest rectangle which can pack the circles. Each case should be output on a separate line by itself, with three places after the decimal point. Do not output leading zeroes unless the number is less than 1, e.g. 0.543.

The keyword is size, which I interpreted as the area of the rectangular box required, but the output given is the length of the box required. The output description is confusing and wrong and should be corrected.

[ImLazy]

Thank you, chunyi81. You have helped me many times.
I will try exhaustive search.