### PROBLEM LINKS

### DIFFICULTY

EASY

### PREREQUISITES

Simple Math, Dynamic Programming

### PROBLEM

Shiro 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**.

- The probability that
**all the flags are Abra**, is**P**. Otherwise,_{i}**all the flags are Kadabra**.

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**.

### EXPLANATION

Let 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

**K out of F flags are Abra flags**-
**Shiro is at level i**.**i**this is initially**0**

p(0,f) = 0.0 for f < 0, 1.0 for f = 0, 0.0 for f > 0 p(i,K) = p(i-1,K - A_{i}) * P_{i}+ p(i-1,K) * (1.0 - P_{i})

The recursive formulation has been derived from the two cases respectively

- The flags picked at
**level i**are**Abra flags** - The flags picked at
**level i**are**Kadabra flags**

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 COMMENTARY

First, 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 K

Be 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 K

To calculate **p(i,K)** we only need values from **p(i-1,*)**.

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 non-active row as **row i-1**.

Be careful to initialize the active row to **0s** before you store any result in it.

##1D table of K

Be 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 CODE

DP[0 - 10000] = { 0 } DP[0] = 1.0 for i = 1 to N for j = 10000-A_{i}to 0 DP[j + A_{i}] = DP[j] * P_{i}DP[j] = DP[j] * (1.0 - P_{i})

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.