Max Pair Matching#13026

Max Pair Matching (Editorial)

Author:

Anton Trygub

Solution 1. Let's assume that a_i \le b_i in each pair.

Clearly, from each of the pairs, we have to choose one number, with a plus or minus sign, so that exactly numbers are chosen with a plus and exactly with a minus, and we have to maximize the sum of these chosen numbers (with corresponding signs). That means, we have to choose pairs from which we will choose b_i, and pairs from which we will choose -a_i.

Now, let's consider S = \sum_{i = 1}^{2n} b_i. Each pair from which we choose -a_i instead of b_i, decreases this sum by a_i+b_i. So, it's optimal to choose -a_i from the pairs with the smallest sum a_i+b_i.

The overall algorithm would be to first make sure that a_i \le b_i, to sort by a_i+b_i, and take -a_i from the first pairs, and b_i from the last .

Solution 2. Let's draw a point c_i = \frac{a_i+b_i}{2} for each pair. Then w_{ij} = \frac{|a_i-b_i|}{2} + \frac{|a_j-b_j|}{2} + |c_i - c_j|.

Then we just have to find the partition into pairs for which the sum of |c_i - c_j| over pairs is the largest possible, and this is a well-known problem: just put match largest points with smallest points.