Monthly Archives: July 2015

Screen Shot 2015-08-01 at 12.15.58 AM

One of the greatest contests is coming

Counter Code is one of the biggest 24 hours contests this year. I am super excited, because my problem will be used as a hard challenge there :) Together with Kevin (kevinsogo), who was a tester, we put a great effort to prepare it and we had a lot of fun doing it too :) For now, I can tell you that the problem is called Long Narrow City and it is a graph related challenge.

The contest is sponsored by 6 big companies including Asana, which I use personally. There are cool prizes to win, so we expect a great number of participants - you cannot miss it!

Right now, I am working on the editorial for the problem, which will be very detailed and I will post it after the contest on HackerRank and also here, so stay tuned.

See you on leaderboards!

11011222_511457242338872_6530479336684615373_n

HackerEarth August Easy / Subscriptions to blog enabled

First things first, I have just enabled subscriptions to blog. If you want to get informed about new posts or just appreciate my work, please leave me your email in the box located on the right. I will personally thank you and you will be receiving latest cool news from competitive programming world as soon as possible.

HackerEarth August Easy

August Easy is coming and I am the tester of all problems in it. They are so cool that you have to participate. If you decide to, you will face 6 problems: a geometry one, one involving bitwise XOR, a string challenge, one related to permutations and 2 ad-hoc problems. There are over 1200 people already registered, so we expect a great competition!

and more..

Moreover,  another big 24 hour contest with great prizes is coming and I am the author of a hard problem in it. More details coming soon :) Stay tuned!

1437723775

CodeChef July LunchTime // Editorialist

The CodeChef July LunchTime begins soon and I am the editorialist for the whole problem set.

The problems are really good and if you decide to take part in it, you won't regret it for sure!

As a quick tip, I can tell you that 3 problems are very cool ad-hook ones - they do not require any specific knowledge, just thinking and coding. The last problem is a math related challenge :)

Good luck!

After the contests I will post the most liked editorial here.

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.