Indian Computing Olympiad

Sliding Window Algorithms

Buying two empty plots

We have a sequence of plots as before, but we want to build two buildings requiring K acres each, so we want to buy two such subsections so that the number of plots in the two subsections is minimized.

Note that the two subsections we require must be disjoint, so it is not enough to pick the two best subsections overall.

Solution

Naive solution

Find all possible K length subsections. We have to find a pair that does not overlap with minimum combined length. Check this property for all possible pairs. Can we avoid checking all pairs?

Hint

For each position i, find the best K length segment to the left and right of i using the solution to the previous problem for A[1] A[2] … A[i] and A[i+1] A[i+2] … A[n].

Call these segments LBEST[i] and RBEST[i] (best K length segments to left and right of i, respectively).

      1 ........................ i ......................... N
           |<--LBEST[i]--->|         |<---RBEST[i]--->|
      

Naively it will take time N to calculate LBEST[i] and RBEST[i] for each position i, so overall it will take time N².

A better approach

For each i, compute

• lbest[i] : Best K-length sequence beginning at i
• rbest[i] : Best K-length sequence starting at i

Note the difference between lbest/rbest and LBEST/RBEST. For lbest/rbest, the segment must end/start at i, respectively.

      1 ........................ i ......................... N
                 |<--lbest[i]--->|<---rbest[i]--->|
      

The solution to the previous problem finds rbest[i] for each i (i.e. sequence of K starting at i).

We reverse the computation from right to left to get lbest[i].

So, we can compute rbest[i] and lbest[i] for each i in time proportional to N.

Now,

• RBEST(i) = min rbest(j) for j ≥ i
• LBEST(i) = min rbest(j) for j ≤ i

Each of these can be computed in a single scan. For instance, as we vary i from 1 to N, we keep the minimum value of lbest[i] seen so far and update it as LBEST[i] for each i along the way.