PROBLEM LINK:
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.