CATALAN NUMBERS:

unsigned long long ar[ ]= {1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452,18367353072152,69533550916004, 263747951750360, 1002242216651368, 3814986502092304, 14544636039226909 };
 
Formula:
Cn = 2nCn/(n+1) = 2n!/{(n+1)!n!}
we can also use this formula
C0 = 1
Cn = Cn-1*(4n-2)/(n+1)
 Source code:

Applications:

1. How many ways are there to construct n pairs of parentheses which are correctly matched.
[Analysis: The leftmost parenthesis l matches some right parenthesis r. Suppose there are k pairs between l and r, there will be n-k-1 pairs outside. Hence, the number of possibilities will be]

2. Counting the number of paths across a lattice which do not cross the diagonal line. More generally, Cn is the number of Dyck words of length 2n. A Dyck word is a string consisting of n X’s and n Y’s such that no initial segment of the string has more Y’s than X’s. eg: XXXYYY, XYXYXY, XYXXYY…

3. Counting the number of rooted ordered binary trees with n+1 leaves.

4. Counting the number of ways n+1 factors can be completely parenthesized.

5. Counting the number of ways of associating n applications of a binary operator.

6. Counting the number of ways a convex polygon with n+2 sides can be cut into trangiles by connecting vertices with straight lines.

7. Counting the number of ways to tile a stairstep shape of height n with n rectangles.

Resources:



Comments

Post a Comment

Popular posts from this blog

HackerEarth: City and Campers 2 (DSU-UnionFind)

HackerEarth: City and Campers 2 (DSU-UnionFind) ///==================================================/// /// HELLO WORLD !! /// /// IT'S ME /// /// BISHAL GAUTAM /// /// [ bsal.gautam16@gmail.com ] /// ///==================================================/// #include<bits/stdc++.h> # define X first # define Y second # define mpp make_pair # define nl printf("\n") # define SZ ( x ) (int)(x.size()) # define pb ( x ) push_back(x) # define pii pair<int,int> # define pll pair<ll,ll> ///--------------------- # define S ( a ) scanf("%d",&a) # define P ( a ) printf("%d",a) # define SL ( a ) scanf("%lld",&a) # define S2 ( a,b ) scanf("%d%d",&a,&b) # define SL2 ( a,b ) scanf("%lld%lld",&a,&b) ///------------------------------------ # define
Read more

Two Pointers Technique & Binary Search For Beginners

Sample Problem: Electronics Shop ( HackerRank ) (Find me on HackerRank @ Handle:  BishalG  ) Problem Summary: In this problem, you are given two arrays of positive integer numbers of lengths n and m respectively and another positive integer b . Your task is to find out the maximum integer formed by the summation of two integer values taken from different arrays and is less than or equal to b. If there does not exist such summation print -1 . Solution Idea: Since the constraints for n and m are small ( i.e. 1 <= n, m <= 1000 ) , so this problem is very much suitable to test different variants of our solution approaches. Here, we will discuss about 3 different approaches to solve this problem progressively starting from least efficient solution to most efficient one. Approach - 1: Brute-force If we think in brute-force manner, the naive approach to solve this problem will be to try every possible pairing among these two arrays. For this, we can just iterate ove
Read more

Problem : Codeforces Round #406 (Div. 1) B [ Legacy ]( Dijakstra, Segment tree)

You are given graph N (10^5) nodes and starting node (S), You have to find min distance needed to go to all other nodes. Connections among nodes are a little bit different in the form of range type queries, which are: (1) you can open a portal from planet u to planet v with cost z. (2) you can open a portal from planet u to any planet with index in range [l, r] with cost z. (3) you can open a portal from any planet with index in range [l, r] to planet u with cost z. Idea: If we tried to make a adjacency matrix normally by traversing from l to r in (2) and (3) type of connection queries, it will surely time out. So, what we have to do is to think little bit about segmenttree representation of array. This representation allow us to make connection matrix only with LOGN adjacency nodes. So that we may proceed further. Lets build two types of segment-tree nodes , say UP segment tree , which will be used for (2) type of query and DOWN segmenttree which will be used for (3) type of
Read more