Hello everyone!
I was upsolving ICPC 2021 Amritapuri Regional Contest. I am stuck on the problem Grid jumps. I searched for editorials or discussions but couldn't find any. So this blog is my last hope :((((
Here is the problem link — Grid jumps
Thanks in advance!!!
Intended complexity of the solution is O(n^4). It's a dynamic programming problem. You can define dp[i][j][k] as the maximum value you can achieve to reach cell (i, j) in k steps. Notice that maximum steps are less than 2n. There are O(n^2) transitions per state (loosely speaking) so overall complexity of naively computing dp values will be O(n^5). You can optimize this by using Kadane's algorithm on a 2D matrix. I hope you can find fill in the blanks from here. Btw, in case you don't know, you can look at accepted solutions of teams that participated in the contest. Link: https://codedrills.io/contests/icpc-amritapuri-2021-regional-round/scoreboard