Home » Algorithms

Non-intersecting chords using Dynamic Programming (DP)

Non-intersecting chords using Dynamic programming: find number of ways in which N non- intersecting chords can be formed using these 2*N points.
Submitted by Ritik Aggarwal, on December 09, 2018

Problem: You are given N chord and 2*N points. You have to find the number of ways in which N non- intersecting chords can be formed using these 2*N points. The answer may be too large so the answer must be taken mod with 10^9 + 7.

Constraints: 1 <= N <= 100

Example:

    Sample input 1:
    2
    Sample output 1:
    2

    Sample input 2:
    100
    Sample output 2:
    558488487

Explanation of the problem:

In the first sample provided above, there are 2 chords and 4 points. Let us label them as A, B, C, D in order. Now possible arrangements are chords AB and chords CD, the second possible arrangement is chord AD and chord BC.

Note: we can’t take chord AC and chord BD because the will intersect and we only have to consider non-intersecting chord.

Solution:

Before proceeding to the solution we can see that the recursive solution will be hard to implement so we will proceed to the dynamic programming approach. In this approach, we select a point and a variable point and then make a chord using both points to divide the circle into two halves then using dp matrix we will find the number of ways to form rest of the chords in both halves multiply them and add them to the solution of i^th column. We will proceed this with same fixed point and different variable point and store the answer in i^th column.

Algorithm

1. Create dp matrix in which ith cell represent the number of ways to form ith points.
2. Start filling dp matrix from the 4^th row (no need to fill odd columns as there answer will be zero).
3. Find the answer of each row by using dp relations.
4. If points in any of the half is 0 then add the number of ways of another half in the answer.
5. Otherwise, multiple numbers of ways in both the half and add to the answer of i^th cell.
6. Store the answer in i^th cell.

C++ Code for Non-intersecting chords using Dynamic Programming (DP)

#include <iostream>
using namespace std;

long long int mod = 1000000007;
// function to find the number of ways
int non_intersecting(int n){
    // total number of points is twice of n
    int tot_points = 2 * n;
    // Intializing all element to zero
    long long int dp[tot_points + 1] = {0};
    // At 2 points number of ways in only 1
    dp[2] = 1;
    for(int i = 4;i<tot_points + 1;i = i + 2){
        long long int sum = 0;
        for(int j = 0;j<i;j = j + 2){
	    // number of points in first half
            int fh = j;
	    // number of points in second half
            int sh = i - j - 2;
	    // if there are 0 points in any half just 
		// add number of ways of other half
            if(fh == 0){
                sum += dp[sh];
                sum %= mod;
            }else if(sh == 0){
                sum += dp[fh];
                sum %= mod;
            }else{
		// used distributive property of modulus
                sum += ((dp[fh] * dp[sh]) % mod);
                sum %= mod;
            }
        }
        dp[i] = sum;
    } 
    return dp[tot_points];
}

// driver function 
int main() {
	int n;
	cin >> n;
	cout << n << endl;
	cout << non_intersecting(n);
	return 0;
}

Output

2
2