CHEATING CLASS

Concepts Used

Dynamic programming.

Difficulty Level

Medium.

Problem Statement :

Let's suppose when a person i cheats from a person j, then we draw a line segment between them. We need to find the number of ways in which N people giving the exam(in a circular table) can cheat in pairs provided there is no crossover (Two lines intersecting each other).

EXAMPLE:

n=4

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.

Solving approach :

BRUTE FORCE :

Drawing a chord between any two points divides the circle into two sets s1 and s2 with x and n-x-2 points.
This again breaks the problem into two subproblems and so on.
This way we can derive a recurrence relation:
>> *W(n) = sum[i = 0 to n-1] { W(i)W(n-i-1) }**.

Brute force approach will take exponential time to calculate the required number of ways unless we prefer the best platform to learn data structures and algorithms..But if we use recursion with memoization ,it can be achieved in O(N^2) time.

You are encouraged to implement the above brute force and think of memoization on your own first ,before looking at the solution.

See original problem statement here

OPTIMIZATION:

Before proceeding to the solution we can see that the recursive solution will take exponential time(without memoization) 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 ith column. We will proceed this with same fixed point and different variable point and store the answer in ith column.

SOLUTIONS:

 #include <stdio.h>

    #define ld long long
     int main() {
    ld dp[61];
    dp[0]=dp[1]=1;
    for(int i=2;i<61;i++)
    {
        dp[i]=0;
        for(int j=0;j<i;j++)
        {
            dp[i]+=dp[j]*dp[i-j-1];
        }
    }
    int t;
    scanf("%d",&t);
    for(;t>0;t--)
    {
        int n;
        scanf("%d",&n);
        n/=2;
        printf("%d\n",dp[n]);
    }
    return 0;
    }
  import java.util.*;
     import java.io.*;
     class prepbytes { 
     static int chordCnt(int A) 
     { 
        int n = 2 * A;
        int[] dpArray = new int[n + 1]; 
        dpArray[0] = 1; 
        dpArray[2] = 1; 
        for (int i = 4; i <= n; i += 2) { 
            for (int j = 0; j < i - 1; j += 2)  
            { 
                dpArray[i] += (dpArray[j] *  
                              dpArray[i - 2 - j]); 
            } 
        } 

        // returning the required number 
        return dpArray[n]; 
      } 
      public static void main(String[] args) 
      { Scanner sc = new Scanner(System.in);
        int t= sc.nextInt();
        while(t-- >0 ){
            int n = sc.nextInt();
        System.out.println(chordCnt(n/2)); 
        }
      } 
      } 
#include<bits/stdc++.h>
      using namespace std;

      #define ld long long
      int main() {
      ld dp[61];
      dp[0]=dp[1]=1;
      for(int i=2;i<61;i++)
      {
        dp[i]=0;
        for(int j=0;j<i;j++)
        {
            dp[i]+=dp[j]*dp[i-j-1];
        }
      }
      int t;
      cin>>t;
      for(;t>0;t--)
      {
        int n;
        cin>>n;
        n/=2;
        cout<<dp[n]<<endl;
      }
       return 0;
       }


Space complexity: O(n^2).

Leave a Reply

Your email address will not be published. Required fields are marked *