subrat0018's blog

By subrat0018, history, 10 months ago, In English

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!!!

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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