PROBLEM LINKSDIFFICULTYEASY PREREQUISITESSimple Math, Dynamic Programming PROBLEMShiro has to pass through N levels to save the princess. Levels are labeled from 1 to N. At each level he encounters flags, which he always picks up. At level i there are A_{i} flags.
What is the probability that when Shiro has crossed all the levels, he has picked up at least as many Abra flags as Kadabra flags. EXPLANATIONLet the total number of flags across all the levels be F. There are at most 10,000 flags. We will formulate a recursive function. Let p(i,K) be the probability that
p(0,f) = 0.0 for f < 0, 1.0 for f = 0, 0.0 for f > 0 p(i,K) = p(i1,K  A_{i}) * P_{i} + p(i1,K) * (1.0  P_{i}) The recursive formulation has been derived from the two cases respectively
This recursive formulation can be memoized and that will pass the test cases as well. You can use dynamic programming and calculate all the values in the table with i rows and K columns. We require the probability that the number of Abra flags is at least as much as the number of Kadabra flags. Thus, the answer is Summa( p(N,K), where K ≥ F / 2 ) CODING COMMENTARYFirst, we have completely ignored the fact that the probabilities are given in percents. This makes the discussion easier. You should convert the percents to probabilities. F may be an odd number. In this case, be careful to add up the probabilities from (F+1) / 2. This way, the number of Abra flags will be at least greater than the number of Kadabra flags. You may be implementing the solution in (at least) any one of the following ways table of i by KBe careful that the formulation above leaves room for negative indices being accessed in the table. Make sure that the value of p(i,0) is also updated for each i. table of 2 by KTo calculate p(i,K) we only need values from p(i1,*). This can often lead to faster running implementations since the memory consumed by the array can be reduced. The optimization of course is, maintain only two rows. Mark one of them as active. Treat the active row as the one that must be updated (the row i). Treat the nonactive row as row i1. Be careful to initialize the active row to 0s before you store any result in it. 1D table of KBe careful that if you update the table from left to right, you may end up considering the A_{i} flags again. The answer is, iterate from right to left. This way, we make sure that we will never encounter a value which was updated due to considering the flags in the current level. If you had't thought using 1D array, look at the pseudo code section. PSEUDO CODEDP[0  10000] = { 0 } DP[0] = 1.0 SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 12 Aug '13, 15:18

I wonder, why are all the limits 100? I pondered quite a bit before implementing this problem, thinking that 100^4 is too slow (for other problems it might well be. I suspect there is no maximal test included). Why not use 50 as a constraint, for example? Does it change the problem in any way? answered 12 Aug '13, 17:53

@gamabunta in the pseudo code at the end, shouldnt it be DP[j + Ai] "+=" DP[j] * Pi instead of "DP[j + Ai] = DP[j] * Pi". there can be more than one way of getting to the same number of flags. answered 14 Aug '13, 17:37

found a really nice solution by @greatwall1995. He is using only a single array of size 5000 and calculating the inverse probablity i.e. that of princess not being rescued. This is equivalent to probablity of having number of flags less than or equal to (V1)/2 (max is 50001) where V is total number of flags. Here is the link answered 16 Aug '13, 13:12

Summa( p(N,K), where K ≤ F / 2 ), How come ? This should be Summa( p(N,K), where K >= F / 2 ), right ?
As Abra flags should be greater than or equal to (F+1)/2 .
You are right :) Fixed!