Facebook decided to launch Hacker Cup, a programming contest to attract the world’s best talents to their HQ. The qualification round started on Friday 4pm (US’s PST timezone) and continues for 72 hours, so go ahead and join now.
Just finished Facebook Hacker Cup Online Qualification Round and thought that I might share some of my thoughts about it.
Just like Google’s CodeJam, this round consisted a total of three problems, and you would need to solve just one of the problem correctly to qualify for the next round.
I admit, I had a lot of fun in this round (which had a lot of hidden surprise in the problems), but the contest’s interface totally suck the hell out of a rhino’s @$$. And seemed like I am not the only one who agrees on this.
The first glitch that really got on my nerves —
As you download the input file, the timer starts to countdown, without you knowing about it. Then, I found a little notice on the corner saying that you would have to refresh the browser after downloading the input file to see the timer. I don’t know why, but this seemed stupid and unacceptable to me.
Second, when you want to submit the answer, it opens up a small text box (by small I mean something like 10×100 pixels), and you are suppose to paste your program’s output to that little text box. What a FAIL — They could have done much better.
Third, after you submitted the answer, there is a message box that mentioned that you would need to wait until the contest is over to find out if your answer is correct. Oh well… On the other hand, the timer just continue on ticking until it says “Time expired”. You get multiple chances to submit your answer, but ONLY within the limited time. I learned the hard way. My advice to you is test your code carefully for edge cases before downloading the input. During the limited time you won’t be able to do much about it if you find that your code has a bug.
Anyway, enough ranting and let’s move on to the fun part, which are the problems itself.
This is a really fun problem with a little surprise behind it. While you are reading the problem, you would notice a little subtitle under the main title “Facebook Hacker Cup” that says “Too hard for brute force, switching to dp“. It’s there for a purpose. I knew I did not get this correct because of their timer display requires a browser reload…
You need to read this problem carefully. Don’t worry, you won’t need much from theory of probability. Reminds me of the binomial theorem. If there are no missing pegs, then the probability of each column could be calculated easily using binomial coefficients. This problem is pretty straight forward, but you need to be some what careful.
This is a fun problem. It is easy to understand the problem statement and it is also easy to fall into a trap. This problem is not as straight forward as you think it might be.
I will post my analysis and solution after the contest is over. Till then have fun solving the problems!