Over the weekend, 25 of the world’s best programmers came to Facebook to compete for the title of World Champion in Facebook’s second-annual Hacker Cup finals.
Hacker Cup is a five-round programming competition designed to test the speed, accuracy, and ingenuity of programmers from around the world. This year, 8,000 people from 150 countries entered the qualification round in January. Over the course of three more rounds, the contestant pool was narrowed down to 25 finalists from Russia, Germany, Poland, Ukraine, China, South Korea, Japan, Taiwan, and the United States. Two months later, the finalists were flown out to Facebook to compete for the World Champion title.
The finalists were judged on accuracy and speed as they raced to solve three programming challenges in three hours. David Alves, the engineer behind Hacker Cup and the author of one of this year’s programming problems, kicked off the competition at 10:00 am Saturday morning. For the next three hours, the finalists tackled the problems, in order of easiest to most difficult. The problems were designed so the obvious solutions would take too long to implement in the time allotted, as a way to test the programmers’ creativity. To complete the challenges in time, the contestants needed to hack out new answers.
As each finalist completed a problem, a live scoreboard at the front of the room would update with their name and the problem they had solved. The contestants could also keep track of how their opponents were doing in a Facebook Group that the contestants used to ask clarification questions. The contestants were able to specify their programming language and dev environment preferences beforehand, and about 70% chose C++.
At 1:00 pm, an alarm sounded and the competition was over. The contestants, many of whom knew each other from previous programming competitions, immediately gathered around each other’s computers to discuss the different solutions they had tried. Then, after the traditional Facebook Hackathon Chinese food meal, everyone came back to hear the results. First place and $5,000 went to Roman Andreev of Russia, who completed one problem correctly in one hour and four minutes. Tomek Czajka from the United States got second place and $2,000 by a margin of one minute, finishing one problem correctly in one hour and five minutes. Third place and $1,000 went to Tiancheng Lou from China, who completed one problem correctly in one hour and 44 minutes.
To compete next year, keep an eye on the Facebook Hacker Cup Page and in the meantime, try your hand at the practice problem below:
——-
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.
