BLDSTAIR - Editorial

PROBLEM LINK:

Contest

Author: Ritik Gour
Tester: Toshit Kale
Editorialist: Ritik Gour

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Math, DP

PROBLEM:

Find the number of ways in which the stairstep of height N could be built using N rectangular blocks.

QUICK EXPLANATION:

Find the nth Catalan number using the formula and keep its value bounded to the maximum possible value of integer supported using modulo 10^9+7 in each step.

EXPLANATION:

In the given problem, it was asked to find the number of ways in which the stairstep of height N could be built using N rectangular blocks.
Actually, this is one of the many applications of Catalan numbers.
The idea is to find the Nth Catalan number using the given formula.

Catalan numbers satisfy the following recursive formula:

C_0 = 1 and C_{n+1} = \sum_{i = 0}^{n} C_i C_{n-i}

Finding the value of the nth Catalan number using the above-given formula requires exponential time.
So, a simple approach involving the direct use of the above-given formula would not be enough to satisfy the constraints for the given problem.

We can observe that the above recursive formula does a lot of repeated work. Since there are overlapping subproblems, we can use dynamic programming for this. The solution to this problem is a dynamic programming-based approach.

Firstly, an array is created to store the solutions of subsequent numbers starting from 0 up to the given number N.

The Catalan numbers for 0 and 1 are set to 1 and 1 respectively.

For numbers starting from 2 to N, the Catalan numbers are calculated using the already calculated values for previous numbers.

Since the answer could be a very large number (out of datatype bounds), modulo division is applied (mod 10^9+7) in each step of the calculation.

SOLUTIONS:

Setter's Solution
#include <iostream>
#define mod 1000000007
using namespace std;
unsigned long int stairWay(int n)
{
	unsigned long int step[n + 1];
	step[0] = step[1] = 1;
	for (int i = 2; i <= n; i++) {
		step[i] = 0;
		for (int j = 0; j < i; j++)
			step[i] = ((step[i] % mod) + ((step[j] % mod) * (step[i-j-1] % mod) % mod)) % mod;
	}
	return step[n];
}

int main()
{
	int T,N;
	cin>>T;
	while(T--){
		cin>>N;
		cout<<stairWay(N)<<"\n";
	}
	return 0;
}

Tester's Solution
#include <iostream>
#define mod 1000000007
using namespace std;
unsigned long int stairWay(int n)
{
	unsigned long int step[n + 1];
	step[0] = step[1] = 1;
	for (int i = 2; i <= n; i++) {
		step[i] = 0;
		for (int j = 0; j < i; j++)
			step[i] = ((step[i] % mod) + ((step[j] % mod) * (step[i-j-1] % mod) % mod)) % mod;
	}
	return step[n];
}

int main()
{
	int T,N;
	cin>>T;
	while(T--){
		cin>>N;
		cout<<stairWay(N)<<"\n";
	}
	return 0;
}

1 Like