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.