SHIRO - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

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

13 Likes
2

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?

1 Like
3

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

4

Yes it should be DP[j + Ai] “+=” DP[j] * Pi

5

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

6

one of the best problem in DP…

1 Like
7

can anyone explain me the recurssion?

8

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 .

2 Likes
9

You are right :slight_smile: Fixed!

10

it is not 100^4 it is 10^2 * 10^4 = 10^6 :slight_smile:

1 Like
11

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…