USACO - Job Processing

We can calculate the earliest finish time for each job with machine A or B independently in a greedy way. For example, with each job to be delivered, we use free_x[i] to represent when will machine i of type x will be available for it, and rate_x[i] to denote the processing rate of machine i of type x. For job j, find the smallest free_x[i] + rate_x[i], assign it to done_x[j] which is the finish time for job j using machine type x alone, then update free_x[i] with value done_x[i].

We get done_a[1..njob] and done_b[1..njob] with this method. Max(done_a[1..njob]) should be the answer to the first question of the problem. To find the answer to the second question, we can use yet another greedy approach which is introduced by the following lemma:

For two arrays A[1..n] and B[1..n] of positive integers and also of the same size, with A[1..n] and B[1..n] already sorted increasingly and decreasingly respectively, and A'[1..n] and B'[1..n] to represent any other possible permutations of the elements of the two arrays, we say Max(A[i]+B[i]) will be no bigger than Max(A'[i]+B'[i]).

We can prove this lemma by induction. It's trivial for n=1. Assume it's true for size n-1, then for arrays of size n, we first remove the last element of each array leaving A[1..n-1] and B[1..n-1] with the relation Max(A[i]+B[i]) <= Max(A'[i]+B'[i]) for i<n. We now need to consider A[n]+B[n] with respect to Max(A[i]+B[i]).

1. If A[n] + B[n] >= Max(A[i]+B[i]), then Max(A[i]+B[i]) = A[n] + B[n] for i<=n. Since B[n] is the smallest value of B'[1..n], we know A[n] + B[n] <= Max(A'[i]+B'[i]). Combine the two relations we get Max(A[i]+B[i]) <= Max(A'[i]+B'[i]) for i<=n.
2. If A[n] + B[n] < Max(A[i]+B[i]), we need to further divide this situation into 3 sub-problems. Assume A'[k] + B'[k] = Max(A'[i]+B'[i]) for i<n.
• Pair A[n] with B'[k], then A[n] + B'[k] >= Max(A'[i]+B'[i]) since A[n] > A'[i] for all i<n.
• Pair B[n] with A'[k], i.e. we substitute A[n] for A'[k] in the original A'[1..n-1], Then how can it possible that Max(A'[i]+B'[i]) can be smaller for i<n since the biggest A[n] is in.
• Leave A'[k] + B'[k] as it is. It's apparent that this won't lower the Max(A'[i]+B'[i]) for i<=n.

Then we can conclude that it is true Max(A[i]+B[i]) <= Max(A'[i]+B'[i]) for i<=n.

The answer for the second question then is Max(done_a[i] + done_b[njob-i]) for 1<=i<=njob. Do you get it? Here is a digram from the ANALYSIS of the problem by USACO staff.

I got information said this problem is related to a more general algorithm named "Johnson" for job scheduling. Links to Wikipedia are listed below.

1. Johnson's Rule, http://en.wikipedia.org/wiki/Johnson%27s_Rule
2. Job shop scheduling, http://en.wikipedia.org/wiki/Job_shop_scheduling

Sample code.