### shubhamgoyal__'s blog

By shubhamgoyal__, history, 6 years ago,

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.

• 0

 » 6 years ago, # |   +3 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]
•  » » 6 years ago, # ^ |   0 Thanks for your explanation...I had even got my recurrences wrong!!