Ruskie Java coder lifts inaugural Facebook Hacker Cup

C++ men squashed

The sliding glass doors at the entrance of Facebook headquarters don't say Facebook. They say HACK – in big, bold, black letters, two on each door. The company goes out of its way to cultivate an extreme developer culture built around the non-pejorative definition of the word. "There's this whole definition that engineers have for themselves," Mark Zuckerberg recently told an incredulous middle-aged American newswoman. "It's very much a compliment when you call someone a hacker. To hack something means to build something very quickly. In one night, you can sit down and you can churn out a lot of code, and at the end, you have a product."

The Hacker Cup cup

These all-night hackathons are a regular part of life inside the social networking behemoth, as millions of mainstream movie goers are very much aware. And now, following the lead of Google and so many others, Facebook has turned the idea into an official coder v coder competition, complete with an unwieldy trophy and some cash prizes.

The first annual Facebook Hacker Cup began in January as an online competition, with nearly 12,000 developers from across the globe joining the fray. After three elimination rounds, the 12,000 were whittled down to twenty-five, and on Saturday morning – at the very un-developer-friendly hour of 9am – these coders descended on Facebook headquarters in Palo Alto for the final geekoff. The twenty-five finalists included seven developers from Poland, six from Russia, four from the US, and exactly zero from the United Kingdom.

These alpha programmers weren't competing to build applications. This isn't a contest that relies on judges. It's not like Rails Rumble or Node Knockout or synchronized swimming. It's like Google Code Jam. Or TopCoder. Contestants were asked to solve algorithmic problems. "It's almost more of a math contest than a programming contest," said Facebook engineer David Alves, who helped organize the competition and write the problem sets. In the end, there are only right answers and wrong answers.

The finalists were given two hours to solve these three problems:

• Problem 1: Alien Game

  Aliens on the Unknown planet have a tradition of playing a game called Loiten. It is played by two players who alternate turns. There are N buckets with apples standing in one line in front of the players. They are numbered from left to right with integers starting from 1. In one turn a player can select one of the buckets, which is not the first and not the last and has a positive number of apples in it, and move all of that bucket's apples to the bucket adjacent to the left and at the same time move all of them to the bucket adjacent to the right. That's right, the number of apples can be negative as it is a really strange planet. Thus, if there are 3 consecutive buckets with the number of apples being x, y, z, then you can perform the move if y is greater than zero. The resulting capacity of the buckets will be as follows: x+y, -y, z+y. The first player who can't make a move loses. You happen to know one of the aliens from the Unknown planet, named Popo. He is a very good Loiten player, and has reached the Loiten Finals. On the day prior to the game, he found out the number of apples in each of the buckets. Unfortunately, his memory is not that good, and he can't remember the number of apples in the P-th bucket. He just remembers that it is a number with absolute value not greater than F. Now, he is asking you to help him to calculate his chances. The players at the Finals are so good that they only make optimal moves to maximize their chance of winning. If neither player can win, the game is considered a draw. You are to find the number of possible apple counts for the bucket with an unknown number of apples where Popo will win. Popo is also sure that he is the one to make the first turn.

  Input The first line of the input file consists of a single number T, the number of test cases. Each test case begins with a line containing two integers N, the number of buckets and P, the number of the bucket with the unknown amount of apples. It is followed by a line containing N integers, the numbers of apples in the corresponding buckets. The Pth number on this line is the positive integer F and corresponds to the constraint on the number of apples in the P-th bucket.

  Output Output T lines, with the answer to each test case on a single line, the number of possible values for unknown bucket.

  Constraints T = 50 1≤ P ≤ N ≤ 2,000. 1≤ F ≤ 1,000,000,000,000. The number of apples in each bucket at the start of the game has an absolute value not greater than 1,000,000,000,000.

