MAXGAME - Editorial






Combinatorics, Recurrences, Catalan numbers


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.


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 Nth Motzkin number - 1


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 =
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
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
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
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
  2. It has exactly one chord incident to it and it connects point 1 with point
    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
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

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.

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


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.


Can be found here.


Can be found here.


Can someone comment the tester’s solution? Thanks

1 Like

Can’t believe I didn’t think to use CRT having written the code for it recently! I even had the factors of the modulus written out!

I think the time for Java programs didn’t set properly for this problem. My code similar to the setter’s solution in Java timed out.

The code Link:

Got it. The BigInt representation was confusing, but it uses the same solution. It’s cool that using base M, the % operation takes O(1).

The problem I had using the chinese remainder theorem was that I had to divide by the prime numbers, which have no multiplicative inverse. I’ll see if I can find a solution that works around the problem

Yes, it is very tricky, especially for Motzkin number which includes + operation in its recurrence formula. See shevchen’s solution And please see evgentu’s solution which does well with O(n^2) recurrence formula for avoiding this issue.

My carefully optimized O(N^2) straightforward 2D DP solution without modulo division or multiplication (only addition) got accepted.

“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.” Can someone explain how this could help?

good work to use LCD having written the code for it recently

link text