10900 - So you want to be a 2n-aire?

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

Moderator: Board moderators

Post Reply
Cezary Zukowski
New poster
Posts: 5
Joined: Tue Oct 12, 2004 1:42 am
Location: Poland

10900 - So you want to be a 2n-aire?

Post by Cezary Zukowski » Thu Sep 22, 2005 10:54 pm

I am weak in probability calculus and can't see the solution.

So, what theory should we know to solve it ???

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan

Post by polone » Tue Sep 27, 2005 2:10 pm

That's also my problem...
I think I must have some misunderstanding. :cry:

Could someone explain how the problem works like?

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac » Tue Sep 27, 2005 2:21 pm

Once you know p, your expected winning if you answer the question is p*e where e is the expected winning for this question and all questions beyond.
You have to compute this recursively (or simply backwards, as the recursion is trivial).

If you don't know p, you have to figure out for what fraction of possible p, you will choose to answer the question, and for what fraction you will not. Compute the expected earning for each case, and take the weighted average.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Tue Sep 27, 2005 8:05 pm

Anonymous wrote:You have written p >= 0.5 and p >= 0.2. But, how to access the p value?? And, how p depends on t value??
Lets say that f(n,a) is the player's expected prize after n questions starting with a prize of a. For n=0 is f(0,a)=a. For bigger n you can get a straightforward (but ugly) recurrence. Think about it before reading the spoiler bellow! By simplifying it you can get a nice solution.

WARNING, a spoiler ahead!
Image

Cezary Zukowski
New poster
Posts: 5
Joined: Tue Oct 12, 2004 1:42 am
Location: Poland

Post by Cezary Zukowski » Wed Sep 28, 2005 7:20 pm

Thanks for formula. I simplified it and got AC.

I have programmed a solution but i still don't understand the formula. I think, I should read something about probability calculus. Could you recommend some readings?

Is this formula from a book? What sort of probability is it?? I would like to know in order to solve similar tasks in next competitions :-)

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Thu Sep 29, 2005 8:50 pm

Cezary Zukowski wrote:Thanks for formula. I simplified it and got AC.

I have programmed a solution but i still don't understand the formula. I think, I should read something about probability calculus. Could you recommend some readings?

Is this formula from a book? What sort of probability is it?? I would like to know in order to solve similar tasks in next competitions :-)
Let's have n (n>0) questions left with a starting prize of a. We are going to compute f(n,a). Suppose the probability of the correct answer to the first question is p (t<=p<=1). After answering the question the prize changes to f(n-1,2*a) with probability p and to 0 with probability 1-p. So the expected prize after this question is p*f(n-1,2*a)+(1-p)*0=p*f(n-1,2*a). If this prize is less than a the player will choose not to answer and to quit the game keeping the prize of a. Therefore, getting a question with probability of the correct answer equal to p the expected prize is max(a,p*f(n-1,2*a)).

As the probability of the correct answer to the question is uniformly distributed over the range [t,1] the average expected prize the player can quit with is 1/(t-1) * \int_t^1 max(a,p*f(n-1,2*a)) dp.
Last edited by Martin Macko on Fri Sep 30, 2005 10:06 am, edited 2 times in total.

Cezary Zukowski
New poster
Posts: 5
Joined: Tue Oct 12, 2004 1:42 am
Location: Poland

Post by Cezary Zukowski » Thu Sep 29, 2005 9:37 pm

Thanks a lot for a nice explanation :)

hellgod
New poster
Posts: 1
Joined: Fri Oct 21, 2005 9:53 am

Post by hellgod » Fri Nov 11, 2005 9:23 pm

I have a question about this problem. could somebody answer me,please?

n=1 ,t=0.3

f(1,1)=1.357 = (1.25-t)/(1-t)

and what's the answer of n=2 ,t=0.3 ?

I think that f(2,1) is ((1.25-t)/(1-t))^2 ,but I am wrong.

can somebody answer me ? thx

Yumin
New poster
Posts: 3
Joined: Sun Jun 26, 2005 6:57 pm

10900 - So you want to be a 2n-aire?

Post by Yumin » Mon Nov 14, 2005 4:50 pm

I've tested those sample I/Os from http://acm.uva.es/p/v109/10900.html,
and the results are ok.
Someone can give me some I/Os ? thanks!

Code: Select all

 Input                  My output
n=10  t=0.6         109.951
n=25  t=0.2         109.514
n=30  t=1           1073741824.000
n=30  t=0           0.000
n=30  t=0.99        923830472.267
n=2   t=1           4.000 

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10900 - So you want to be a 2&n-aire? I need sample

Post by Martin Macko » Sat Dec 10, 2005 9:15 pm

Yumin wrote:I've tested those sample I/Os from http://acm.uva.es/p/v109/10900.html,
and the results are ok.
Someone can give me some I/Os ? thanks!

Code: Select all

 Input                  My output
n=10  t=0.6         109.951
n=25  t=0.2         109.514
n=30  t=1           1073741824.000
n=30  t=0           0.000
n=30  t=0.99        923830472.267
n=2   t=1           4.000 
My AC's output:

Code: Select all

109.951
109.514
1073741824.000
4.045
923830491.567
4.000

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sat Dec 10, 2005 9:23 pm

hellgod wrote:n=1 ,t=0.3
1.357
hellgod wrote:n=2 ,t=0.3
1.773

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

Post by Darko » Fri Feb 03, 2006 9:50 am

Ok, every time I read this thread my brain tries to pop out of my head.

I really don't know probability and these kinds of problems are just shortening the life of my keyboard (well, mine too).

I have zillion questions, but the first one would be - what is the "best strategy"? And another - how does one calculate the "weighted average"?

I really tried to understand above posts, but I don't get it :(

What I did was - we have a uniform probability - expected value for p is (t+1)/2. OK, so far. Expected prize after n questions - (2*p)^n. Alright , it works... but not if t < 0.5. That's when the "best strategy" comes into play. And I have no idea what to do with it.

Can someone simplify it a bit for me? Dumb it down?

I guess I have to add that part above the triangle for t<0.5 on that diagram, but I have no idea how to do it. Or better yet - I don't know the meaning of it (well, I guess that's when you decide to stop answering questions, but I think that if p<0.5 you wouldn't even answer the first question, would you?)

Darko

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Fri Feb 10, 2006 9:46 pm

Darko: Try reading my explanation at the Algorithmist: http://www.algorithmist.com/index.php/UVa_10900

(I admit that it was written according to Martin Macko's post, but I tried to simplify it and be more verbose.)

If this doesn't help, you really should get a better background in calculus and probability theory.

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

Post by Darko » Tue Aug 29, 2006 1:51 am

I kept coming to this thread every couple of months, not getting anything (reminded me of Bart Simpson) until, suddenly, it was just so obvious.

Learning by epiphany? :)

Anyway, that graph on the previous page represents the solution in the best way (IMO). Using notation from Algorithmist, replace 2 by f(k-1) and 1 by 2^(n-k). And replace 0.3 by t. Then, for every k, f(k) is the area under two lines - 2^(n-k) and p*f(k-1), where p is in (t,1). Picture shows the case when they intersect in (t,1) but they might intersect to the left of t, deal with those two cases separately.

You can use calculus to find the area, or just do it the "old fashioned" way - just keep in mind that the probability of any of the values in (t,1) is 1/(1-t).

P.S. there are a few typos on Algorithmist, including the one in the image - should be 1/(1-t) instead of 1/(t-1).

Post Reply

Return to “Volume 109 (10900-10999)”