×

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 Ai flags.

• The probability that all the flags are Abra, is Pi. Otherwise, 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 - Ai) * Pi +
p(i-1,K) * (1.0 - Pi)


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 Ai 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-Ai to 0
DP[j + Ai] = DP[j] * Pi
DP[j] = DP[j] * (1.0 - Pi)


# SETTER'S SOLUTION

Can be found here.

# TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

2.4k128183169
accept rate: 14%

2

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 .

(14 Aug '13, 08:27) 3★

You are right :) Fixed!

(14 Aug '13, 12:15)

 1 one of the best problem in DP... answered 20 Aug '13, 00:26 16●1●1 accept rate: 0%
 0 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 5★hedgefog 15●1 accept rate: 0% 1 it is not 100^4 it is 10^2 * 10^4 = 10^6 :) (14 Aug '13, 19:58)
 0 @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 3★kcahdog 10.0k●28●54●129 accept rate: 14%
 0 Yes it should be DP[j + Ai] "+=" DP[j] * Pi answered 14 Aug '13, 21:56 3★coolbun 29●1●2 accept rate: 0%
 0 in the pseudo code at the end, is the case DP[j+Ai]+=DP[j+Ai]*(1-pi) included or is it not required?? answered 15 Aug '13, 15:10 1 accept rate: 0%
 0 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 (V-1)/2 (max is 5000-1) where V is total number of flags. Here is the link answered 16 Aug '13, 13:12 3★kcahdog 10.0k●28●54●129 accept rate: 14%
 0 can anyone explain me the recurssion? answered 02 Oct '13, 18:07 4★s24w 45●6 accept rate: 0% It's not difficult if you got what p(i, K) stands for... Let say you are at level i, then probability, that Shiro picked K flags is: with probability Pi you pick Ai flags, so in next level you are interested in probability, that you pick K-Ai flags, what is exactly p(i+1, K-Ai) and also there is complementary probability, so you have to add those two... (02 Oct '13, 21:59)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×14,365
×3,155
×1,754
×279
×27

question asked: 12 Aug '13, 15:18

question was seen: 6,758 times

last updated: 02 Oct '13, 21:59