## 10012 - How Big Is It?

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

### 10012- How Big it is, forsooth?!

<cut> - see other posts about 10012 - the crux is - the circles may overlap
Last edited by serur on Mon Jun 21, 2010 4:48 pm, edited 2 times in total.
Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
For this problem, I don't think you have a precision error. You should backtrack on circles. and compute the total length.
About precision error, Oh no, but you can avoid them just with your experences.
epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.
my program produces exactly the same output (with the indicated corrections) and it get WA! could anymore post more test I/O please!

thx
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli
epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.
changing my floats to doubles solved it!! if anyone has the same pb, take this hint!

nice problem.
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli
Zaspire
New poster
Posts: 36
Joined: Sun Apr 23, 2006 2:42 pm
Location: Russia

### 10012

I read all post before, and i pass all test. But WA. WHY? Help please!

Code: Select all

``````/* CUT*/

#define delta(x,y) sqrt((rad[x]+rad[y])*(rad[x]+rad[y])-abs(rad[x]-rad[y])*abs(rad[x]-rad[y]))

/*CUT*/
``````
Last edited by Zaspire on Fri Nov 03, 2006 12:19 pm, edited 1 time in total.
Zaspire
New poster
Posts: 36
Joined: Sun Apr 23, 2006 2:42 pm
Location: Russia
I only correct my formula to simply one and get AC.

Code: Select all

``````#define delta(x,y) 2*sqrt(rad[x]*rad[y])
``````
Why with prev I got WA?????
m_fantastic
New poster
Posts: 1
Joined: Sun May 30, 2010 11:06 pm

### Re: 10012 - How Big Is It?

hello everyone
would you give me some more correct test cases so I can find my program problem?
zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

### Re: 10012 - How Big Is It?

I have got a few WA for a strange reason, obviously related to precision issues and I am kind of worried about that.
The problem was, I used next_permutation on the radii array which gave me 3-4 WA, when I checked closely (after being unable to find my bug in logic) I found huge precision error even at 3rd decimal place. Then, just to check, I used an integer index array, and used next_permutation over that, this time, everything gone ok, and I got AC.

Finally, array size 8 is sufficient, as one of the users previously told, he got WA at n = 8 but got AC at n = 10, he had some other problem I don't know what.

Cool problem, this time language made it harder. I knew about precision errors and I know how to handle them, but an error at this scale is really un-expect-able, gcc/g++ is lagging behind day by day.
You should not always say what you know, but you should always know what you say.
nixe
New poster
Posts: 1
Joined: Mon Oct 24, 2011 2:27 am

### Re: 10012 - How Big Is It?

Hey guy. Topic looks dead, but i had no idea, whether i can find another big enough community about UVa.
If you by any chance have some time, could you look at my code, please?
I'm lost. I'm using the right algorithm (I guess), and I got right answer for more than 100 different outputs. I really have no idea, what's wrong with my solution. Code: Select all

``````#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>

using namespace std;

float circles;
float smallest;

void swap (char *x, char *y)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
}

float get_size_of_box(char *order, int N)
{
int poradi;
for (int i = 0; i < 8; i++)
{
poradi[i] = order[i]-'0';
}
float partial_dist; //stores distancies from the left side of the box up to the ith circle center
float centers; 	//stores "coordinate" of the centers

float size = 2*circles[poradi];

centers = circles[poradi];
partial_dist = circles[poradi];
float max_par_dist;
float aux_dist;

for (int i  = 1; i < N; i++)
{
max_par_dist=0;
for (int j = 0; j < i; j++)
{
aux_dist = 2*sqrt(circles[poradi[j]]*circles[poradi[i]]);
if ((max_par_dist < (partial_dist[j]+aux_dist)) )
{
max_par_dist =  partial_dist[j]+aux_dist;
}									//tim overime, ze se skutecne dotyka jen predposledniho
}
partial_dist[i] = max_par_dist;

//ale muze nastat pripad, kdy je kulicka dosti mala
if (partial_dist[i] < circles[poradi[i]])
partial_dist[i] = circles[poradi[i]];
if ((partial_dist[i]+circles[poradi[i]])> size)
size = partial_dist[i]+circles[poradi[i]];
}
return size;
}

