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) { read (x1,y1,x2,y2) 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) { read (x1,y1,x2,y2) 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.