Problem A from Waterloo ACM Sept 17/2005

[gubd]

Hi,

I'm trying to understand the solution to problem A of the Waterloo Sept17/2005 contest:

Problem statement is here:

http://plg.uwaterloo.ca/~acm00/050917/A.html

My (very wrong) attempt was to

- first calculate the expected value of the probability that he would answer a question correctly (since this probability is uniformly distributed between t..1, the expected probability is (1+t)/2.) Call this p_expected.

- Then, for a given strategy (i.e., don't give up before answering question k), the expected value would be 2^k * p_expected^k. (multiplied p_expected with itself k times since I was treating answering each contest question that lead up to question k as an independent trial.)

Can anyone provide a pseudo-code explanation, deriving any formulas required from basic definitions of expected value?

I know there are solutions available here:

http://plg.uwaterloo.ca/~acm00/050917/data

but I found them fairly cryptic.

Thanks.

[gvcormac]

For each question, there's a threshold probability T such that if p >= T you should answer the question; otherwise not. If T <= t, you will always answer the question. If t < T < 1 the proportion of times that you answer the question will be (1-T)/(1-t). The overall expected winning is the sum of the proportion for each case multiplied by the expected winning for the case.

[Quantris]

Just to add on to what gvcormac said, if you read the statement carefully you will see that the player knows the probability p of answering a question correctly after seeing the question - therefore his optimal strategy can use the specific value of p (comparing to the threshold for positive expectation) in deciding if/when to stop answering questions.