# UVa 410

## 410 - Station Balance[edit]

## Summary[edit]

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[edit]

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 {}, we match with , with , ..., with , ..., 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 {}. We have . In the k'th step, we try to match . Let us just look into the first step, all the rest steps are similar. By the Greedy algorithm described above, the best match of is . Let us denote it by { }. We want to show that the match { } is at least as good as any other match { }, .

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

and .

Notice that

- and
- , and
- .

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

.

So, we know that { } is optimal, similarly { , }, ....

## Gotchas[edit]

- 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[edit]

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

## Output[edit]

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