{"id":2174,"date":"2020-07-29T08:32:09","date_gmt":"2020-07-29T08:32:09","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2174"},"modified":"2022-06-17T07:47:22","modified_gmt":"2022-06-17T07:47:22","slug":"cheating-class","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/cheating-class\/","title":{"rendered":"CHEATING CLASS"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Dynamic programming.<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Medium.<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

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).<\/p>\n<\/blockquote>\n

Example:<\/h4>\n

n=4<\/em><\/strong><\/p>\n

\"\"<\/p>\n

\n

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.<\/p>\n

Note: we can\u2019t take chord AC and chord BD because the will intersect and we only have to consider non-intersecting chord.<\/p>\n<\/blockquote>\n

Solving approach :<\/h3>\n

BRUTE FORCE :<\/h4>\n
\n

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

Brute force approach will take exponential time to calculate the required number of ways.But if we use recursion with memoization ,it can be achieved in O(N2<\/sup>) time.<\/p>\n<\/blockquote>\n

You are encouraged to implement the above brute force and think of memoization on your own first ,before looking at the solution.<\/em><\/strong>
\n<\/strong><\/u><\/a><\/p>\n

Optimization:<\/h3>\n
\n

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<\/strong> 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.<\/p>\n<\/blockquote>\n

Solutions:<\/h3>\n\t\t\t\t\t\t