Invitation to India Hacks 2015, Qualification Round 3

Hello!

I want to invite all of you to participate in the last Qualification Round of India Hacks 2016, which is organized by HackerEarth.

This is the third and the last one qualification round. If you missed or didn't qualify in the two previous rounds, this is the last change to advance to the semifinals.

Qualification Round 3 takes place on January 17, 04:30 PM CET (click to check your timezone). Top 1000 participants with non-zero score will advance to the main contest.

The prizes in India Hacks are quite nice, including a trip to San Francisco, many tech gadgets and a lot of goodies for top 50 participants. If you want to grab any of them, or you just like to compete agains a lot of other programmers and you haven't qualified to the main contest yet, reserve a time slot for this round!

I'm a tester of the problem set and a conductor of the contest. There will be 5 problems in the contest and you'll have 3 hours to solve all of them. In addition, a partial scoring system will be used in all of them, which means that you'll get points for each correctly solved test file in any problem.

Big thanks to tanujkhattar, subway, aditya1495 and hellgeek for creating the problems, to belowthebelt for technical assistance and to I_love_Tanya_Romanova and Errichto for proofreading and solving the problems, and for all their suggestions.

Since this is the last qualification round, problems won't be very hard, so if you're going to participate, you may assume that submission time might be a big factor in the final standings.

As a small hint, I can tell you that you should be prepared with number theory, computing optimal subsequences of some types, and techniques used with computation on trees.

Have fun and good luck to all of you!

See you on the leaderboard, hopefully at the top of it

HackerRank Regular Expresso Contest

Tomorrow a new type of contest will be hosted on HackerRank. It's going to be all about regular expressions - a concept that all software engineers should be aware of.

Register for the contest

The contest duration is set to 24 hours and top 10 participants will be awarded with HackerRank T-Shirts. I created two problems there and I'm going to take care of user questions during the contest. As a hint, I can tell you that most problems are not hard if you are familiar with regular expressions already, so speed will be a big factor here.

Have fun with it and see you on leaderboard!

December Easy 2015 by HackerEarth

Hi all,

December Easy Contest by HackerEarth is taking place on December the 3rd at 5:00pm CET. Contest duration is 3 hours.

There will be 5 problems to solve, all algorithmic ones, especially targeted for beginners. However, I'm pretty sure that any participant will find them interesting to solve All the problems have partial scoring and ties are resolved by penalty time.

A little hint for you, 3 of the 5 problems will ask you to minimize some value, so be better prepared with methods of solving these kind of problems

As the tester and editorialist for the contest, I want to thank the problem setter aditya1495 and admin belowthebelt for preparing the contest. It was nice to work with you guys as always!

As a tradition in Easy Contests, the top 5 beginners (1st year or 2nd year) will receive HackerEarth T-shirts.

Good luck and see you on leaderboard!

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!

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:

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:

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:

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.