Editorial for Facebook Hacker Cup '17 Qualifying Round P3 - Fighting the Zombie - Olympiads Online Judge

Editorial for Facebook Hacker Cup '17 Qualifying Round P3 - Fighting the Zombie

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

For each attack, we need to compute the probability that it rolls at least $H$ $H$ damage. We can compute this using dynamic programming.

Let $f(D, K)$ $f (D, K)$ be the probability of dealing at least $K$ $K$ damage with $D$ $D$ dice. For a given input $X\ Y\ Z$ $X Y Z$ , we want to compute $f(X, H-Z)$ $f (X, H - Z)$ . We can use the following recursive definition:

$f(D, K) = 1$ $f (D, K) = 1$ for $K \le 0$ $K \leq 0$ (We can always do at least $0$ $0$ damage)
$f(0, K) = 0$ $f (0, K) = 0$ for $K > 0$ $K > 0$ (We can't do a positive amount of damage with $0$ $0$ dice)
$f(D, K) = \frac 1 Y \sum_{d=1}^Y f(D-1, K-d)$ $f (D, K) = \frac{1}{Y} \sum_{d = 1}^{Y} f (D - 1, K - d)$

This last formula combines the outcomes of all possible die rolls for a single die, and weights them evenly by $\frac 1 Y$ $\frac{1}{Y}$ .

In this way, we can compute the probability of success for each attack in $\mathcal O(XY(H-Z))$ $O (X Y (H - Z))$ time.

Since the most damage we can do is $XY$ $X Y$ , we can trivially reject any case where $H-Z > XY$ $H - Z > X Y$ . That means we can also consider the time complexity to be $\mathcal O(XYXY) = \mathcal O(X^2 Y^2)$ $O (X Y X Y) = O (X^{2} Y^{2})$ .

Comments

There are no comments at the moment.