The “2011 Facebook Hacker Cup” is currently happening, and the qualification stage has just finished as I write those lines.
Since I like solving fun problems I took part and solved all 3 problems and will be progressing to next stage. The goal here is speed (code won’t be reviewed by Facebook staff, but you need to produce results fast) so I decided to trade CPU cycles for development time. It took less time to write the code, but the CPU usage will be a bit more intensive than what it could be if I took time to optimize the code and fine more elegant ways to produce the required output.
So, let me explain the first one, called “Double Squares”. The problem here is quite simple, and revolves around the following equation:
x² + y² = a
Only a is known. x and y are both integer values between 0 and 2147483647 (0x7fffffff, the maximal value for a signed integer). The goal is not to find x or y, but to determine how many values of x and y can yield to the equation being true. And reversing values for x and y do not count as an extra solution.
First, let’s make this equation a bit easier to handle, shall we? What if we write our equation this way:
y = sqrt(a – x²)
We could then cycle through the possible values of x, compute y each time and see if it is integer. The problem makes things even easier:
- We know the minimal value of y is 0, which means the maximal value for x would be sqrt(a). Since the maximal value for a is 2147483647, this means x will never be over 46340.
- To avoid duplicate values of x and y we can stop as soon as y goes below x. This also means that in the worst case, we’ll have to test half of all the possibilities (23170 iterations in worst case is viable)
Looks like bruteforce is a viable solution.
My implementation in PHP needed about 200ms with the values from Facebook’s input. I was a bit disappointed it ran this fast (can’t really call it bruteforce) but at least the result is good.