shubhamgoyal__'s blog

Expectation value problem
By shubhamgoyal__, history, 8 years ago, In English

Can someone please help me out with this problem. https://www.codechef.com/TCFST13/problems/TCFST05 My aprroach: I was thinking of a dp approach..dp[i][0] would denote expectation value obtained from first i shots given we miss the ith shot...dp[i][1] is defined similarly but this time we hit the ith shot. dp[i][0]=dp[i-1][0]+dp[i-1][1]. dp[i][1]=p[i]*(1-p[i-1])+dp[i-2][0]+dp[i-2][1]+p[i]*p[i-1]*(1-p[i-2])*2*2+dp[i-3][0]+dp[i-3][1]+p[i]*p[i-1]*p[i-2]*(1-p[i-3])*3*3+dp[i-4][0]+dp[i-4][1]...so on.. I am not able to figure out how to calculate dp[i][1] in O(n) time.. Please Help.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Here is my approach that follows the above dp.

We have to precalculate stuff in O(n) to solve this problem fast.

Denote sum[i] = dp[i][0] + dp[i][1]. Then we have the following two recursions.

dp[i][0] = (1 - p[i])·sum[i - 1]
dp[i][1] = p[i]·(1 - p[i - 1])·(1 + sum[i - 2]) + p[i]·p[i - 1]·(1 - p[i - 2])·(4 + sum[i - 3]) + ...

It is easy to keep up with $dp[i][0]$. The real problem is dp[i][1].

Let us break the sum into two parts

(p[i] - p[i - 1])·sum[i - 2] + (p[i]p[i - 1] - p[i]p[i - 1]p[i - 2])·sum[i - 3] + ...

and

p[i] + 3p[i]p[i - 1] + 5p[i]p[i - 1]p[i - 2] + ...

Let us look at the second sum first. Denote that sum as $sprec[i]$

Also, denote fprec[i] = p[i] + p[i]p[i - 1] + p[i]p[i - 1]p[i - 2] + ....

It is easy to see that fprec[i] = p[i](1 + fprec[i - 1]) and sprec[i] = p[i] * sprec[i - 1] + 2fprec[i] - p[i].

Now we have to deal with the first sum. Denote that sum as prec[i].

It is also quite easy to see that prec[i + 2] = p[i + 2] * prec[i + 1] + (p[i + 2] - p[i + 1]p[i + 2])sum[i].

This gives us a way to solve the problem, since dp[i][1] = prec[i] + sprec[i]

→ Reply