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?!

Post by serur » Tue Mar 28, 2006 9:23 pm

<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:

Post by Moha » Mon Apr 10, 2006 6:36 pm

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.

Post by epsilon0 » Sat Jul 08, 2006 7:34 pm

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.

Post by epsilon0 » Sat Jul 08, 2006 8:45 pm

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

User avatar
Zaspire
New poster
Posts: 36
Joined: Sun Apr 23, 2006 2:42 pm
Location: Russia

10012

Post by Zaspire » Thu Nov 02, 2006 10:46 pm

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.

User avatar
Zaspire
New poster
Posts: 36
Joined: Sun Apr 23, 2006 2:42 pm
Location: Russia

Post by Zaspire » Fri Nov 03, 2006 12:17 pm

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?

Post by m_fantastic » Sun May 30, 2010 11:13 pm

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?

Post by zobayer » Mon Nov 15, 2010 8:04 pm

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?

Post by nixe » Mon Oct 24, 2011 10:11 am

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
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10012 - How Big Is It?

Post by DD » Tue Feb 19, 2013 5:16 am

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[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);
	}
	
} 

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?

Post by Silvie » Thu Oct 23, 2014 10:40 am

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?

Post by brianfry713 » Thu Oct 23, 2014 11:04 pm

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!

Post Reply

Return to “Volume 100 (10000-10099)”