PROBLEM LINK:

Practice
Contest

DIFFICULTY:

Medium

PREREQUISITES:

Combinatorics, Recurrences, Catalan numbers

PROBLEM:

There are N points along a circle. We've to draw non-intersecting chords on these points. Special property to satisfy is that if there is a chord between points A and B, number of chords incident on A should be same as number of chords incident on B. Also number of chords incident on any point should be no more than K where K is an input parameter. Task is to find out how many ways of drawing chords are there when atleast one chord is drawn.

QUICK EXPLANATION:

Answers are same for all K > 2 and K = 2. So now there are three cases :

1. K = 0. In this case answer is clearly 0 as we can't draw any chord.
2. K = 2. In this case answer is Catalan(N) - 1
3. K = 1. In this case answer is N^th Motzkin number - 1

DETAILED EXPLANATION:

Firstly, assume that there is no constraint on number of chords incident on a point, or in other words, K is very large (say N). If one tries to draw some cases by hand, it is easy to see that it is impossible to draw a system of non-intersecting chords where 3 or more chords are incident on the same point. If this is true, answers for all K > 2 should be same as answer for K = 2 as in no valid game, would be draw more than 2 chords incident on the same point.

Here is formal proof for the same.

Claim : In any valid system of non-intersecting chords, no point has more than 2 chords incident onto it.

Proof : Consider a game where this is not true. Now consider a graph where all points are vertices and there is an edge between two points if they've a chord between them. Make connected components of this graph. Let C be any arbitrary component. Number of bondings is same for every vertex in a connected component, by definition of game. So if we can prove that there is some vertex of degree 2 in any arbitrarily chosen component, we'd be through.

Say vertices of component are V₁, V₂ .. V_k in clockwise order along the circle. Add chords (V₁, V₂) , (V₂, V₃) .... etc if they don't already exist. They can't intersect with any of the existings chords of this component. Now we've a K sided convex polygon whose vertices are V_i for different i.

Find any diagonal. It separates the polygon into two parts. Take any of the parts. Say the current part is constrained by a diagonal between vertices X[0] and Y[0] and a path between these vertices by the border of the polygon which passes through every vertex between them (there are two possibilities, but we consider any one of them);

Our strategy is to start with some part like this, and then at each stage will we take a part which is inside the previous part.

So repeat the following for i from 0 to infinity:

1) Find any diagonal inside the current part. It separates this part into two smaller parts.
2) If this diagonal connects vertices A and B which are both different from X[i] and Y[i], set X[i+1] = A, Y[i+1] = B and go to 1).
3) If this diagonal connects X[i] and some vertex A, set X[i+1] = X[i], Y[i+1] = A and go to 1).
4) If this diagonal connects some vertex A and Y[i], set X[i+1] = A, Y[i+1] = Y[i] and go to 1).
5) This diagonal can't connect vertices X[i] and Y[i], so there are no more possibilities.

Now this algorithm would stop as every time we're decreasing the number of vertices in our chosen part and there is only finite number of them. When it stops, we've a convex polygon (with atleast 3 vertices) whose all vertices (except 2) are along the circle. Since there is no diagonal (that is why we stopped) in this polygon, vertices on the circle have a degree of atmost 2. Hence proved.

Now let's try to solve the three cases.

Case 1 : K = 0

This is the easiest case. As we can't draw any chord and any valid game must have atleast 1 chord, there are no valid games possible. So the answer for all N is 0.

Case 2 : K = 1

Denote by f(N) the number of different games possible for N points. Let's try to find out a recurrence relation for this quantity. Label all the points and look at point number 1. There are two cases:

1. It has no chord incident to it. Number of valid games of this type is f(N-1).
2. It has exactly one chord incident to it and it connects point 1 with point i. We can't have any more chords incident on points 1 and i, so we may as well delete them from the system. Now look at points [2...i-1] and [i+1...N]. As chords aren't allowed to intersect, these ranges form independent problems of smaller size.

Hence we get following recurrence:

