Final fight // HackerEarth July Easy

My official editorial to this problem turned out to be very popular and liked by HackerEarth community, so I decided to post it here also :)

The original problem statement is available here.

This problem is pure math. Let's reformulate it a little bit first.

Let R represents a single Arjit's soldier and D represents a single soldier who belongs to Fatal Eagle. Then we are interested in the number of sequences of R's and D's consisting of N R's and N D's, such that in any prefix of these sequences the number of R's is not greater than the number of D's. We call any such sequence a valid sequence and any not valid sequence we call an invalid one.

Why I called elements of sequences R and D and not for example 0 and 1? Well, this helps us to represent the problem in a graphical way which is probably the greatest explanation here.

Let's consider a grid of size N \times N and any path starting in its upper left corner and ending in its bottom right corner. Any such path uses N moves right and N moves down. If we represent a right move as R and a down move as D, we can see an analogy to our sequences! Great, but we are searching for only valid sequences, how a valid sequence is represented on the grid? Well, it is any path which does not cross the diagonal. Consider the following illustration of a valid path:

valid

It is easy to see, that any valid path does not cross the diagonal, so in its every prefix, it has at least as many R's as D's. Sounds great, but how to count the number of valid walks? We will do this counting the number of all paths and subtracting from it the number of invalid paths.

There are \binom{2N}{N} paths in the grid, because we have to make 2N moves and N from these moves has to be down moves.

Invalid paths

The only remaining task is to count the number of invalid paths. Remember that any invalid path crosses diagonal at least once? Let p be a point when it crosses it for the first time. Take a look at the illustration for better understanding:

invalid_with_p

Let's now do some clever transformation which is super useful in counting invalid paths. Let's take any invalid path and its point p. Then reflect its subpath which begins at p, the transformation is presented as follows:

invalid_transformation

Now notice that any invalid path can be transformed this way and the transformations of two different invalid paths produces two different paths on grid of size (N - 1) \times (N + 1). Moreover, any path on (N - 1) \times (N + 1) can be produced from an invalid path on grid N \times N, so there is a bijection between invalid paths on N \times N grid and paths on (N - 1) \times (N + 1) grid. From these observations, we know that there are \binom{2N}{N + 1} invalid paths.

Putting it together

The answer to this problem is \binom{2N}{N} - \binom{2N}{N + 1} and you can compute it using factorials after expanding the equation. In order to get the result modulo 10^9 + 9, you can use modular inverse to simulate division with multiplication.

Bonus credit

If you expand the final equation, \binom{2N}{N} - \binom{2N}{N + 1}, and simplify it, you will get the definition of the Catalan Number, i.e 1 / (N + 1) \cdot \binom{2N}{N}. It arrises so many times in counting that you should be familiar with it definitely.