ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1017. Staircases

How to solve this problem in o(n^2)?
Posted by lnxdx 11 Sep 2019 01:43
How to solve this problem in o(n^2)?
Re: How to solve this problem in o(n^2)?
Posted by Игор 9 Feb 2020 17:08
Let's start from the beginning:
Let R(n) will be the function that returns count of unique staircases.
Now let's introduce function G(n,j) that returns count of unique staircases each first step of which has more than j bricks.
Then R(n) = G(n,0) - 1 . We have to subtract one because it is the case when all bricks are spent on the first step.

G(n,j) = (n>j ? 1 : 0) + (G(n-j-1, j+1) + G(n-j-2, j+2) + ... +G(0,n))

G(n,j-1) - G(n,j) = (n == j ? 1 : 0) + G(n-j, j) => G(n,j) = G(n,j-1) - G(n-j,j) - (n == j ? 1 : 0)

We know that in the case when n<=j G(n,j) = 0, so we can solve upper equation only for cases when j<n, in such cases upper formula will transform to G(n,j) = G(n,j-1) - G(n-j,j).

But we still have to solve the cases when j == 0 and i > j as G(n, 0) = 1 + G(n-1, 1) + G(n-2, 2) + ... + G(0,n)

//Alloc and init matrix g with zeroes

//Calculat g matrix
for(i = 2; i<=N; ++i){
g[i] = 1;
for(j=1; j<i;++j){
g[i] += g[i-j, j];
}
for(j=1; j<i;++j){
g[i][j] = g[i][j-1] - g[i-j,j];
}
}
cout<<g[N]-1;

Edited by author 09.02.2020 17:14