10167 - Birthday Cake

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

Moderator: Board moderators

benetin
New poster
Posts: 2
Joined: Thu Feb 13, 2003 11:36 pm

10167 - Birthday Cake

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

SDiZ
New poster
Posts: 13
Joined: Fri Aug 05, 2005 12:20 pm
Location: Hong Kong
Contact:

10167 Birthday Cake

Post by SDiZ »

I got WA..
any one have good test case for this question?

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon »

Hi,

Try not to use doubles.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon »

Hi,

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

cpphamza
New poster
Posts: 18
Joined: Sat Sep 09, 2006 12:55 pm

Post by cpphamza »

Can anyone explain how to solve this problem?

Thanks alot

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

I did it by trying random lines.

cpphamza
New poster
Posts: 18
Joined: Sat Sep 09, 2006 12:55 pm

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

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post 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.

cpphamza
New poster
Posts: 18
Joined: Sat Sep 09, 2006 12:55 pm

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

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post 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.

cpphamza
New poster
Posts: 18
Joined: Sat Sep 09, 2006 12:55 pm

Post 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

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 10167 - Birthday Cake

Post 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.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

amacfie
New poster
Posts: 2
Joined: Tue Dec 23, 2008 3:36 am

Re: 10167 - Birthday Cake

Post by amacfie »

why is randomized faster than linear iteration?

JINX
New poster
Posts: 3
Joined: Sat Jul 19, 2008 3:36 pm

Re: 10167 - Birthday Cake

Post 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;
}

diego_engcomp
New poster
Posts: 9
Joined: Sat Jul 18, 2009 1:18 am

Re: 10167 - Birthday Cake

Post 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.

Post Reply

Return to “Volume 101 (10100-10199)”