void permute(char *a, int i, int n)
{
int j;
if (i == n)
{
float size = get_size_of_box(a, n+1);
if (size < smallest)
smallest = size;
}
else
{
for (j = i; j <= n; j++)
{
swap((a+i), (a+j));
permute(a, i+1, n);
swap((a+i), (a+j)); //backtrack
}
}
}

int main ()
{
int cases;
scanf("%d\n", &cases);
char order[] = {'0', '1', '2', '3', '4', '5', '6', '7'};
while (cases)
{
cases--;
int N;
scanf("%d", &N);
for (int i = 0; i < N; i++)
scanf(" %f", &circles[i]);
getchar(); //end of line

smallest = get_size_of_box(order, N);
permute (order, 0, (N-1));

printf("%.3f\n", smallest);
}

}

``````
DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

### Re: 10012 - How Big Is It?

If you did passed the about test cases, have you tried to use double instead of float to prevent the precision errors?
nixe wrote:Hey guy. Topic looks dead, but i had no idea, whether i can find another big enough community about UVa.
If you by any chance have some time, could you look at my code, please?
I'm lost. I'm using the right algorithm (I guess), and I got right answer for more than 100 different outputs. I really have no idea, what's wrong with my solution. Code: Select all

``````#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>

using namespace std;

float circles;
float smallest;

void swap (char *x, char *y)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
}

float get_size_of_box(char *order, int N)
{
int poradi;
for (int i = 0; i < 8; i++)
{
poradi[i] = order[i]-'0';
}
float partial_dist; //stores distancies from the left side of the box up to the ith circle center
float centers; 	//stores "coordinate" of the centers

float size = 2*circles[poradi];

centers = circles[poradi];
partial_dist = circles[poradi];
float max_par_dist;
float aux_dist;

for (int i  = 1; i < N; i++)
{
max_par_dist=0;
for (int j = 0; j < i; j++)
{
aux_dist = 2*sqrt(circles[poradi[j]]*circles[poradi[i]]);
if ((max_par_dist < (partial_dist[j]+aux_dist)) )
{
max_par_dist =  partial_dist[j]+aux_dist;
}									//tim overime, ze se skutecne dotyka jen predposledniho
}
partial_dist[i] = max_par_dist;

//ale muze nastat pripad, kdy je kulicka dosti mala
if (partial_dist[i] < circles[poradi[i]])
partial_dist[i] = circles[poradi[i]];
if ((partial_dist[i]+circles[poradi[i]])> size)
size = partial_dist[i]+circles[poradi[i]];
}
return size;
}

void permute(char *a, int i, int n)
{
int j;
if (i == n)
{
float size = get_size_of_box(a, n+1);
if (size < smallest)
smallest = size;
}
else
{
for (j = i; j <= n; j++)
{
swap((a+i), (a+j));
permute(a, i+1, n);
swap((a+i), (a+j)); //backtrack
}
}
}

int main ()
{
int cases;
scanf("%d\n", &cases);
char order[] = {'0', '1', '2', '3', '4', '5', '6', '7'};
while (cases)
{
cases--;
int N;
scanf("%d", &N);
for (int i = 0; i < N; i++)
scanf(" %f", &circles[i]);
getchar(); //end of line

smallest = get_size_of_box(order, N);
permute (order, 0, (N-1));

printf("%.3f\n", smallest);
}

}

``````
Have you ever...
• Wanted to work at best companies?
• Struggled with interview problems that could be solved in 15 minutes?
• Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.
Silvie
New poster
Posts: 1
Joined: Thu Oct 23, 2014 10:26 am

### Re: 10012 - How Big Is It?

thanks it helped
Last edited by Silvie on Fri Oct 24, 2014 1:31 pm, edited 1 time in total.
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10012 - How Big Is It?

Code: Select all

``````middle at 0.306, radius 0.306
middle at 1.908, radius 1.908
middle at 5.048, radius 1.292
middle at 8.710, radius 2.595
middle at 11.119, radius 0.559
maxright = 11.678

middle at 0.306, radius 0.306
middle at 1.908, radius 1.908
middle at 3.973, radius 0.559
middle at 6.382, radius 2.595
middle at 10.044, radius 1.292
maxright = 11.336

middle at 1.908, radius 1.908
middle at 3.973, radius 0.559
middle at 6.382, radius 2.595
middle at 8.165, radius 0.306
middle at 10.044, radius 1.292
maxright = 11.336
``````
Check input and AC output for thousands of problems on uDebug!