Training Material

## Computing Prefix Sums

### Two dimension: Ramu's Mango Trees

Ramu's father has left a farm organized as an N × N grid. Each square in the grid either has or does not have a mango tree. He has to divide the farm with his three sisters as follows: he will draw one horizontal line and one vertical line to divide the field into four rectangles. His sisters will choose three of the four smaller fields and he gets the last one.

He wants to divide the field so that he gets the maximum number of mangos possible, assuming that his sisters will pick the best three rectangles.

For example, suppose the field looks as follows:

```      . # # . . .
# . . # # .
. # . . . .
. # # . . #
# . . # # .
. # . . . .
```

Ramu can ensure that he gets at least 3 mango trees by cutting as follows:

```        . # | # . . .
# . | . # # .
. # | . . . .
------+---------
. # | # . . #
# . | . # # .
. # | . . . .
```

Solution

If Ramu draws the vertical line after column x and the horizontal line after row y, we represent it by (x,y). For each cut (x,y), we need to calculate the minimum rectangle that it creates. Then, over all the cuts, we choose the one whose minimum rectangle is maximized.

The problem is to efficiently calculate how a cut divides up the mango trees in the four rectangles.

Let M[x,y] be the number of mango trees in the rectangle between (0,0) and (x,y). We can calculate M[x,y] as follows:

```      M[x,y] = 1 + M[x-1,y] + M[x,y-1] - M[x-1,y-1], if tree at (x,y)
= 0 + M[x-1,y] + M[x,y-1] - M[x-1,y-1], if no tree at (x,y)
```

Thus, M[x,y] is the number of mango trees in the top left rectangle formed by the cut. Using M[x,y], we can also calculate the number of mango trees in the top right and bottom left rectangles defined by (x,y).

Top right rectangle:

```      M[N,y] - M[x,y] : Number of mangos in rectangle defined by (x,y) and (N,0)
```

Bottom left rectangle:

```      M[x,N] - M[x,y] : Number of mangos in rectangle defined by (0,N) and (x,y)
```

Finally, we subtract these three quantities from total number of mango trees to get number of mangos in fourth rectangle (bottom right), defined by (x,y) and (N,N).