### Online Programming Contest, 4-5 December, 2004

Solution to Problem 2: The Timber Auction

```
In this problem you are given a M X N rectangular grid of
positive integers. You are then given a number of subrectangles
of this grid and asked to find the sum of all the integers in the
subgrid.

A subrectangles is described by the position of its top left
corner and bottom right corner in the given grid.  Each position
is a pair (x,y) where x determines the row number and y
determines the colomn number.

The naive algorithm simply adds up the entries in the
subrectangle and prints out the answer.

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

/* We assume that the grid is described by a 2 dimensional
array T where T[i][j] is the volume of the tree on the ith row
and jth colomn */

for (i = 1 to  C) {
Read (x1,y1)    /* position of the top left corner
Read (x2,y2)    /* position of the bottom right corner

sum = 0

/* add up the volume in the trees in the subrectangle */

for (j=x1 to x2)
for (k=y1 to y2)
sum = sum + T[j][k]

print sum
}

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

Thus, computing the total volume in each subrectanlge takes time
proportional to the size of the grid, which is roughly M*N.  So,
for C subrectangles the time taken is proportional to C*M*N.

If the number of subrectangles whose sum is needed is small, then
this algorithm performs quite well. But, as the input data to
this problem suggests, C could be large, for example of the order
of M*N. (Note that C could actually be very large, almost as
large as M*N*M*N (i.e. the number of pairs of locations that
define subrectanlges)).

We should certainly be able to do better than that! After all,
the above algorithm wastefully recomputes sums of
subrectangles. (For example, if we had one subrectangle contained
in another, this algorithm would recompute the sum of the smaller
rectangle twice.)

Our first observation is that even though there are M*N*M*N
rectangles it suffices to compute the sums of the M*N rectangles
whose top left corner is (1,1).

(1,1)   (1,2)  ... (1,y1)  ...   (1,y2) ...   (1,N)
(2,1)   (2,2)  ... (2,y1)  ...   (2,y2) ...   (2,N)
.       .          .             .            .
.       .          .             .            .
.       .          .             .            .
(x1,1) (x1,2)  ... (x1,y1) ...  (x1,y2) ...   (x1,N)
.      .           .            .           .
.      .           .            .           .
.      .           .            .           .
(x2,1)  (x2,2) ... (x2,y1) ...  (x2,y2) ...  (x2,N)
.      .                                    .
.      .                                    .
.      .                                    .
(M,1)   (M,2)  ...  (M,y1)       (M,y2) ...   (M,N)

Let V(a,b,c,d) denote the sum of the rectangle whose top left
corner is at position (a,b) and bottom right corner is at
position (c,d). Then

V(x1,y1,x2,y2) =   V(1,1,x2,y2) - V(1,1,x1 - 1,y2) - V(1,1,x2,y1 - 1)
+ V(1,1,x1 - 1 ,y1 - 1)

(where V(1,1,a,b) is 0 whenever a < 1 or b < 1).

Thus if know the volumes of all the rectangles with (1,1) as the
top left corner, we can compute the volume of any other rectangle
in just one operation.

But there are N*M rectangles with the top left corner at (1,1)
and thus computing the sums of all these rectangles using the
naive algorithm described above can take time proportional to
M*N*M*N.

But as we observed, there is a lot of repetition in these
computations, and we should look for some way to avoid that.
Dynamic Programming to the rescue!!

Notice that

V(1,1,1,1) = T[1][1]
V(1,1,x,y) = V(1,1,x-1,y) + V(1,1,x,y-1) - V(1,1,x-1,y-1) + T[x][y].

(where V(1,1,a,b) = 0 whenever a<1 or b<1).

So, this is an example of a 2-dimensional dynamic programming
algorithm.  writing V'(x,y) for V(1,1,x,y), we get:

V'(1,1) = T[1][1]
V'(x,y) = V'(x-1,y) + V'(x,y-1) - V(x-1,y-1) + T[x][y]

We could write a recursive algorithm that stores values in a 2
dimensional array to avoid recomputations as follows: (since this
is the first time we have encountered a 2 dimensional Dynamic
programming algorithm, I describe it in detail below):

----------------------------------------------------------------------
/* Initialize the StoredV' array to indicate nothing has been
computed so far */
for (i=1 to M)
for (j=1 to N)
StoredV'[i][j] = -1

/* A neat trick now. Instead of checking if i<1 or j<1 and then
returning 1, we simply set V[i][0] and V[0][j] to 0's. So we
never have to check if i<1 or j<1 */

for (i=1 to M) StoredV'[i][0]=0
for (i=1 to N) StoredV'[0][i]=0

/* the function that computes V'(i,j)

V'(i,j) {

if ( StoredV'[i][j] != -1 )
return(StoredV'[i][j])

if (StoredV'[i][j-1] == -1)  x = V'(i,j-1)
else   x = StoredV'[i][j-1]

if (StoredV'[i-1][j] = -1)  x = x + V'(i-1,j)
else   x = x + StoredV'[i-1][j]

if (StoredV'[i-1][j-1] = -1)  x = x - V'(i-1,j-1)
else   x = x - StoredV'[i-1][j-1]

x = x + T[i][j]

StoredV'[i][j] = x

return(x)

}

/* compute the volume of the given rectangles using V' now */

for (i=1 to C) {
return(V'(x2,y2) - V'(x2,y1-1) - V'(x1-1,y2) + V'(x1-1,y1-1))
}

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

This algorithm above avoids multiple evaluations of the same
rectangle.

Note, that calling V'(x,y) calls V'(x-1,y) which in turn calls
V'(x-2,y) ... V'(1,y). It also calls V'(x,y-1) which in turn
calls V'(x,y-2) and so on till V'(x,1). Thus, a call to V'(x,y)
actually results in the computation of
V'(1,1)...V'(1,y),V'(2,1)... V'(2,y) ... V'(x,1) ... V'(x,y).

So it would not be to expensive to simply compute all the
V'(x,y)s before we evaluating the volumes of the given
subrectangles. In other words we could simply "precompute"
V'(M,N) (which in turn would ensure that all entries V'(i,j) are
computed) before the loop at the end of the above
algorithm. Though this might be wasteful if C was small and did
not require most of these sums, the idea behind this
precomputation is that once this is done, for any rectangle we
can return the answer in just 1 step. Such precomputations are
often very useful.

Now that we do plan to evaluate all the V'(x,y)'s, can we do that
without recursion? What order should we choose to avoid the
recursive calls?

The answer is rather evident from the expression for V'(i,j).  It
depends on the element to its left V(i,j-1), the element above it
V(i-1,j) and the element diagonally above it to its left
V(i-1,j-1).  Thus, if we evaluate the V's form the top row to the
bottom row and from left to right in each row (that is, in the
order V(1,1)...V(1,N),V(2,1)...V(2,N).... V(M,1)... V(M,N)) then
we can avoid recursion.

Here is an algorithm to do this:

----------------------------------------------------------------------
for (i=1 to M) StoredV'[i][0]=0
for (i=1 to N) StoredV'[0][i]=0

for (i=1 to M)
for (j=1 to N) {
StoredV'[i][j] =  StoredV'[i][j-1] + StoredV'[i-1][j]
- StoredV'[i-1][j-1] + T[i][j]
}

/* compute the volume of the given rectangles using V' now */

for (i=1 to C) {
return(StoredV'(x2,y2) - StoredV'(x2,y1-1)
- StoredV'(x1-1,y2) + StoredV'(x1-1,y1-1))
}

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

The above algorithm takes roughly M*N steps to compute the
entries in the StoredV'[][] array. Computation of each subgrid
takes just one operation after that. So the overall time taken is
roughly M*N + C. This algorithm would get 100% marks.

```

Copyright (c) IARCS 2003-2022;   Last Updated: 15 Mar 2005