a bit of uva : UVa 11389 - The Bus Driver Problem (Greedy Algorithm)

Problem:
UVa 11389 - The Bus Driver Problem

Summary:
Given a function
\( f(x) = \begin{array}{cc} x & \text{if x } \geq 0 \\ 0 & \text{if x } < 0 \end{array} \)
and two ordered sets \(a_i\) and \(b_i\), find the minimum S = \(r*\sum{f(a+b-d)}\) for some \(r,d \geq 1\).

There is a large set of possibilities for pairing \(a\) and \(b\), but there is an intuitive (or maybe not) arrangement for a and b that can hopefully minimize S, that is by first sorting \(a_i\) and \(b_i\), and pairing the largest a with the smallest b sequentially. The code is very short, and it is indeed the solution. Now it remains to prove that our algorithm is really correct.

To do so, we consider the case when we only have \(\{a_1, a_2\}\) and \(\{b_1, b_2\}\), with some value \(d\). For the ease of discussion, suppose that \(a_1 \leq a_2\) and \(b_1 \leq b_2\) (if not, we can swap the values to obtain this configuration). We need to prove that \(S = f(a_1 + b_1 - d) + f(a_2 + b_2 - d)\) is the smallest S possible, that is,

Lemma 1:
For any a, b, and d, we have \(S \leq T\) where \(T = f(a_1 + b_2 - d) + f(a_2 + b_1 - d)\).

Proof:
Firstly observe that \(a_1 + b_1 \geq a_1 + b_2\) and \(a_2 + b_2 \leq a_2 + b_1\).
Consider a few cases:
1. If \(a_1 + b_1 - d > 0\) and \(a_2 + b_2 - d > 0\), then
\(S = (a_1 + b_1 - d) + (a_2 + b_2 - d) \)
\(S = (a_1 + b_2 - d) + (a_2 + b_1 - d) \)
\(S \leq f(a_1 + b_2 -d) + f(a_2 + b_1 - d) = T\)

2.If \(a_1 + b_1 - d < 0\) and \(a_2 + b_2 - d > 0\) or \(a_1 + b_1 - d < 0\) and \(a_2 + b_2 - d < 0\), the  proposition is trivially true.

3. Lastly, if  \(a_1 + b_1 - d > 0\) and \(a_2 + b_2 - d < 0\), notice that \(a_1 + b_1 > a_2 + b_2\). We show that \(a_2 + b_1\) cannot be less than \(d\) (since otherwise, S will be more than T). Suppose \(a_2 + b_1 < d\), then \(d \leq a_1+b_1 \leq a_2 + b_1 < d\), a contradiction. As such the proof is complete.

Now, using the above lemma, we can prove that our arrangement is indeed the smallest. Consider a pairing \(\{(a_1,b_1'), (a_2,b_2'), \ldots, (a_n,b_n')\}\) for some arrangement of b. We can find a pair of \((a_i,b_i)\) and \((a_j,b_j)\) such that \(b_i < b_j\) (since otherwise b is already sorted in reverse order). Applying Lemma 1, we will obtain a new arrangement with a decreasing total sum, until we cannot find anymore such pairs, in which we obtain the desired arrangement of a and b! :D