10217 - A Dinner with Schwarzenegger!!!

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

Moderator: Board moderators

20717TZ
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

Post by 20717TZ » Wed May 26, 2004 8:56 am

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

20717TZ
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

Post by 20717TZ » Wed May 26, 2004 9:02 am

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)=(1-p(1))*(2/N) to win, p(3)=(1-p(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).
my idea to clarify the problem compared with dumb dan's:
p(1)=1/N
p(2)=(1-P(1))*(1/N)
p(3)=(1-P(1)-P(2))*(2/N)
..

p(i)=(1-sum(p(1..i-1)))*(i-1)/N

am i right?
I Believe I Can - leestime.com

User avatar
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

Post by cytmike » Mon Jul 19, 2004 9:58 am

20717TZ wrote:
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)=(1-p(1))*(2/N) to win, p(3)=(1-p(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).
my idea to clarify the problem compared with dumb dan's:
p(1)=1/N
p(2)=(1-P(1))*(1/N)
p(3)=(1-P(1)-P(2))*(2/N)
..

p(i)=(1-sum(p(1..i-1)))*(i-1)/N

am i right?
Yes, you are right. But anybody can tell me how is the generalized forumla?
Impossible is Nothing.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sat Sep 25, 2004 10:49 am

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sat Sep 25, 2004 1:01 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 :lol:

Once you accepted the formula p(x) = (1 - sum(1, x-1)) * (x-1)/N, where sum(1, x-1) = p(1) + p(2) + .. p(x-1), you can rearrange:

sum(1, x-1) = 1 - p(x)*N/(x-1).

Now: p(x+1) = (1 - sum(1, x)) * x/N and since sum(1, x) = p(x) + sum(1, x-1), you can work out the recursive formula:

p(x+1) = p(x) * (N/(x-1) - 1) * x/N

Now comes a little "Manzoor Mathemagic":
As long as p(x+1) is increasing with increasing x, the multiplier (N/(x-1) - 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?

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sat Sep 25, 2004 3:35 pm

Thanks a lot little joey!!
You explanation is clear and easy to understand. :D
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 :lol:
I would say: Let's go ahead together :D Our target are Per and Adrain, right? :wink:
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.

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Thu Sep 30, 2004 1:07 pm

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

Also, one can note that you get the generalized formula:

p(x) = (N-1)! / (N-x)! * (x/(N^x))

And good luck catching up to Per and Adrian,
you will need it :wink:

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Sep 30, 2004 2:08 pm

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

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Fri Oct 01, 2004 4:30 am

:D
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 :wink: )
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.

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Post by cytmike » Fri Oct 01, 2004 6:27 pm

So that means every people compare with the ticket seller as well?
And then p(i)=(1-sum(p(1..i-1)))*i/N ?

So my previous idea is wrong?
Impossible is Nothing.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Fri Oct 01, 2004 6:59 pm

cytmike wrote:So that means every people compare with the ticket seller as well?
Yes, it is also written in the first post of this thread.
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.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Wed Mar 21, 2007 7:12 am

little joey wrote: So when will p(x+1) be at its maximum?
Thanks for the post, your trick is educating~!

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

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Wed Mar 21, 2007 9:23 pm

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) = ((N-1)/N) * (2/N), etc.

But if I do the mathemagic using these conditions I have to output x-1 and floor(x) to get AC, where p(x)=p(x+1), x>1 for sure since N>=30. But why output x-1? 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.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Wed Mar 21, 2007 9:23 pm

cleared, double posting.

Post Reply

Return to “Volume 102 (10200-10299)”