Hi, I wanted to know the logic for ANTEATER problem listed in the CodeChef’s June cook-off challenge.
Thanks!
Editorial just came out wait for a bit you will get the logic here
I created a 3D table dp of size 50 * 50 * 50. Now traverse each cell and if the cell has L, R, U, D, we traverse the row to right, left or the column to up or down till we either move out of the matrix or we find an anteater. While traversing we keep a count of how many steps it shall take to reach the particular cell and we increment A = dp[row][col][count] by 1. Finally, for all cells, we add A * (A - 1) /2 to the final answer. ( We actually don’t need to do this final traversal to get value of count but instead at the time of increment, add the previous value of cell to answer. Complexity: O( T * R * C * max(R, C))
2 Likes