SURESH - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice

Contest

Author: Anurag Anand

Tester: Sameer Gulati

DIFFICULTY:

EASY

PREREQUISITES:

DP, Probabilites

PROBLEM:

You are given a game with N levels. The time taken and the probability of passing a level is given. You need to find the expected time taken to pass all the levels.

EXPLANATION:

Let E_i be the expected time taken to pass all the levels till i.

E_0 = 0. Let us consider level i > 0.
We can write E_i = E_{i-1} + T_i where T_i is the expected time taken to pass level i.
Let us consider two cases at level i:

  • He passes the level: Expected time taken = $p_it_i$.
  • He fails the level: Expected time taken = $(1-p_i)(t_i + E_i)$. This is because he'll have to start again from the first level and pass all the levels till $i$ again.
$T_i = p_it_i + (1-p_i)(t_i + E_i) = t_i + (1-p_i)E_i.$

Hence, E_i = E_{i-1} + t_i + (1 - p_i)E_i

i.e. E_i = \frac{E_{i-1} + t_i}{p_i}

AUTHOR’S SOLUTION:

Author’s solution can be found here.

2

Ti=piti+(1−pi)(ti+Ei)=ti+(1−pi)*Ei.
In this question success in 1st attempt and 2nd attempt is considered only, what about 3rd, 4rd …nth attempt.

So the equation should be Ti=piti+(1−pi)(ti+Ei)+(1−pi)(1-pi)(t1+Ei+Ei)…continues

(1−pi)(1-pi)(t1+Ei+Ei) <— is for the 3rd successful attempt.

I could be horribly wrong, please correct me if so.