I first heard about the Facebook Hacker Cup on Twitter from @lhchavez, a friend of mine, a couple of hours before it started. Being a seasoned programming contest participant (I went all the way to the 2009 ACM-ICPC World Finals), I was immediately interested and promptly signed up for it.
The competition started with a 72-hour Qualification Round on January 8, 2011 at 0:00 UTC (January 7, 2011 at 6:00 PM in Monterrey) and ends on January 11, 2011 at 0:00 UTC (January 10, 2011 at 6:00 PM in Monterrey) and will continue with 3 more rounds, culminating with an onsite final at Facebook’s Palo Alto, CA headquarters, after getting back from work on Friday I got to work on the problems.
My first impression when I opened the problems was that the first one seemed pretty straightforward (and it was). Given that they had mentioned that you needed to solve only one of the problems to advance to the next round, I was expecting them to be more difficult, at least on the level of Meal problems on the Facebook Puzzles.
I proceeded to analyze and solve the first problem (Double Squares) only to find out when I submitted it that Facebook said my time had expired. I later found out that me, like many others, did not see the pretty obscure “warning” mentioning that once you opened the input file you had 6 minutes to submit the problem. I was completely unaware of this and, in order to learn more about the problem (and exploring the contest’s UI), I downloaded the input before coding anything.
By the time I was done coding (less than 10 minutes later), my time had expired without me even knowing it had started. To say that I was upset about this is an understatement, especially considering that my dynamic programming algorithm solved the problem for the input practically instantaneously and nowhere near the 6 minute limit. In the end, I could not submit my output and the problem will be unsolved.
As I wanted to advance to the next round, I proceeded to solve the third problem (Studious Student), as it looked (and was) significantly easier than the second one. Unfortunately I fell into the problem’s “trap answer” and only realized it some minutes after submitting my results. I should have known better and tried it with more rigorous test cases but my disappointment due to the time limit issue on the first problem clouded my judgment. Ultimately, the solution I submitted for this problem was incorrect.
Having lost the two easy opportunities to advance to the next round, I proceeded onto the second and, by far, most difficult problem (Peg Game). After finally understanding the “game mechanic” proposed by the problem, I coded and tested it thoroughly. I was ready to make my submission and decided to be very careful when doing it.
In the end, I was unable to upload the result for it on time because it turns out that Opera 11.00 (build 1156), which is what I used to open the input, has a 65536 byte limit on the amount of data it will display when opening a text file. As the browser stopped opening any more data, I thought it had finished and proceeded to copy and paste the data onto my program (which uses standard console input) and believed (correctly) that my implementation was fast enough to process the input with plenty of time to spare, however the seconds passed and I kept on waiting for my program to finish computing a result.
I thought I had come across a very tough test case and kept on waiting completely unaware that what was actually happening is that my program was waiting for more input!. Then I noticed that my CPU utilization was actually pretty low which gave me an indication that my program was idle and noticed that Opera was not showing the reload icon on its toolbar but the stop icon. By this point I only had a bit over 2 minutes left and began to suspect that something was awry so I opened Internet Explorer to download the input there.
This time I decided to open the file directly and load it in Notepad++, this would guarantee that it would be opened correctly as I had previously seen that the files are using the UNIX EOL format and regular Notepad would screw that up. I did that and as I initially expected, the input was processed in around 40 seconds.
Unfortunately by that point I was watching the timer and it ran out before the program finished. A big bummer given that I had put in a couple of hours into this problem.
Overall, the cup was an interesting challenge but slightly disappointing as I missed out on the opportunity to advance to the next rounds due to silly issues. I will be posting the source code to my answers and insight into the problems tomorrow after the contest round is over.