• Problem 2: Safest Place

  While en route to the 295th annual Galactic Dance Party on Risa, you find yourself unceremoniously yanked out of hyperspace and, according to your sensors, surrounded by N space bombs. Apparently caught in a trap laid out by some dastardly and unknown enemy, and unable to return to hyperspace, you must find the safest place in the vicinity to weather the detonation of all the space bombs. Your unseen opponent has constructed a cube-shaped space anomaly that you are unable to leave, so your options are limited to points within that cube. Before the bombs explode (all simultaneously), you have just enough time to travel to any integer point in the cube [0, 0, 0]-[1000, 1000, 1000], both inclusive. You must find the point with the maximum distance to the nearest bomb, which your captain's intuition tells you will be the safest point.

  Input The first line of the input file consists of a single number T, the number of test cases. Each test consists of single number N, the number of bombs, followed by 3*N integers describing the positions of the bombs.

  Output Output T integers, one per test case each on its own line, representing the square of distance to the nearest bomb from the safest point in the cube.

  Constraints T = 50 1 <= N <= 200 All bombs coordinates will be in [0, 1000], both inclusive.

• Problem 3: Party Time

  You're throwing a party for your friends, but since your friends may not all know each other, you're afraid a few of them may not enjoy your party. So to avoid this situation, you decide that you'll also invite some friends of your friends. But who should you invite to throw a great party? Luckily, you are in possession of data about all the friendships of your friends and their friends. In graph theory terminology, you have a subset G of the social graph, whose vertices correspond to your friends and their friends (excluding yourself), and edges in this graph denote mutual friendships. Furthermore, you have managed to obtain exact estimates of how much food each person in G will consume during the party if he were to be invited. You want to choose a set of guests from G. This set of guests should include all your friends, and the subgraph of G formed by the guests must be connected. You believe that this will ensure that all of your friends will enjoy your party since any two of them will have something to talk about... In order to save money, you want to pick the set of guests so that the total amount of food needed is as small as possible. If there are several ways of doing this, you prefer one with the fewest number of guests. The people/vertices in your subset G of the social graph are numbered from 0 to N - 1. Also, for convenience your friends are numbered from 0 to F - 1, where F is the number of your friends that you want to invite. You may also assume that G is connected. Note again that you are not yourself represented in G.

  Input The first line of the input consists of a single number T, the number of test cases. Each test case starts with a line containing three integers N, the number of nodes in G, F, the number of friends, and M, the number of edges in G. This is followed by M lines each containing two integers. The ith of these lines will contain two distinct integers u and v which indicates a mutual friendship between person u and person v. After this follows a single line containing N space-separated integers with the ith representing the amount of food consumed by person i.

  Output Output T lines, with the answer to each test case on a single line by itself. Each line should contain two numbers, the first being the minimum total quantity of food consumed at a party satisfying the given criteria and the second the minimum number of people you can have at such a party.

  Constraints T = 50 1 ≤ F ≤ 11 F ≤ N-1 2 ≤ N ≤ 250 N-1 ≤ M ≤ N * (N - 1) / 2 G is connected, and contains no self-loops or duplicate edges. For each person, the amount of food consumed is an integer between 0 and 1000, both inclusive.

Contestants could use any language and any tool to build a program capable of solving these problems. And once they actually downloaded the input data and plugged it into their code, they had six minutes to produce an answer. Naturally, the coder with the most correct answers wins, with ties decided by how quickly each contestant delivered each solution.

Most contestants coded in C++, as you might expect, given the tight time frame. And all twenty-five coded atop, um, Windows machines. Facebook offered a choice of Windows or Mac, and according to Alves, no one wanted a Mac. "I can't really explain it," he said. "It surprised me." Several developers told us they merely chose a Windows machine so they could put Linux on it. But some were happy with unadulterated Windows. Chinese developer Tiancheng Lou coded on Windows with Visual Basic, and Russian Petr Mitrichev, opting for Java, ran IntelliJ IDEA on the Microsoft OS.

"[IntelliJ] runs the same on all platforms," he told us, "so I don't care what OS I use."

After two hours, only three coders produced answers to all three problems, including Tiancheng Lou and Petr Mitrichev; four finished two; and ten finished one.

But not all solutions were correct. Lou's answer to "Safest Place" missed the mark, and he dropped to third place, handing the trophy – and $5,000 – to Mitrichev. Asked why he coded in Java when most contestants used C++, Mitrichev told us: "It's harder to make a mistake in Java." Asked how many of these of hackathons he's competed in, he said: "Thousands." In 2006, he won the Google Code Jam.

Petr Mitrichev

You can find Mitrichev's solutions to the three problems here (registration required).®