ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1017. Лестницы

How to solve this problem in o(n^2)?
Послано lnxdx 11 сен 2019 01:43
How to solve this problem in o(n^2)?
Re: How to solve this problem in o(n^2)?
Послано Игор 9 фев 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][0] = 1;
    for(j=1; j<i;++j){
        g[i][0] += g[i-j, j];
    }
    for(j=1; j<i;++j){
        g[i][j] = g[i][j-1] - g[i-j,j];
    }
}
cout<<g[N][0]-1;

Edited by author 09.02.2020 17:14