ATTENTION: CoudyNews Will be Closed
1 min readCoudyNews will be closed on Saturday, January 15, between 7:00 am and 4:00 pm, as I have qualified in the Facebook Hacker Cup and have moved on to the next round.
The competition is time-based, and therefore I will need to dedicate my time entirely to competing.
If I’m lucky, I may finish the competition early, and CoudyNews will be back before 7:00 pm.
Breaking News and other items will still be posted.
Thanks everyone, and wish me luck!
You mean, if WE’RE lucky, you may finish early & CoudyNews will be back before 7:00 p.m.!! Good luck, Buck!!
Best of luck, Tim!!
lol, thanks! 🙂
What in the world is the Facebook Hacker Cup?
This is the first year for it. Facebook has began an annual ‘Hacker Cup’, which has brought nearly 100,000 computer programmers, coders, and ‘hackers’ from around the world to compete and see who is the best.
Only one can win.
Nearly 100,000 contestants entered the first round, and there is something like 4,000 at this time who are going on to the next round.
See below an actual problem that needed solved in the first round. Contestants must write a computer program to solve the problem. This is one of two that I completed out of three in the qualifying round. I’ll include my code also after the problem. I used php in this case, but in future rounds I don’t think php will be fast enough to compete, as the next rounds are more time-based than the qualifier was.
—-
Double Squares
A double-square number is an integer X which can be expressed as the sum of two perfect squares. For example, 10 is a double-square because 10 = 32+ 12. Your task in this problem is, given X, determine the number of ways in which it can be written as the sum of two squares. For example, 10 can only be written as 32 + 12 (we don’t count 12 + 32 as being different). On the other hand, 25 can be written as 52 + 02 or as 42 + 32.
Input
You should first read an integer N, the number of test cases. The next N lines will contain N values of X.
Constraints
0 ≤ X ≤ 2147483647
1 ≤ N ≤ 100
Output
For each value of X, you should output the number of ways to write X as the sum of two squares.
Example input
5
10
25
3
0
1
Example output
1
2
0
1
1
—-
My php code that solved this problem:
< ?php //ilabs double-square hackercup solution //load the data from input file function loadData($filename){ $fh = fopen($filename, "rb"); $data = fread($fh, filesize($filename)); fclose($fh); $array = explode("\n",$data); $rows = $array[0]; unset($array[0]); return array('rows' => $rows, ‘data’ => $array);
}
//fix for php is_int function
function is_intFix($int) {
return ctype_digit((string) $int);
}
//Too hard for brute force, switching to dp
function dp($number){
$result=0;
$counter = ceil(sqrt($number/2));
for ($i=0; $i< $counter; $i++) { $remainder = sqrt($number-($i*$i)); if (is_intFix($remainder)) { $result++; } } return $result; } //lets roll $data = loadData('input.txt'); foreach ($data['data'] as $y => $z){
echo dp($z).”\n”;
}
?>
As an after-thought for those who are familiar with programming, these problems could not be brute-forced. I originally whipped up a brute-force script that worked fine for the sample input, but the actual input.txt file given to me had integers that were waaay to long to be brute-forced. My script ran for nearly 15 minutes before I realized another method was in order. And since Facebook required you to submit your answer within 6 minutes, brute-force was not an option. Also, Facebook provided a clue to this with sub-title ‘too hard for brute-force, swithing to dp”.
With that I used a dynamic programming(dp) script, as seen in the above code.
Actually I should say, some coders claimed they were able to brute-force it with c++, but I find that hard to believe, although it might be possible on a wicked top-end machine.
No way to brute-force it with php though. I’d be shocked to see anyone pull that off.
We at our house are praying for you. You dint need luck you know what to do. Just like I tell my niece just relax and do it. You know the stuff. Will be waiting for results.
Thanks Zukowski!
It’s gonna be tough. I’m going up against some of the best in the world! 🙂
Sub-Round 1 = FAIL
– Got hung up on the multidimensional arrays somehow and did not finish in the top 1,000
Two more sub-rounds, two more chances… it should only get easier…
Here was the problem:
A lot of people at Facebook like to play Starcraft IIâ„¢. Some of them have made a custom game using the Starcraft IIâ„¢ map editor. In this game, you play as the noble Protoss defending your adopted homeworld of Shakuras from a massive Zerg army. You must do as much damage to the Zerg as possible before getting overwhelmed. You can only build two types of units, shield generators and warriors. Shield generators do no damage, but your army survives for one second per shield generator that you build. Warriors do one damage every second. Your army is instantly overrun after your shield generators expire. How many shield generators and how many warriors should you build to inflict the maximum amount of damage on the Zerg before your army is overrun? Because the Protoss value bravery, if there is more than one solution you should return the one that uses the most warriors.
Input
The first line of the input is the number of test cases, N. The next N lines each contain a test case, which consists of three integers, G, W and M, each separated by a single space. G is the cost to build a shield generator. W is the cost to build a warrior. M is the total amount of money you have to build warriors and shield generators.
Constraints
1 ≤ G ≤ 100
1 ≤ W ≤ 100
G + W ≤ M ≤ 1000000000000 (1012)
Output
For each test case, output a line containing a single integer A (for “awesome”), the number of revered warriors you choose to build.
Example Input:
5
15 10 658931394179
92 37 304080438521
39 100 972826846685
24 89 306549054135
64 16 254854449271
Example Output:
21964393379
1652611083
12472102915
6386403897
1991050385
—-
I came up with a great formula to calculate the problem, but I ran into trouble when loading up the multi-dimensional arrays to pass through the formula. The arrays should have been the easiest part, so a dumb error somewhere on my part that I have yet to determine.
Interesting is that I chose this problem out of 3 total, as I felt this was the simplest to solve, yet this was the least chosen problem amongst other contestants.
As usual, like in the first round, brute-force was my first instinct, simply checking every possible combination of warriors and shields for the most effective amount of damage, but the W constraint was a good indication that again brute-force would be too slow.
Due to problems with Facebook, they have postponed the competition until next weekend.
Alas, my arrays were fine. Facebook’s sample output was incorrect. Unbelievable really… and many unhappy programmers.
Facebook has postponed the competition until they can fix their mistakes. This has made Facebook look very bad to many programmers.
The behemoth Facebook, worth $50 billion, cannot get a simple mathematical equation correct… it is no wonder they are looking for hackers.
Look at this great blog explaining the solutions of qualification round of Hacker Cup.
Double Squares: http://itbhu.ac.in/codefest/blog/?p=159
Peg Game: http://itbhu.ac.in/codefest/blog/?p=172
Studious Student : http://itbhu.ac.in/codefest/blog/?p=180
Hope you will love this.