Hello :')↵
↵
Recently I've solving this: [link](http://ceoi.inf.elte.hu/probarch/16/kangaroo-statement.pdf), and I've read solution [here](http://ceoi.inf.elte.hu/probarch/16/kangaroo-solution.pdf). ↵
↵
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
↵
Recently I've solving this: [link](http://ceoi.inf.elte.hu/probarch/16/kangaroo-statement.pdf), and I've read solution [here](http://ceoi.inf.elte.hu/probarch/16/kangaroo-solution.pdf). ↵
↵
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