f(N) = f(N-1) + Sum over i from 2 to N { f(i-2) * f(N-i) } 
Base cases : f(1) = 0 and f(2) = 1.

Note that final answer is f(N) - 1 as empty game is not a valid game.
This recurrence can be computed in time O(N²) and is too slow for our purpose. This can be cast in forms where it is more readily computable. As it turns out, f(N) is called N^th Motzkin number and you can check out several of its formulas at OEIS here. One of the formulas on this page that could be used for an O(N) computation of Motzkin number is this. It is a linear recurrence.

a(n) = (n-1)*(2*a(n-1)+3*a(n-2))/(n+1).
f(N) = a(n) + a(n+1)

You can also find a direct linear recurrence for Motzkin number on its wikipedia page.

Case 3 : K = 2

As stated above K = 2 is as good as K = infinity. So all we need to find is the number of non-intersecting systems of chords with one extra contraint : if there is a chord between A and B, number of chords incident on A should be same as number of chords incident on B.

Let's try to derive a recurrence for it.

Firstly we'd try to get away with the constraint that if there is a chord between A and B, number of chords incident on A should be same as that of B.

Claim : The constraint that all vertices of same component have the same bonding number and the fact that no vertex is allowed to have more than 2 bondings together imply that given a connected component, there is only 1 way of creating bonds in that component and that 1 way is a cycle.

Proof :
Choose any vertex v. These are three cases :
a. if deg(v) = 0, then the component has only v. So it is trivial.
b. if deg(v) = 1, then the component has only 2 nodes. It is also trivial.
c. Otherwise, because all nodes has degree = 2, the component must be cycle (size >= 3). Let V₁, V₂, .. V_k be vertices of this component along circle. It is easy to see that there can't be any diagonal chord and so the only way of having a cycle is having cycle along the bonudary of convex polygon formed by these vertices.

Hence given a connected component, there is exactly 1 way of drawing chords respecting all the constraints of the problem.

Hence Proved.

Now we can safely forget the constraint that if A and B have bonding, their bonding numbers should be same. Once we do that, we need to find number of ways of choosing different connected components.

Let f(N) denote the number of valid games. Let g(N) denote the number of valid games where point 1 and point 2 are always bonded. Now let's look the first point. It may not be involved in any bonding in which case answer is f(N-1). Or it might be involved in some bondings. Look at the leftmost such point (along clockwise order). say it is i^th point. Then

f(N) = g(i) * g(n-i+1)

So

f(N) = f(N-1) + summation on i from 2 to N { g(i) * g(N-i+1) }

About computing g(N) : Now as all we care about is connected components (from the claim) and points 1 and 2 are already connected, we could merge them! So

g(N) = f(N-1)

So we get

f(N) = f(N-1) + summation on i from 2 to N { f(i-1) * f(N-i) }

As f(0) = 1,

f(N) = summation on i from 1 to N { f(i-1) * f(n-i) }

This is exactly same as the famous recurrence for Catalan numbers. In fact thanks to Gennady for pointing out, but the image on Wikipedia page of Catalan numbers itself is of this problem : non-intersecting partitions of N-element set.

So the final answer in this case is Catlana(N) - 1 (Again subtract 1 because empty game is not a valid game). All catalan numbers can also be precomputed in O(N) time by using the following more readily computable form of the recurrence:

C(n+1) = 2 (2n+1) C(n) / (n+2)

One final note regarding the implementation. All answers had to be computed modulo (10^14 + 7) and as many contestants noted as well - this MOD is not a prime. That makes things difficult as divison modulo MOD may not be defined in certain cases. There are two work arounds:

1. Use big-integers. Maybe built-in ones of Java or Python or code your own in C++ or your language of choice.

2. Prime factorise MOD as = 43 * 1103 * 2083 * 1012201. Compute all quantities modulo each of these primes and then use chinese remainder theorem to find out the value modulo MOD. Beware, as here divison is also involved, for each quantity one would need to maintain the highest powers of each of these primes which divides them as well.

SETTER'S SOLUTION:

Can be found here.

TESTER'S SOLUTION:

Can be found here.