Peter Mitrichev - Facebook Hacker Cup winner

The results of the Facebook Hacker Cup. The competition, which was attended by 11,768 people from around the world, is held in the format of solving complex algorithmic problems in three rounds "for departure". Twenty-five finalists were invited to 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 from China, Germany, the Netherlands, Singapore, Switzerland and Ukraine got into the final. All of them were able to spend 2 days in the Facebook office: 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 decision is ready for each of the tasks, and at the end of the two-hour round the total number of points for each participant is calculated.



Task conditions can be viewed on the Facebook Engineering blog (however, if there is a demand - I can try to translate them later).



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



UPD # 1 - interesting details from Skiminok :

I also add that there was an amazing intrigue about the winner.

Mitrichev's main rival is Lou Tian Cheng, also known as ACRush.

The principle of this competition is such that each of the three tasks is estimated at 1 point, and in the standings, the one who has more tasks is higher, and with equality the one who has the total time spent on each task since the beginning of the round is lower. In this case, the final check of answers occurs only after the round ends.



So, ACRush was ahead of Mitrichev throughout the whole round. Mitrichev passed the same tasks, in number they were always the same - but ACRush passed them faster, we did not even hope to win Petit. And then the round ends, the final check takes place, and ACRush drops one of the tasks with the wrong answer, and he ends up with two points, and descends into two places, skipping ahead of Petya with three solved more slowly, but correctly.



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



Task 1. The game of aliens.



On the Unknown Planet, aliens traditionally play a game called Loiten. It is attended by two players who take turns. In front of the players, N baskets of apples are lined up in a row. They are numbered from left to right by integers starting with 1.



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



You are familiar 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 World Championship. The day before the game, he somehow found out how many apples would be in each of the baskets. Unfortunately, his memory is not too good, and he forgot the number of apples in the basket under the number P. He remembers only that this number does not exceed F in absolute value.



Now, he asks you to calculate his chances of winning. So good players pass to the championship finals that they always make only optimal moves to maximize their chance of winning. If no player can win, a draw is counted. You need to know the number of possible quantities of apples in basket No. P , for which Popo wins. Popo is also confident that he is the one who makes the first move in the game.



Input data

The first line of input contains a single integer T , the number of tests. Each test starts 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 N integers - the number of apples in the respective baskets. The Pth number in this line is a positive integer F , corresponding to the limit on the number of apples in the Pth basket.



Output

The output file should contain T lines, one per test. Each line contains the answer to the corresponding test, the number of possible winning values ​​for the number of apples for the Pth basket.



Restrictions

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 in absolute terms does not exceed 1,000,000,000,000.



Task 2. Safe place.

On the way to the 295th anniversary of the Big Galactic Party, you were suddenly unceremoniously thrown out of hyperspace and now, according to sensors, you are surrounded by N space bombs. Undoubtedly, you fell 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. You invisible rival created a cosmic anomaly in the form of a cube, beyond which you can not fly, so that as a variant of the location only points within this cube are available to you.



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



Input data

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 should contain T lines, one per test. Each line contains the square of the distance to the nearest bomb from the safest point in the cube.



Restrictions

T = 50

1 ≤ N ≤ 200

All coordinates of the bombs are in the range [0, 1000] inclusive.



Task 3. Party time

You are having a party for your friends, but since not all of your friends know each other, you fear 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 should be invited to make a great party?



Fortunately, you know the details of all the relationships between your friends and your friends. In terms of graph theory, there is a subgraph G of a 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 were able to establish exactly how much food each person in G will eat at the party, if invited.



You want to choose a lot of guests from G. This host of guests must contain all your friends, and, in addition, the subgraph G , formed by 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 such a large number of guests so that the total amount of food needed was as small as possible. If this can be achieved in several different ways, the method with the fewest guests is preferred.



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



Input data

The first line of input contains a single integer T , the number of tests. The first line of each test contains three integers: N is the number of vertices in G , F is the number of your friends, and M is the number of edges in G. Next are M lines, two integers each. The first such line contains two different integers u and v , which means mutual friendship between man number u and man number v . After that, the last line of the test contains N integers separated by 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 that meets 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.