CHESSGM - Editorial

PROBLEM LINKS

Practice
Contest

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.

//