PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
We can solve this problem using Dynamic Programming:
-
Call F(i, j, t) = the number of ways to complete the game after t turns in the state that the left pawn is i steps far from the middle, and the middle pawn is j steps far from the right one.
-
So F(i, j, t) = SUM( F(i’, j’, t - 1) ) while (i’, j’) can be:
— (i + 1, j) in case the last move is the move of the left pawn,
— or (i - 1, j + 1) in case the last move is the move of the midle pawn,
— or (i, j - 1) in case the last move is the move of the right one.
-
The base state should be F(0, 0, 0) = 1,
-
then the result should be F(0, 0, K).
This solution takes a complexity of O( D^2 x K ).
To reduce the complexity, we use matrix multiplication!
- At first, we build the matrix M, while M(s, s’) = 1 or 0 whether the state s can go directly to state s’ or not (each state s or s’ represents a state of (i, j) in the DP function mentioned above), then
- Just take the power K of the matrix M and take the sum of M(s, s * ) as the result while s * is the state of (0, 0).
This solution takes a complexity of O( D^6 x log2(K) ).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.