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

Moderator: Board moderators

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?

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
That's also my problem...
I think I must have some misunderstanding.

Could someone explain how the problem works like?

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
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.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
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.

Cezary Zukowski
New poster
Posts: 5
Joined: Tue Oct 12, 2004 1:42 am
Location: Poland
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

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
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
Thanks a lot for a nice explanation

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

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?

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 

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

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

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
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

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