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
).
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:
I hope it helps. Sorry for my english.