PLATPLTS-Editorial

editorial
,
1

PROBLEM LINK:

PRACTICE
Editorialist: Shivam Kumar

DIFFICULTY:

Hard

PREREQUISITES:

Catalan Number

PROBLEM:

Chef’s has been asked to find the no of ways he can arrange the n(n>= 3) plants in a line left to right, so that he cannot find any three plants that are arranged tallest to shortest (in left to right order). The plant’s height triples do not have to be adjacent. The height of the n plants are in order {1, 2, 3, …, n-1, n}

Input:

The first line contains a single integer n which denotes the number of plants.

Output:

Print the no of ways he can arrange the n(n>= 3) plants in a line left to right, so that he cannot find any three that are arranged tallest to shortest (in left to right order)…

Constraints:

3 <= n <= 35000

Example-1

Input-1

3

Output

5

Explanation:

The heights of the plants are in order {1, 2, 3}. He can arrange the plants in following order {1, 2, 3}, {2, 1, 3}, {1,3, 2}, {2,3,1}, {3, 1, 2}

EXPLANATION:

This question is an application of Catalan Numbers.

SOLUTION:

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using boost::multiprecision::cpp_int;
using namespace std;

// Driver code
int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;

    cpp_int cat_ = 1;

	for (cpp_int i = 1; i <= n; i++) 
	{
		// Calculate the number
		// and print it
		cat_ *= (4 * i - 2);
		cat_ /= (i + 1);
		
	}
	cout << cat_ << "\n";
	return 0;
}