Internet Problem Solving Contest

• Correct output for H1
• Correct output for H2
• C++ program solving both subproblems

For the easy subproblem a simple brute-force solution was sufficiently fast. Let us denote Adam’s team by A and Betka’s team by B. Each of the other n − 2 children joins either A or B, so there are 2^n − 2 ways to form the teams. We can afford to try them all, every time computing the strengths of the teams in O(m) by processing the list of friendships.

To solve the hard subproblem we will consider Adam’s and Betka’s teams composition preferences separately. Let us start with Adam – he wants to maximize the sum of the teams’ strengths. If we regard pairs of friends as edges of a graph, his criterion corresponds to finding a partition of vertices into two sets A, B which maximizes the number of edges within each part. This is of course equivalent to minimizing the number of edges between A and B. Our task is therefore to find a minimum s-t cut where the source and sink are the vertices corresponding to Adam and Betka respectively. There are more efficient algorithms to solve this problem, but even our lazy implementation of the Ford-Fulkerson algorithm with time complexity O(nm) was fast enough.

Now we move on to Betka’s criterion – she would like the absolute difference between the teams’ strengths to be as small as possible. Let us consider any partition of the vertices into teams A and B. For any edge and any of its two endpoints, we add to a running total 1/2 if the endpoint is in A and  − 1/2 if it is in B. Clearly, the final value we obtain equals
$$ \frac{1}{2} \cdot \left( \sum_{v \in A} d_v - \sum_{v \in B} d_v \right) $$
where d_v denotes the degree of vertex v. Moreover, this value is exactly the strength of team A minus the strength of team B: For any edge within A we have a 1, for any edge within B we have a  − 1, and for any edge between A and B we have a 0.

This observation offers us another way how to phrase the problem. We can represent each vertex by a single number (its degree) and then look for a partition which minimizes the absolute difference between the sums of the numbers in each part. Equivalently, we want to find a subset of the vertices such that its sum is as close to half the total sum as possible. We could compute which sums it is possible to achieve by listing all subsets, but using dynamic programming is much faster: If we denote by S = {s₁, …, s_|S|} the set of sums obtainable from numbers d₁, …, d_k − 1, then the sums obtainable from d₁, …, d_k − 1, d_k are S ∪ {s₁ + d_k, …, s_|S| + d_k}. Because the sum of all degrees equals 2m, each set has size O(m) and our solution runs in time O(nm).