# CHESSGM - Editorial

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.