dx24816's blog

By dx24816, history, 5 years ago, In English

Hello,

I was recently reading the solution for the 2016 CEOI problem Kangaroo. However, I can't understand what motivates you from switching from A[n][i][j] and D[n][i][j] to trying to compute X[n][i][j] and Y[n][i][j]. I know it's a common trick to substitute sum and difference, but is there a deeper reason for why I would think of doing this substitution and knowing that it will work out?

Problem: https://oj.uz/problem/view/CEOI16_kangaroo Solution: http://ceoi.inf.elte.hu/probarch/16/kangaroo-solution.pdf

-dx24816

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It is usual to write any DP solution, look at the transition and try to simplify it/apply data structures.