Computing Prefix Sums→Oil (APIO 2009)

The Government of Siruseri has decided to auction off land in its oil-rich Navalur province to private contractors to set up oil wells. The entire area that is being auctioned off has been divided up into an M×N rectangular grid of smaller plots.

The Geological Survey of Siruseri has data on the estimated oil reserves in Navalur. This information is published as an M×N grid of non-negative integers, giving the estimated reserves in each of the plots.

In order to prevent a monopoly, the government has ruled that any contractor may bid for only one K×K square block of contiguous plots.

The AoE oil cartel consists of a group of 3 colluding contractors who would like to choose 3 disjoint blocks so as to maximize their total yield.

Suppose that the estimated oil reserves are as described below:

      1 1 1 1 1 1 1 1 1
      1 1 1 1 1 1 1 1 1
      1 8 8 8 8 8 1 1 1
      1 8 8 8 8 8 1 1 1
      1 8 8 8 8 8 1 1 1
      1 1 1 1 8 8 8 1 1
      1 1 1 1 1 1 8 8 8
      1 1 1 1 1 1 9 9 9
      1 1 1 1 1 1 9 9 9

If K = 2 , the AoE cartel can take over plots with a combined estimated reserve of 100 units, whereas if K = 3 they can take over plots with a combined estimated reserve of 208 units.

AoE has hired you to write a program to help them identify the maximum estimated oil reserves that they can take over.

Solution

We can always find a horizontal or vertical line such that one of the three squares is separated from the other two.

       ---------------------              ---------------------
      |      .         --   |            |       --      --    |
      |  --  .        |  |  |            |      |  |    |  |   |
      | |  | .        |  |  |            |      |  |    |  |   |
      | |  | .  --     --   |            |       --      --    |
      |  --  . |  |         |            |.....................|
      |      . |  |         |            |    --               |
      |      .  --          |            |   |  |              |
      |      .              |            |   |  |              |
      |      .              |            |    --               |
       ---------------------              ---------------------

We can then separate the two that are on the same side with a second cut. This cut may be parallel or perpendicular to the first cut.

       ---------------------              ---------------------
      |      .      .  --   |            |       --  .   --    |
      |  --  .      . |  |  |            |      |  | .  |  |   |
      | |  | .      . |  |  |            |      |  | .  |  |   |
      | |  | .  --  .  --   |            |       --  .   --    |
      |  --  . |  | .       |            |.....................|
      |      . |  | .       |            |    --               |
      |      .  --  .       |            |   |  |              |
      |      .      .       |            |   |  |              |
      |      .      .       |            |    --               |
       ---------------------              ---------------------

The first configuration could also occur rotated as two horizontal cuts. The second configuration can occur rotated in three other orientations. So, overall there are six cases to consider.

Case 1

Suppose the cuts are perpendicular.

       ---------------------
      |           .         |
      |           .         |
      |           .         |
      |           .         |
      |...........o.........|
      |         (x,y)       |
      |                     |
      |                     |
      |                     |
       ---------------------

Let (x,y) be the point where the cuts meet.

Suppose for every point (x,y), we have computed the following:

TL(x,y) : best K x K square from (x,y) to top left corner
TR(x,y) : best K x K square from (x,y) to top right corner
BL(x,y) : best K x K square from (x,y) to bottom left corner
BR(x,y) : best K x K square from (x,y) to bottom right corner

Then, for this choice of cuts, the best solution is TL(x,y) + TR(x,y) + BR(0,y).

We can compute TL(x,y) as follows (the others can be done similarly, by rotation).

Precompute the sum TLSum(x,y) of the rectangle from the origin A(0,0) to A(x,y) for all x,y.

To compute the sum within the rectangle with top left corner (u,v) and bottom right corner (x,y)

       -------------------------------
      |        .         .            |
      |        .         .            |
      |        .         .            |
      |.. (u,v) --------- (u,y)       |
      |        |         |            |
      |        |         |            |
      |        |         |            |
      |        |         |            |
      |.. (x,v) --------- (x,y)       |
      |                               |
       -------------------------------

TLSum(x,y) - TLSum(u,y) - TLSum(x,v) + TLSum(u,v)

Overall, all these computations can be done in time N². Remember that there are 3 other rotatational variants of Case 1 to be calculated!

Case 2

Suppose the cuts are parallel:

               (0,i+K)
       -----------o---------
      |     .     .         |
      |     .     .         |
      |     .     .         |
      |     .     .         |
      |     .     .         |
      |     .     .         |
      |     .     .         |
      |     .     .         |
      |     .     .         |
       -----o---------------
          (M,i)

Without loss of generality, we can assume that the two cuts are at the boundaries of the middle square, so the cuts are at positions i and i+K.

For the left and right rectangles, we can get the best K x K square from the quantities TL(M,i) and BR(0,i+k) that we have already precomputed

What about the best K×K square in the middle strip?

We start with the top K×K square in this strip with bottom right corner (K,i+K) for which we can compute the sum from TLSum as described earlier.

We then walk down this column and keep track of the best K×K square along this strip. Overall this takes time O(N).

In other words, for each i, we compute

BC(i) = best K×K square in the strip between columns i and i+K

This can be done overall in time O(N²). Remember that the horizontal variants of Case 2 must also be calculated!

Indian Computing Olympiad

Computing Prefix Sums→Oil (APIO 2009)

Solution

Problems related to