MCO16402 - Editorial

PROBLEM LINK:

Practice
Contest

Author: Zi Song Yeoh

DIFFICULTY:

EASY

PREREQUISITES:

DYNAMIC PROGRAMMING

PROBLEM:

Given a grid, find the number of ways a robot can reach each square after k moves.

EXPLANATION:

To solve subtask 1, a simple exponential brute force suffice. There are 4^{10} \approx 10^{6} possible sequences of moves and thus we can try them all. This approach works in O(4^{k} \cdot k) time.

To get AC, we can use a simple dp solution. Let dp[i][j][k] be the number of ways to reach square (i, j) in k moves. Now, we can easily fill this dp table in O(nmk) time by checking the four neighbours each square. Time complexity is O(nmk).

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

RELATED PROBLEMS:

//