PROBLEM LINK:
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.