Page 1 of 2

10167 - Birthday Cake

Posted: Tue Feb 18, 2003 8:42 am
by benetin
--- Note: the coordinate of a cherry (x , y) are two integers. You must give the line as form two integers A,B(stands for Ax+By=0) each number mustn't in [-500,500].

What does that mean by "mustn't in[-500,500]", while the sample output is 0,1??

10167 Birthday Cake

Posted: Fri Aug 05, 2005 12:22 pm
by SDiZ
I got WA..
any one have good test case for this question?

Posted: Sat Aug 19, 2006 3:37 pm
by daveon
Hi,

Try not to use doubles.

Posted: Sat Aug 19, 2006 3:38 pm
by daveon
Hi,

It actually means, A and B are between -500 and 500 inclusive.

Posted: Thu Oct 19, 2006 11:07 pm
by cpphamza
Can anyone explain how to solve this problem?

Thanks alot

Posted: Thu Oct 19, 2006 11:22 pm
by Darko
I did it by trying random lines.

Posted: Fri Oct 20, 2006 4:37 pm
by cpphamza
do you mean you randomly choose A then randomly choose B and check if the same number of points lie on each of the line sides?

I think this problem has some mathematical approach (looking at the very small times it has been solved in), any ideas?

Posted: Fri Oct 20, 2006 5:13 pm
by Darko
Yes, that's what I mean.

I was thinking about sorting them by angle and go looking for a line that splits them in two - but it sounded too complicated, so I tried random. And it worked (there are only 50 points on a 1000x1000 grid). My time is 0.014 in Java.

Posted: Fri Oct 20, 2006 9:21 pm
by cpphamza
Well I've tried the random approach as follows:

while(true){
-randomly generate A, B. That is O(1)
-divide the points in two sets where each set lies in one side of the line Ax+BY=0. That is O(n)
-if both sets has the same size break
}

However the soltion also times out! do you make any further enhancements?

Posted: Fri Oct 20, 2006 9:58 pm
by Darko
That's exactly what I do.
I am using integers and built-in random function. How do you look for random numbers? And are they in the right range, [-500,500]?
Btw, that "if both sets same size, break" part is wrong, should be "if both sets are of size n, break". Just check that you really break.

Posted: Fri Oct 20, 2006 10:25 pm
by cpphamza
Got AC using your random approach (I had a bug in intializing an array :oops: ).
Btw, that "if both sets same size, break" part is wrong, should be "if both sets are of size n, break". Just check that you really break.
Funny thing I got AC using my wrong condition, I think there wasn't a testcase for that!

I still can't imagine that a problem setter intended such a solution for the problem

Re: 10167 - Birthday Cake

Posted: Wed May 07, 2008 5:01 am
by andmej
I solved this using a Divide-and-conquer approach. I got the idea from problem 10077 - The Stern-Brocot number system. However, a brute force algorithm will also run on time.

Re: 10167 - Birthday Cake

Posted: Tue Jan 06, 2009 2:00 am
by amacfie
why is randomized faster than linear iteration?

Re: 10167 - Birthday Cake

Posted: Sun Aug 23, 2009 3:28 pm
by JINX
Here is my code that uses the random method, but it is slow and cann't get an AC.
Needs some help.
Thanks.

Code: Select all

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int N;

struct Point
{
	int x,y;
};

Point p[100];

void Process()
{
	int A,B;
	 srand ( time(NULL) );
	while (true)
	{
		A = rand()*1000/RAND_MAX-500;
		B = rand()*500/RAND_MAX;
		//cout<<A<<' '<<B<<endl;
		int count1 = 0;
		int count2 = 0;
		for (int i=0;i<2*N;i++)
		{
			if (A*p[i].x+B*p[i].y>0)
			{
				count1++;
			}
// 			else if(A*p[i].x+B*p[i].y<0)
// 			{
// 				count2 ++;
// 			}
		}
		if (count1*2==N)
		{
			break;
		}
	}
	cout<<A<<' '<<B<<endl;
}

int main()
{
	cin>>N;
	while (N)
	{
		for (int i=0;i<N*2;i++)
		{
			cin>>p[i].x>>p[i].y;
		}
		Process();
		cin>>N;
	}
	return 0;
}

Re: 10167 - Birthday Cake

Posted: Thu Dec 17, 2009 3:42 pm
by diego_engcomp
JINX, I used the same ideia than you and got AC. I'm not sure if your way to generate the random numbers is correct. I think a more easy way is:

Code: Select all

a=-500+(rand()%1001);
b=-500+(rand()%1001);
And I think that the break condition should be:

Code: Select all

if(count1==n && count2==n)
     break;
I hope it helps. Sorry for my english.