### 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] would denote expectation value obtained from first i shots given we miss the ith shot...dp[i] is defined similarly but this time we hit the ith shot. dp[i]=dp[i-1]+dp[i-1]. dp[i]=p[i]*(1-p[i-1])+dp[i-2]+dp[i-2]+p[i]*p[i-1]*(1-p[i-2])*2*2+dp[i-3]+dp[i-3]+p[i]*p[i-1]*p[i-2]*(1-p[i-3])*3*3+dp[i-4]+dp[i-4]...so on.. I am not able to figure out how to calculate dp[i] in O(n) time.. Please Help. Comments (2)
 » 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] + dp[i]. Then we have the following two recursions. dp[i] = (1 - p[i])·sum[i - 1] dp[i] = 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]$. The real problem is dp[i]. 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] = prec[i] + sprec[i]
•  » » Thanks for your explanation...I had even got my recurrences wrong!!