Facebook Hacker Cup 2012 Qualifier 1

This is that time of the year once again, when coders gather to take part in some good programming fun, the Facebook Hacker Cup. It’s only the first qualifier round, and while I hoped it will go better than last year, well, it didn’t. Not that I’m really surprised.

My Facebook Hacker Cup 2012 Qualifier score
I needed one right to qualify, but I wish I haven't messed up the easiest problem.

After that 72 hours results are in, as is the explanation and example source code for the solutions. It’s good that the example solutions are in Python, I might even learn a trick or too.

Alphabet Soup

The problem setting is easy enough. Funny thought that no matter how many times I counted the letters in the world “HACKERCUP”, I didn’t notice that there are two Cs. I mean, duh! As usual, the example input set was designed such that it wouldn’t trigger the bug of miscounted Cs. This carelessness is one thing that comes up quite often in my programming, probably should take better care of it.

Billboards

This problem actually worked, which means I’m in Round 2, but I guess it can be improved quite a bit, make it more efficient or come up with some heuristics. Or maybe it doesn’t matter much.

Auction

This problem was on a whole different level. While the first two had apparently more than 5000 and 3000 correct solutions respectively, this had only 28… I was thinking about it for quite a while, drawing diagrams, trying to use my intuition and imagination to see where the trick is since the naive O(N^2) algorithm is definitely unusable on the N~10^18 level. On the other hand, I might have tricked myself. Reading the solution the trick was completely different than I expected – I thought there’s some weakness in the random number generator that can be used to express everything analytically, while it is actually just about keeping good track of things. There’s no fancy algorithm to break this problem, just pure logical thinking. Now that’ll teach me as well…

Looking out

This of course means that I have a lot more to learn, and most likely I’m not cut out to be a Facebook caliber hacker. That’s no problem, but good to know. Whenever I think about it, the picture that comes to me is the hacking competition scene from The Social Network, where they hire their first employee. I’d love to be in the middle of such brainfest, such intense creation, such inspired learning from one another while having an an amazing time. Well, fortunately there are other places where I can have that experience, like the Startup Bus. And maybe, I can also set out to create that environment over here in Taiwan.

But first, let’s get ready for round 2, should make that one better.

 

Published by Gergely Imreh

Physicist, hacker. Enjoys avant-guarde literature probably a bit too much. Open source advocate and contributor, both for software and hardware.

Leave a comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.