Solution to Problem 1: Railway Catering Contracts
Let p_1, p_2, ... , p_N be the expected profits at the N stations. Our task is to identify i,j with i≤j such that j-i+1 is at least K and and p_i + p_{i+1} ... + p_j is maximised. The brute force idea would be to pick every such pair (i,j) and find the sum of the sequence p_i + p_{i+1} ... p_j and take the maximum amongst these. There are C(N,2) pairs to consider and the computation of the sum of such a segment could take up to N additions. Thus the naive algorithm takes about N*N*N steps. Let us first consider a simpler version of the problem where K is fixed to be 1. Thus, we are interested in the maximum possible sum among all subsequences (i.e. sequences of the form p_i,p_{i+1} ... p_j for 1≤i≤j≤N). Can we do better than the naive algorithm mentioned above? Yes, and the trick is use dynamic programming. Let Best(j) be the maximum possible sum among all subsequences of the form p_i, p_{i+1} ... p_j (with i≤j). Can we compute Best(j+1) from Best(j)? Suppose p_i + p_{i+1} + ... + p_{j-1} + p_j has maximum sum among such sequences with i<j (i.e. sequences ending at p_j and whose length is at least 2). Then, we claim that p_i + p_{i+1} ... p_{j-1} = Best(j-1). Otherwise p_i + p_{i+1} ... p_{j-1} < Best(j-1). Let p_m + p_{m+1} ... p_{j-1} = Best(j-1). Then, p_m + p_{m+1} ... p_{j-1} + p_j > p_i + p_{i+1} ... p_{j-1} + p_j. which contradicts our assumption about i. Thus, the maximum sum among all sequences of the form p_i + p_{i+1} ... p_{j-1} + p_j with i<j is Best(j-1) + p_j. The only other sequence ending at p_j is the sequence consisting of p_j alone! Thus, Best(j) = Maximum( Best(j-1) + p_{j}, p_{j} ) Hence, the value of Best(j) can be computed for all values of j in time proportional to N and the maximum among these is the desired answer. This algorithm would take take time proportional to N. Now let us go back to the original problem where we are also given K and we are to restrict ourselves to sequences of the form p_i + p_{i+1} ...+ p_j with j-i+1 ≥ K. Let BestK(j) be the maximum possible sum among all sequences of the form p_i + p_{i+1} ... + p_j with j-i+1 ≥ K (or equivalently i ≤ j-K+1). Of course, BestK(j) makes sense only for j ≥ K. We apply the same idea as above, that is to first consider all the sequences whose length exceeds K and those (exactly one) with length K. We claim that if p_i + p_{i+1} + ... + p_{j-1} + p_j has maximum sum among all sequences with i < j-K+1 (i.e. among all sequences of length > K and ending at p_j) then p_i + p_{i+1} ... p_{j-1} = BestK(j-1). Otherwise, p_i + p_{i+1} ... p_{j-1} < BestK(j-1). and there is some m ≤ (j-1)-K+1 with p_m + p_{m+1} ... p_{j-1} = BestK(j-1). Thus, p_m + p_{m+1} ... p_j > p_i + p_{i+1} ... + p_j and m ≤ j-K and hence m < j-K+1 contradicting the defining property of i. Hence, the claim is proved. The only other sequence of length K or above ending at p_j is the sequence p_{j-K+1} + p_{j-K+2} ... p_j, the unique sequence of length K ending at p_j. Suppose SumK(j) is the sum of the unique sequence of length K ending at p_j then, BestK(j) = Maximum( BestK(j-1) + p_j, SumK(j) ) Thus, if the values of SumK are known apriori then the value of BestK(j) for all j can be computed using about N operations. Notice that the value of SumK(j) can be computed for all j in time proportional to N using the following recurrance: SumK(j) = SumK(j-1) + p_j - p_{j-K} Thus, we can compute the values of BestK(j) for all j in time proportional to N and the maximum among these yields the desired answer. We now describe below the complete algorithm described above. Here we have combined the computation of BestK(j) and SumK(j) into a single loop. ------------------------------------------------------------------------- /* We assume that there is an array P[1 ... N] with the profits and that the variables N and K have been set to the appropriate value */ sum = 0; for j=1 to K do sum = sum + P[i]; SumK[K] = sum; // SumK[K] is set. BestK[K] = sum; // for j=K, BestK[K] = SumK[K] Ans = sum; // The best BestK[j] so far. for j=K+1 to N do { SumK[j] = SumK[j-1] + P[j] - P[j-K]; BestK[j] = Maximum( BestK[j-1] + P[j], SumK[j] ) if (Ans < BestK[j]) Ans = BestK[j]; } Print Ans; ----------------------------------------------------------------------