10012 - How Big Is It?

[serur]

<cut> - see other posts about 10012 - the crux is - the circles may overlap

[Moha]

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]

my program produces exactly the same output (with the indicated corrections) and it get WA!

could anymore post more test I/O please!

thx

[epsilon0]

changing my floats to doubles solved it!! if anyone has the same pb, take this hint!

nice problem.

[Zaspire]

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*/

[Zaspire]

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]

hello everyone
would you give me some more correct test cases so I can find my program problem?

[zobayer]

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.

[nixe]

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[8];
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[8];
	for (int i = 0; i < 8; i++)
	{
		poradi[i] = order[i]-'0';
	}
	float partial_dist[8]; //stores distancies from the left side of the box up to the ith circle center   
	float centers[8]; 	//stores "coordinate" of the centers
	
	float size = 2*circles[poradi[0]];
	
	centers[0] = circles[poradi[0]];
	partial_dist[0] = circles[poradi[0]];
	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]

If you did passed the about test cases, have you tried to use double instead of float to prevent the precision errors?

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[8];
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[8];
	for (int i = 0; i < 8; i++)
	{
		poradi[i] = order[i]-'0';
	}
	float partial_dist[8]; //stores distancies from the left side of the box up to the ith circle center   
	float centers[8]; 	//stores "coordinate" of the centers
	
	float size = 2*circles[poradi[0]];
	
	centers[0] = circles[poradi[0]];
	partial_dist[0] = circles[poradi[0]];
	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);
	}
	
} 

[Silvie]

thanks it helped

[brianfry713]

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