Saturday, January 31, 2015

108: Maximum sum (continued)

The problem with an O(n^6) algorithm is that you get a time limit error in UVA. Forums claim that you need an O(n^4) algorithm or better to have your code accepted. According to the algorithmist, if you use kadane's algorithm, you can reach an astonishing O(n^3): only 3 for loop implementation which has very fast execution time. Forums recommend using dynamic programming too.

But the problem is, what the fuck is dynamic programming?

I've heard about dynamic programming a lot of times in the past, but I really don't know what it is. My computer science professor tried to explain it to me in the past. The way I understand it is that you use previous results in order to build the results of the current cases which are bigger than the previous cases.

Which makes sense in our case, right? In this problem, we're counting the sums of rectangles. But if you think about it, a big rectangle is composed of several smaller rectangles. If you know the sums of the smaller rectangles, then you can use those sums to solve for the sum of the cells for the big rectangle. In essense, that is what dynamic programming is. We solve for the sum of a big rectangle by using the sums of the smaller rectangles which comprise the big rectangle. And these sums of the smaller rectangles were previously obtained.

People say that dynamic programming is like recursion but with the use of memory. In our problem, we are using memory to store the results of the sums of smaller rectangles so that we can recall these smaller sums to solve for the sums of larger rectangles later on.

Consider the implementation below. In particular, let us take a look at the 3 for loops beginning at line 49. Here we are considering the rectangles with sizes 1x2, 1x3, 1x4, 1x5, ... 1xn. For each size, we consider the rectangles of such sizes at coordinates (1,1), (1,2), (1,3), ..., (2,1), (2,2), ...

Initially, the sumsA array is simply a replica of the original input matrix. To solve for the 1x2 rectangles, we note that a 1x2 rectangle is composed of two 1x1 rectangles that are adjacent to each other horizontally. So, to solve for the sum of a 1x2 rectangle, we simply add the sums of the smaller 1x1 rectangles that comprise it. After solving for the sums of the 1x2 rectangles, we update sumsA array so that it contains the 1x2 rectangular sums.

To solve for 1x3 rectangles, we note that 1x3 rectangles are composed of a 1x2 rectangle and a 1x1 rectangle connected adjacently horizontally. So, in essense, to get the sum of a 1x3 rectangle, we can simply add the sum of its 1x2 rectangle and its 1x1 rectangle. Take note, however, that the 1x2 rectangular sums have been previously saved in the array sumsA. Also the 1x1 rectangular sums are simply stored already in the original array, arr. So, we can simply add the corresponding cells in sumsA and arr to arrive at the 1x3 rectangular sums.

Once we obtain the 1x3 sums, we store these in sumsA array overwriting the previously stored 1x2 sums. We overwrite the 1x2 sums because we don't need these data anymore. To build the 1x4 sums, we simply add the 1x3 sums with the 1x1 sums. So, we don't need to store the 1x2 sums anymore. As a note, notice that we store the sums for each successive rectangle considered. This is what dynamic programming is about. Storing previous results so that we can use them later on to build results for larger cases -- larger rectangles. We use the 1x3 result to solve for the 1x4 results.

Once the 1x4 sums are obtained, these are stored in sumsA, and these in turn are used to build the 1x5 sums by adding the 1x4 sums with the 1x1 sums. We continue the process until we reach the 1xn size. Remember that for each size, we have to consider all rectangles of such size at all possible beginning coordinates: (1,1), (1,2), (1,3), ..., (2,1), (2,2)...

After considering 1x1, 1x2, ..., 1xn rectangles, we consider the rectangles of sizes 2x1, 3x1, 4x1, 5x1, ..., nx1. This is what you see starting at line 63.

Let's start first with the 2x1 rectangle. We use a sumsB array which is initially set to have the same contents as the original input matrix, arr. We note that a 2x1 rectangle is composed of two 1x1 rectangles adjoined vertically. Therefore, to get the sum of a 2x1 rectangle, we add the sum of a 1x1 rectangle (from sumsB) and another sum of a 1x1 rectangle (from arr). (line 67)

Again we store the 2x1 sums in sumsB overwriting the previous 1x1 sums. We do this because if we are going to solve for the 3x1 sums, we need to have the 2x1 sums ready since a 3x1 rectangle is formed from a 2x1 rectangle and a 1x1 rectangle. Similarly, to solve for the 4x1 rectangle, we can simply add the sum for a 3x1 rectangle and 1x1 rectangle.

Note, however, that after solving for the 2x1 sums, instead of proceeding to solve for the 3x1 sums, we do something else (line 76). We solve for the 2x2 rectangular sums, the 2x3 sums, the 2x4 sums, etc. Why is that?

