10217  A Dinner with Schwarzenegger!!!
Moderator: Board moderators

 New poster
 Posts: 33
 Joined: Tue Apr 27, 2004 7:41 pm
 Location: Santa Clara / Mountain View, CA, USA
 Contact:
I am always hating this type of problems which express thems
I am always hating this type of problems which express themselves undefined (You just don't know what the problem means until .......). 10217 is the typist one of this type.
I Believe I Can  leestime.com

 New poster
 Posts: 33
 Joined: Tue Apr 27, 2004 7:41 pm
 Location: Santa Clara / Mountain View, CA, USA
 Contact:
my idea to clarify the problem compared with dumb dan's
my idea to clarify the problem compared with dumb dan's:To clarify the problem:
Exactly one person in the ticket queue will win. A person will win if no person in front of him has won AND his/her birthday is the same as ANY one of the people in front of him.
So if there are N days in the year the first person will have a probability p(1)=1/N to win, second person will have probability p(2)=(1p(1))*(2/N) to win, p(3)=(1p(1)p(2))*(3/N) and so on... and you need to find the highest p(x). (Just calculating the values for p will obviously lead to rounding errors for large N, hence the problem).
p(1)=1/N
p(2)=(1P(1))*(1/N)
p(3)=(1P(1)P(2))*(2/N)
..
p(i)=(1sum(p(1..i1)))*(i1)/N
am i right?
I Believe I Can  leestime.com
 cytmike
 Learning poster
 Posts: 95
 Joined: Mon Apr 26, 2004 1:23 pm
 Location: Hong Kong and United States
 Contact:
Re: my idea to clarify the problem compared with dumb dan's
Yes, you are right. But anybody can tell me how is the generalized forumla?20717TZ wrote:my idea to clarify the problem compared with dumb dan's:To clarify the problem:
Exactly one person in the ticket queue will win. A person will win if no person in front of him has won AND his/her birthday is the same as ANY one of the people in front of him.
So if there are N days in the year the first person will have a probability p(1)=1/N to win, second person will have probability p(2)=(1p(1))*(2/N) to win, p(3)=(1p(1)p(2))*(3/N) and so on... and you need to find the highest p(x). (Just calculating the values for p will obviously lead to rounding errors for large N, hence the problem).
p(1)=1/N
p(2)=(1P(1))*(1/N)
p(3)=(1P(1)P(2))*(2/N)
..
p(i)=(1sum(p(1..i1)))*(i1)/N
am i right?
Impossible is Nothing.
It is so sad that no one give help since I ask for hint half year ago.
This problem confuses me for long time. Actually I have a few copies of other's AC code, but I think it is meaningless to get AC by sending some code that I don't understand the logic.
This problem may be trivial to the people who solved it, but it also confuse many people, as you see there are other people requesting for hint. So, please, anyone who get AC, tell me how to generalize the formula to floating point position. Thanks!
This problem confuses me for long time. Actually I have a few copies of other's AC code, but I think it is meaningless to get AC by sending some code that I don't understand the logic.
This problem may be trivial to the people who solved it, but it also confuse many people, as you see there are other people requesting for hint. So, please, anyone who get AC, tell me how to generalize the formula to floating point position. Thanks!
My signature:
 Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.  I HATE testing account.
 Don't send me source code for debug.
 little joey
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Well, I shouldn't be doing this, since you're still a couple of problems ahead of me , but hey, I'm not a bad guy
Once you accepted the formula p(x) = (1  sum(1, x1)) * (x1)/N, where sum(1, x1) = p(1) + p(2) + .. p(x1), you can rearrange:
sum(1, x1) = 1  p(x)*N/(x1).
Now: p(x+1) = (1  sum(1, x)) * x/N and since sum(1, x) = p(x) + sum(1, x1), you can work out the recursive formula:
p(x+1) = p(x) * (N/(x1)  1) * x/N
Now comes a little "Manzoor Mathemagic":
As long as p(x+1) is increasing with increasing x, the multiplier (N/(x1)  1) * x/N will be greater than 1, but as soon as p(x+1) starts decreasing, this multiplier will be smaller than 1.
So when will p(x+1) be at its maximum?
Once you accepted the formula p(x) = (1  sum(1, x1)) * (x1)/N, where sum(1, x1) = p(1) + p(2) + .. p(x1), you can rearrange:
sum(1, x1) = 1  p(x)*N/(x1).
Now: p(x+1) = (1  sum(1, x)) * x/N and since sum(1, x) = p(x) + sum(1, x1), you can work out the recursive formula:
p(x+1) = p(x) * (N/(x1)  1) * x/N
Now comes a little "Manzoor Mathemagic":
As long as p(x+1) is increasing with increasing x, the multiplier (N/(x1)  1) * x/N will be greater than 1, but as soon as p(x+1) starts decreasing, this multiplier will be smaller than 1.
So when will p(x+1) be at its maximum?
Thanks a lot little joey!!
You explanation is clear and easy to understand.
You explanation is clear and easy to understand.
I would say: Let's go ahead together Our target are Per and Adrain, right?little joey wrote:Well, I shouldn't be doing this, since you're still a couple of problems ahead of me , but hey, I'm not a bad guy
My signature:
 Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.  I HATE testing account.
 Don't send me source code for debug.
 little joey
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
You're right. I could say I left that 'typo' in on purpose to prevent people from dumbly copying a formula (sorry dan, name pun intentional, no offense meant), but I must admit I just made a silly mistake...dumb dan wrote:While little joey is correct I'd just like to correct a little typo of his. It's supposed to be:
p(x+1) = p(x) * (N/x  1) * (x+1)/N
I just have a quick look on your post and then start doing everything again myself. So I haven't found that you have leave a trap for me (just kidding )
My signature:
 Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.  I HATE testing account.
 Don't send me source code for debug.
Yes, it is also written in the first post of this thread.cytmike wrote:So that means every people compare with the ticket seller as well?
My signature:
 Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.  I HATE testing account.
 Don't send me source code for debug.
Thanks for the post, your trick is educating~!little joey wrote: So when will p(x+1) be at its maximum?
p(x+1) = p(x) * (N/x  1) * (x+1)/N,
I am guessing that you were looking for the asnwer to be when
(N/x  1) * (x+1)/N = 1, p(x+1) is maximized??
When if that is true, then p(x) = p(x+1) is just as big, would it not be the case that something in between x and x+1 have even bigger probability? But if that is so, how to we find it with the given formula?
And, since p(x) = p(x+1), then why should we output x and not x+1?
May me I am just totally confused??
If someone's birthday matches the birthday of a person who has bought ticket before him, he (the one who bought ticket later) will be given the honor to have dinner with Schwarzenegger. To give the guy at the front of the queue some chance, his birthday will be compared with the ticket seller's birthday.
I think it is quite clearly stated that the seller's birthday is only compared to the first person's birthday.
So, p(1) = 1/N, p(2) = 1/N, p(3) = ((N1)/N) * (2/N), etc.
But if I do the mathemagic using these conditions I have to output x1 and floor(x) to get AC, where p(x)=p(x+1), x>1 for sure since N>=30. But why output x1? The answer, by intuition, should lay in between x and x+1. Right?
Last edited by yiuyuho on Wed Mar 21, 2007 9:26 pm, edited 4 times in total.