Indian National Olympiad in Informatics

Online Programming Contest, 5-6 March 2005

IARCS home > OLYMPIAD

Advanced Division

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;

----------------------------------------------------------------------




Copyright (c) IARCS 2003-2018;   Last Updated: 07 Sep 2005