10900  So you want to be a 2naire?
Moderator: Board moderators

 New poster
 Posts: 5
 Joined: Tue Oct 12, 2004 1:42 am
 Location: Poland
10900  So you want to be a 2naire?
I am weak in probability calculus and can't see the solution.
So, what theory should we know to solve it ???
So, what theory should we know to solve it ???
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.
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.

 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
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.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??
WARNING, a spoiler ahead!

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

 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
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(n1,2*a) with probability p and to 0 with probability 1p. So the expected prize after this question is p*f(n1,2*a)+(1p)*0=p*f(n1,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(n1,2*a)).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
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/(t1) * \int_t^1 max(a,p*f(n1,2*a)) dp.
Last edited by Martin Macko on Fri Sep 30, 2005 10:06 am, edited 2 times in total.

 New poster
 Posts: 5
 Joined: Tue Oct 12, 2004 1:42 am
 Location: Poland
10900  So you want to be a 2naire?
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!
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

 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&naire? I need sample
My AC's output: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
Code: Select all
109.951
109.514
1073741824.000
4.045
923830491.567
4.000

 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
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
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
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.
(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.
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(k1) and 1 by 2^(nk). And replace 0.3 by t. Then, for every k, f(k) is the area under two lines  2^(nk) and p*f(k1), 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/(1t).
P.S. there are a few typos on Algorithmist, including the one in the image  should be 1/(1t) instead of 1/(t1).
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(k1) and 1 by 2^(nk). And replace 0.3 by t. Then, for every k, f(k) is the area under two lines  2^(nk) and p*f(k1), 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/(1t).
P.S. there are a few typos on Algorithmist, including the one in the image  should be 1/(1t) instead of 1/(t1).