PROBLEM LINK:
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 :
- K = 0. In this case answer is clearly 0 as we can’t draw any chord.
- K = 2. In this case answer is Catalan(N) - 1
- K = 1. In this case answer is Nth 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 V1, V2 … Vk in
clockwise order along the circle. Add
chords (V1, V2) , (V2, V3) … 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 Vi 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:
- Find any diagonal inside the current part. It separates this part into two smaller parts.
- 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). - If this diagonal connects X[i] and some vertex A, set X[i+1] =
X[i], Y[i+1] = A and go to 1). - If this diagonal connects some vertex A and Y[i], set X[i+1] = A,
Y[i+1] = Y[i] and go to 1). - 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:
- It has no chord incident to it. Number of valid games of this type is
f(N-1). - 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(N2) 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 Nth 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 V1, V2, … Vk 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 ith 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:
-
Use big-integers. Maybe built-in ones of Java or Python or code your own in
C++ or your language of choice. -
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.