PROBLEM LINK:
Author: Aniket Marlapalle
Tester: Harsh Shah
Editorialist: Aniket Marlapalle
DIFFICULTY:
easy
PREREQUISITES:
dynamic-programming
PROBLEM:
Given a grid of size NXM with each cell having value either 1,2 or 3. Form a cell (x,y) you can go (x+1,y) and (x,y+1), and cost of a path is the product of all the numbers of the cells visited. Given multiple queries with X and Y find if there is a path starting from (1,1) and ending at (N,M) with a cost of 2X*3Y.
EXPLANATION:
We can just pre-compute all the costs by writing a recursive function with 4 parameters,
- Current Row i
- Current Column j
- Current power of 2 in the cost x
- Current power of 3 in the cost y
And make transitions from (i,j) to (i+1,j) and (i,j+1) by updating the cost values depending on the values present on those cells. You will have to memoize the recuresive function to avoid the timeout.
You can also solve the problem by using BFS starting from (1,1) with 2 more parameters as mentioned above.
Mark all the cost values that you visited with in this cell.
Now for every query just check if that (X,Y) is marked in the cell (N,M) or not if Yes then print the answer “Yes” otherwise “No”.
Time Complexity : O(N^2*M^2 + Q)
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here