UVa 410

From Algorithmist
Jump to navigation Jump to search

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