PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: yash_daga
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
easy
PREREQUISITES:
Dynamic programming, elementary probability
PROBLEM:
N participants want to cross a glass bridge.
Each step of the bridge has 2 glass pieces, exactly one of which will break when it’s stepped on.
The participants will go in order; and each participant has full knowledge of the steps taken by the preceding ones.
For each bridge length from 1 to M, find the probability that all N participants fall off the bridge.
EXPLANATION:
Let’s first solve for length equal to M.
The fact that all participants have complete knowledge of all previous movements is quite important here.
The first participant is forced to choose his moves randomly, and so has a 50\% chance of being right on each step.
Suppose the first participant falls off step x_1.
All future participants now know how to be safe till step x_1, because they can simply mimic participant 1's moves before x_1, and then choose the other step at x_1 itself.
However, after x_1 no information is known; so it’s equivalent to having N-1 participants on a bridge of length M-x_1.
This reduction in size to a smaller scenario suggests we can use dynamic programming.
Let p(N, M) denote the probability that there are N participants on a bridge of size M, and they all fall.
Then, by fixing the value x_1 (which can be anything between 1 and M), we obtain
because:
- The probability that the first person falls off step x_1 is 2^{-x_1}, because x_1 50-50 chances have to go his way (win the first x_1 - 1 of them, lose the last one).
- That leaves N-1 people with a bridge of effective length M - x_1, which they have a p(N-1, M-x_1) chance of all falling off by definition.
The base cases are p(0, M) = 1 for all M \geq 0, and p(N, M) = 0 for N \gt M.
The former corresponds to the case when everyone has already fallen off, and the latter to the case where there are more people than steps, so they definitely can’t all fall.
Memoizing the p(N, M) values gives us a solution that’s \mathcal{O}(NM^2), which is correct but unfortunately too slow.
To optimize this, let’s look at the transitions slightly differently.
When the first person takes one step, no matter whether he falls or not, everyone else can definitely get past that step too.
So,
- If the first person falls off the first step, there are N-1 people and M-1 steps left.
- If the first person doesn’t fall, there are N people and M-1 steps left.
This gives us
with the same base cases as earlier, after all our states haven’t changed.
We now have N\cdot M states, with \mathcal{O}(1) transitions from each, so the overall complexity with dynamic programming is \mathcal{O}(NM) which is fast enough for the easy version.
Now, we’ve computed the answer for a fixed M in \mathcal{O}(NM) time.
However, along the way, the answers for all lengths \leq M have been cached too, so simply print them all.
TIME COMPLEXITY:
\mathcal{O}(NM) per testcase.
CODE:
Editorialist's code (PyPy3)
mod = 10**9 + 7
half = (mod + 1) // 2
dp = [ [0]*3005 for _ in range(3005) ]
for n in range(3005):
for m in range(3005):
if n == 0: dp[n][m] = 1
elif n > m: dp[n][m] = 0
else: dp[n][m] = half * (dp[n-1][m-1] + dp[n][m-1]) % mod
for _ in range(int(input())):
n, m = map(int, input().split())
ans = [dp[n][i] for i in range(1, m+1)]
print(*ans)