REI - Editorial

editorial
, ,
1

PROBLEM LINK:

Rei Ayanami and Triangular Colony

Setter: sayan_kashyapi

Tester: debrc

Editorialist: sayan_kashyapi

DIFFICULTY:

Easy

PREREQUISITES:

Catalan Numbers

PROBLEM:

There was a right angled triangular colony whose height and width is N dekameter. There are horizontal and vertical roads running from left to right and top to bottom respectively at a distance of 1 dekameter each. Ayanami’s house is located on the top end of the colony. The candy shop is located on the opposite side of colony. Now by moving only down or right, she has to reach out the shop.

EXPLANATION

By observation, we can see that,
For a colony of 1 dekameter size the number of different path = 1.
For a colony of 2 dekameter size the number of different path = 2.
For a colony of 3 dekameter size the number of different path = 5.
For a colony of 4 dekameter size the number of different path = 14.

So, it’s following the Catalan Number series.

Therefore, the total number of ways of triangulation = C_N.

TIME COMPLEXITY

Time complexity is O(N) for each test case.

SOLUTIONS:

Setter's Solution
C++17 
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using boost::multiprecision::cpp_int;
using namespace std;
const int MOD = 1000000007;
void catalanNumber(int n)
{
    cpp_int cat_ = 1;
    for (cpp_int i = 1; i <= n; i++)
    {
        cat_ *= (4 * i - 2);
        cat_ /= (i + 1);
    }
    cout << (cat_) % MOD << endl;
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        catalanNumber(n);
    }
}
Tester's Solution
PYTH 3.6 
import math,sys
MAX=1001
MOD=1000000007
INT_MAX=sys.maxsize
dp=[0 for _ in range(MAX)]

def precompute():
    dp[0]=1
    for i in range(1,MAX):
        dp[i] = 0
        for j in range(0,i):
            dp[i]=(dp[i]+(dp[j]*dp[i-j-1])%MOD)%MOD


precompute()
for _ in range(int(input())):
    n=int(input())
    a=[i for i in range(1,n+1)]
    print(dp[n])

Feel free to share your approach.
Suggestions are welcomed as always had been.