Training Material

## 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 N2. 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(N2). Remember that the horizontal variants of Case 2 must also be calculated!