# UVa 410

## Summary

Mathematically, given a list of 2n integers, we need to match them in pairs such that the imbalance factor defined in the problem is minimum.

## Explanation

Since each chamber can only hold at most 2 specimens, greedy algorithm works here. Let n be the number of chambers. To simplify, we always assume that there are 2n specimens. If there are not so many, we can zero-padding it by adding some specimens of mass 0. Let the sorted list of specimen masses be {${\displaystyle A_{1},A_{2},...,A_{2n}}$}, we match ${\displaystyle A_{1}}$ with ${\displaystyle A_{2n}}$, ${\displaystyle A_{2}}$ with ${\displaystyle A_{2n-1}}$, ..., ${\displaystyle A_{i}}$ with ${\displaystyle A_{2n-i}}$, ..., and put them into separate chambers. This way, the imbalance is guaranteed to be the smallest.

Why does Greedy algorithm works for this problem? Followed is a sketch of a proof. We exploit the fact that each chamber can only hold at most 2 specimens.

Let n the number of chambers and the zero-padded sorted list of specimen masses be {${\displaystyle A_{1},A_{2},...,A_{2n}}$}. We have ${\displaystyle A_{1}. In the k'th step, we try to match ${\displaystyle A_{k}}$ . Let us just look into the first step, all the rest steps are similar. By the Greedy algorithm described above, the best match of ${\displaystyle A_{1}}$ is ${\displaystyle A_{2n}}$. Let us denote it by { ${\displaystyle (A_{1},A_{2n})}$ }. We want to show that the match { ${\displaystyle (A_{1},A_{2n})}$ } is at least as good as any other match { ${\displaystyle (A_{1},A_{j})}$ }, ${\displaystyle 1.

Suppose in the match { ${\displaystyle (A_{1},A_{j})}$ }, ${\displaystyle A_{2n}}$ is matched to ${\displaystyle A_{i}}$, ${\displaystyle 1 and ${\displaystyle i\not =j}$. Let us denote it by { ${\displaystyle (A_{1},A_{j})}$, ${\displaystyle (A_{i},A_{2n})}$ }. We claim that the match { ${\displaystyle (A_{1},A_{2n})}$, ${\displaystyle (A_{i},A_{j})}$ } is at least as good as the previous one. Since we get the new match by simply switching ${\displaystyle A_{j}}$ and ${\displaystyle A_{2n}}$, the imbalance contributions from the other chambers are not changed. So, let M be the average chamber mass, we are actually comparing

${\displaystyle |A_{1}+A_{j}-M|+|A_{i}+A_{2n}-M|}$ and ${\displaystyle |A_{1}+A_{2n}-M|+|A_{i}+A_{j}-M|}$.

Notice that

• ${\displaystyle A_{1}\leq A_{i},A_{j}\leq A_{2n}}$ and
• ${\displaystyle A_{1}+A_{j}\leq A_{1}+A_{2n}}$ , ${\displaystyle A_{i}+A_{j}\leq A_{i}+A_{2n}}$ and
• ${\displaystyle 2*A_{1}\leq M\leq 2*A_{2n}}$.

By studying the cases of different ranges of A. It is not hard to prove (details ignored)

${\displaystyle |A_{1}+A_{j}-M|+|A_{i}+A_{2n}-M|\leq |A_{1}+A_{2n}-M|+|A_{i}+A_{j}-M|}$.

So, we know that { ${\displaystyle (A_{1},A_{2n})}$ } is optimal, similarly { ${\displaystyle (A_{1},A_{2n})}$, ${\displaystyle (A_{2},A_{2n-1})}$ }, ....

## Gotchas

• As long as the matching is correct, it does not matter which chamber you put a pair into.
• Do not forget the space before the chamber ID.

## Input

2 3
6 3 8
3 5
51 19 27 14 33
5 9
1 2 3 5 7 11 13 17 19


## Output

Set #1
0: 6 3
1: 8
IMBALANCE = 1.00000

Set #2
0: 51
1: 19 27
2: 14 33
IMBALANCE = 6.00000

Set #3
0: 1 17
1: 2 13
2: 3 11
3: 5 7
4: 19
IMBALANCE = 11.60000