OJ Board

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.

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.

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.