I love competitive programming. I love the anticipation while I wait with my fingers crossed after submitting a solution. And the rush that follows after getting an ‘AC’.

After stagnating near the 60-70th percentile for eons, I have decided to dedicate focused practice time for competitive programming. The next series of blog posts will track my journey through USACO.

All the best to me!

…

Facebook recently organized the qualification round of Hacker Cup 2015. They posed some interesting problems and anyone who could get at least one problem right can move to the next round.

I managed to get a rank of 217, with a perfect score of 100. I have posted my solutions below with a little bit of commentary. You can access the problems here.

Cooking the Books (15 points)

This was the easiest question. Since the constraints were so small, it suffices to use brute force and try all possible swaps. Care has to be taken however to make sure that a number never starts with 0.

…

Iterating over all possible subsets of a set is a problem that can arise not only in competitive programming but also in day-to-day programming. While the total number of possible subsets is quite huge (2^n where n is the cardinality of the input set), often we want an algorithm that systematically considers all subsets for small values of n.

A power set is a set of all subsets of a given input set. Often we may want to simply iterate over all members of the power set, but sometimes (if we have enough memory) we may need the power set itself. In the following post, I have attempted to present some algorithms (with C++11 implementations) that solve both kinds of problems (simple iteration and complete power set construction).

…