Petr Mitrichev - winner of the Facebook Hacker Cup

Summed up the Facebook Hacker Cup. The competition, which was attended by 11768 people from all over the world, is held in the format of solving complex algorithmic problems in three rounds “on the fly.” Twenty-five finalists were invited to the Facebook headquarters in Palo Alto for the final match.

7 representatives from Poland, 6 from Russia, 4 from the USA, 2 from Japan and one each from China, Germany, the Netherlands, Singapore, Switzerland and Ukraine each got to the final. All of them were able to spend 2 days in the office of Facebook: to meet with the developers, dine at Cafe X, play Catan and try to ride on RipStik .

Participants had the opportunity to choose a machine (Mac or PC), after which the final round began. The finalists were required to solve three algorithmic problems: Party Time, Safest Place and Alien Game - as quickly as possible.

The results are presented to the court as soon as the solution for each of the tasks is ready, and at the end of the two-hour round, the total number of points for each participant is calculated.

You can see the conditions of the tasks on the Facebook Engineering blog (however, if there is demand, I can try to translate them later).

As a result, our compatriot Pyotr Mitrichev ( participant and winner of many similar competitions ) went to the “gold” .

UPD # 1 - interesting details from Skiminok :
I add that there was a terrific intrigue regarding the winner.
Mitrichev’s main rival is Lou Tian Cheng, also known as ACRush.
The principle of this competition is that each of the three tasks is evaluated at 1 point, and in the standings the one with the most tasks is passed, and if it is equal, the one with the total time spent on each task from the beginning of the round is lower. In this case, the final check of the answers occurs only after the round is over.

So, ACRush was ahead of Mitrichev throughout the round. Mitrichev passed the same tasks, in terms of quantity they were always the same - but ACRush passed them faster, we no longer hoped for Petit's victory. And then the round ends, the final check takes place, and ACRush drops one of the problems with the wrong answer, and he finds himself with two points, and falls into two places, letting Petya forward with three solved more slowly, but correctly.

UPD # 2 - translation of the tasks themselves (thanks again to Skiminok )

Task 1. The game of aliens.

On an Unknown planet, aliens traditionally play a game called Loiten. It involves two players who take turns. N players are lined up in front of the playersbaskets with apples. They are numbered from left to right by integers, starting with 1.

Each move consists in the player choosing one of the baskets, which is not the first and not the last in the row, and in which the number of apples is positive, and transfers all the apples in this basket to the adjacent left basket, and at the same time simultaneously transfers them all to the basket next to the right. Yes, on this really strange planet, the number of apples can be negative. So, if there are 3 consecutive baskets in which there are x , y , z apples, respectively , then you can make a move with them if y is greater than zero. As a result, after the move, the baskets will have the following quantities: x + y , - y, z + y . The player who cannot make the move loses.

You are acquainted with one of the inhabitants of the Unknown Planet, named Popo. He is a great player in Loiten, and made it to the finals of the Loiten planet championship. The day before the game, he somehow figured out how many apples will be in each of the baskets. Unfortunately, it's not a good memory, and he forgot the number of apples in a basket under the number P . He only remembers that this number does not exceed F in absolute value .

Now, he asks you to calculate his chances of winning. So good players go to the finals of the championship that they always make only the best moves to maximize their own chance of winning. If no player can win, a tie is counted. You need to find out the number of possible quantities of apples in basket No. P at which Popo wins. Popo is also sure that it is he who makes the first move in the game.

Input
The first line of input contains a single integer T , the number of tests. Each test begins with a line containing two integers: N , the number of baskets, and P , the number of the basket with an unknown number of apples. The next line contains Nintegers - the number of apples in the respective baskets. P th number in this row - a positive integer F , corresponding to a restriction on the number of apples in P th basket.

Output
The output file should contain T lines, one per test. In each row, - an answer to the appropriate test, the number of possible winning numbers apples values P th bin.

Limitations
T = 50
1 ≤ P ≤ N ≤ 2,000.
1 ≤ F ≤ 1,000,000,000,000.
Before the start of the game, the number of apples in each basket does not exceed 1,000,000,000,000 in absolute value.

Task 2. A safe place.
On the way to the 295th anniversary of the Big Galactic Party, you were suddenly unceremoniously thrown out of hyperspace and now, if you believe the sensors, you are surrounded by N space bombs. Undoubtedly, you have fallen into a trap set up by some unknown vile enemy, you cannot return to hyperspace, and now you have to find the safest place in the vicinity to survive the explosion of all bombs. An invisible rival has created a space anomaly in the form of a cube beyond which you cannot fly out, so that as an option for your location, only points within this cube are available to you.

Before all the bombs simultaneously explode, you have enough time to get to any whole point within the cube [0, 0, 0] - [1000, 1000, 1000], inclusive. You need to find a point at which the distance to the nearest bomb is maximum, as your intuition tells you that this will be the safest place.

Input
The first line of input contains a single integer T , the number of tests. Each test begins with an integer N , the number of bombs, followed by 3 * N integers that specify the coordinates of each bomb.

Output
The output file must contain Tlines, one per test. On each line is the square of the distance to the nearest bomb from the safest point in the cube.

Limitations
T = 50
1 ≤ N ≤ 200
All coordinates of the bombs lie within [0, 1000] inclusive.

Task 3. Time for a party
You have a party for your friends, but since not all of your friends know each other, you are afraid that some of them may not like the party. To avoid this situation, you also decided to invite some friends of your friends. But who exactly to invite to get a great party?

Fortunately, you know the details of all the relationships between your friends and the friends of your friends. In terms of graph theory, there is a subgraph Ga social graph whose vertices correspond to your friends and their friends (not counting you), and the edges of the graph mean mutual friendship. Moreover, you managed to establish exactly how much food each person from G would eat at the party if invited.

You want to choose a variety of guests from the G . This set of guests must contain all of your friends, and in addition, the subgraph G formed by the guests must be connected. It seems to you that this will be enough for everyone to enjoy the party, as any two guests will have something to talk about ...

To save money, you decided to choose so many guests so that the total amount of food needed is as small as possible. If this can be achieved in several different ways, the method with the least number of guests is preferred.

People / peaks in your subset G of the social graph are numbered from 0 to N - 1. Also, for your convenience, your friends have numbers from 0 to F - 1, where F is the number of friends you want to invite. We can also assume that G is always connected. Once again, we remind you that you are not represented in G in any way .

Input
The first line of input contains a single integer T, number of tests. The first line of each test contains three integers: N - the number of vertices in G , F - the number of your friends, and M - the number of edges in G. Next, M lines, two integers in each. The 1st such line contains two different integers u and v , which means mutual friendship between person No. u and person No. v . After that, the last line of the test contains N integers through spaces, where the i- th number is the amount of food needed by person No. i .

Output
The output file should contain T lines, one per test. Each line contains two numbers separated by a space: the minimum total amount of food for a party meeting the above conditions, and the minimum number of people at such a party.

Restrictions
T = 50
1 ≤ F ≤ 11
F ≤ N -1
2 ≤ N ≤ 250
N -1 ≤ M ≤ N * ( N - 1) / 2
G is connected and does not contain loops or multiple edges.
For each person, the amount of food he needs is an integer from 0 to 1000 inclusive.