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.
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.
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
and
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]
Thanks for your explanation...I had even got my recurrences wrong!!