Observe that a 2x2 rectangle can be thought of as formed from a 2x1 rectangle and another 2x1 rectangle joined together horizontally beside each other. The 2x1 sums were previously stored in sumsB, but they were also stored in sumsA array (lines 68-69). Therefore, to solve for a 2x2 rectangle, we sum the corresponding sums from sumsA (2x1 sums) with the sums in sumsB (2x1 sums).

The resulting 2x2 sums are stored in sumsA overwriting the previous 2x1 sum contents. We overwrite because we need the updated 2x2 sums to solve for the 2x3 rectangles. A 2x3 rectangle can be thought of as formed by adjoining a 2x2 rectangle with a 2x1 rectangle horizontally. Notice that we did not overwrite the contents of sumsB which contains 2x1 sums. So, to solve for the 2x3 sums, we add the sums from sumsA (2x2 sums) with the sums in sumsB (2x1 sums). We repeat the process for 2x4, 2x5, ..., 2xn rectangles.

We then solve for the 3x1 rectangles using the sumsB array which contains the 2x1 sums (line 63). After solving for the 3x1 rectangles which are now stored in sumsB (2x1 contents overwritten (line 68), we solve for the 3x2 rectangles by noting that we can solve 3x2 rectangles by adding two 3x1 rectangles (sumsA and sumsB which both contain 3x1 sums (lines 68-69). I'm tired, I think you get how the algorithm goes.

Bottom line is you end up with an O(n^4) algorithm (only max of 4 embedded for-loops). This results to an accepted solution in UVA. This implementation ran in 0.062 seconds in UVA. I still have to learn about Kadane's algorithm which results in O(n^3).

     1 #include "stdio.h"
     2 #include "string.h"
     3 #include "stdlib.h"
     4 int main() {
     5  const int lsize = 100000;
     6  char line[lsize];
     7  int n, x, y, r, c, i, j, k;
     8  int p, q, s, t, u, v;
     9  int max, sum;
    10  char *pch;
    11  int arr[150][150];
    12  int sumsA[150][150];
    13  int sumsB[150][150];
    14  fgets(line, lsize, stdin);
    15  sscanf(line, "%d", &n);
    16  r = c = 1;
    17  while (fgets(line, lsize, stdin)) {
    18    pch = strtok(line, " \t\n");
    19    while (pch) {
    20      x = atoi(pch);
    21      arr[r][c] = x;
    22      c += 1;
    23      if (c > n) {
    24        r += 1;
    25        c = 1;
    26      }
    27      pch = strtok(NULL, " \t\n");
    28    }
    29  }
    30 //  for (r = 1; r <= n; r += 1) {
    31 //    for (c = 1; c <= n; c += 1) {
    32 //      printf("%d ", arr[r][c]);
    33 //    }
    34 //    printf("\n");
    35 //  }
    36  max = arr[1][1];
    37 //  printf("1x1\n");
    38  for (i = 1; i <= n; i += 1) {
    39    for (j = 1; j <= n; j += 1) {
    40      sum = arr[i][j];
    41      sumsA[i][j] = sum;
    42      sumsB[i][j] = sum;
    43      if (sum > max) {
    44        max = sum;
    45      }
    46    }
    47  }
    48 //  printf("1x2, 1x3, 1x4, ...\n");
    49  for (i = 2; i <= n; i += 1) {
    50    x = n - i + 1;
    51    for (j = 1; j <= n; j += 1) {
    52      for (k = 1; k <= x; k += 1) {
    53        sum = sumsA[j][k] + arr[j][k+i-1];
    54        sumsA[j][k] = sum;
    55        if (sum > max) {
    56          max = sum;
    57        }
    58 //        printf("%d %d %d = %d\n", i, j, k, sum);
    59      }
    60    }
    61  }
    62 //  printf("2x1, 3x1, 4x1, ...\n");
    63  for (i = 2; i <= n; i += 1) {
    64    x = n - i + 1;
    65    for (j = 1; j <= x; j += 1) {
    66      for (k = 1; k <= n; k += 1) {
    67        sum = sumsB[j][k] + arr[j+i-1][k];
    68        sumsB[j][k] = sum;
    69        sumsA[j][k] = sum;
    70        if (sum > max) {
    71          max = sum;
    72        }
    73 //        printf("%d %d %d = %d\n", i, j, k, sum);
    74      }
    75    }
    76 //    printf("\t%dx2,3,4,...\n", i);
    77    for (s = 2; s <= n; s += 1) {
    78      y = n - s + 1;
    79      for (j = 1; j <= x; j += 1) {
    80        for (k = 1; k <= y; k += 1) {
    81          sum = sumsA[j][k] + sumsB[j][k+s-1];
    82          sumsA[j][k] = sum;
    83          if (sum > max) {
    84            max = sum;
    85          }
    86 //          printf("\t%d %d %d %d = %d\n", i, s, j, k, sum);
    87        }
    88      }
    89    }
    90  }
    91  printf("%d\n", max);
    92  return 0;
    93 }

No comments:

Post a Comment