minimario's blog

CEOI 2016 Kangaroo Solution
By minimario, history, 8 years ago, In English

Hello :')

Recently I've solving this: link, and I've read solution here.

When the solution says, we can infer the following recurrences:

A[n][i][j] = D[n-1][i][j-1] + D[n-1][i+1][j-1] +…+ D[n-1][n-1][j-1]
D[n][i][j] = A[n-1][1][j-1] + A[n-1][2][j-1] +…+ A[n-1][i-1][j-1],

Is this only valid for i<j? Because the solution says, that when renumbering, we remove i and relabel everything greater than i. But if i>j, then the recurrence will not be D[n-1][smth][j-1], but rather D[n-1][smth][j].

But if both A and D are valid for only i<j, then do the formulas really work? Because in the sum for A[n][i][j], we will add some D[n-1][i'][j'] such that i'>j'. Then the recurrence wouldn't really work.

Can anyone provide some explanation or clarification on this?

Thanks,

-minimario

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

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

Auto comment: topic has been updated by minimario (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

From what I understand, is that A[n][i][j], i>j is a valid value defined as in the case i<j, though the recurrence provided for the case i<j does not work in this case.

Nevertheless we manage to express A[n][i][j] and D[n][i][j] in terms of other such values for which i<j, so we don't really care about calculating these numbers in cases for which i>j.

→ Reply