Saturday, January 31, 2015

108: Maximum sum

The first time I saw this problem was about in year 2006. The problem was in a programming contest orientation. Back then, I remember I think I was able to solve the problem. So this time, when I saw the same problem in uVA after more than 9 years, I was pretty confident I could resolve the problem.

I did resolve the problem and I was confident that my solution would get accepted. Then, came the bad news. My solution was rejected with a time limit error. I was appalled. Didn't know what to do beyond a brute force algorithm.

I read through the discussions in the internet and they said that you need at least an O(n^4) algorithm in order for your solution to get accepted. This means that the time by which your algorithm executes should be a polynomial function of the number of inputs, but the polynomial function should only be a variant of n raised to 4, where n is the number of inputs. In other words, time of execution = f(n^4). Another way to put it is that your algorithm should only have a maximum of 4 embedded for loops:

for (...) { for (...) { for (...) { for (...) {...} } } }

My original algorithm was O(n^6) consisting of 6 embedded for loops. I tried running my solution using an i5 machine for a 100x100 input. It took about 2.5 minutes to execute. The machine uVA uses for judging uses a weaker machine than an i5 probably, that's why I got a time limit.

My original algorithm uses a brute force approach and considers all possible rectangles beginning with 1x1 rectangles. A 1x1 rectangle is simply a rectangle consisting of 1 cell. Then the algorithm considers all 1x2 rectangles. A 1x2 rectangle is a rectangle consisting of 2 cells aligned horizontally. Then, the algorithm considers all 1x3 rectangles, 1x4 rectangles, up to 1xn rectangles where n is the total number of columns of the input.

Then the algorithm considers 2x1 rectangles (2 cells aligned vertically). Then, 2x2 rectangles (4 cells arranged as a square). Then 2x3 rectangles, 2x4 rectangles, etc up to 2xn rectangles.

The algorithm keeps continuing until the nxn rectangle is considered. The algorithm then stops. For each rectangle considered, the sum of the cells in the rectangle is compared against a maximum. If the sum is greater than the maximum sum previously obtained, then the maximum is updated.

For each dimension, the algorithm considers all possible rectangles at all possible positions in the matrix. For instance, for 1x1 rectangles, the algorithm considers the rectangle at coordinates (1,1), the rectangle at coordinates (1,2), at (1,3)...at (1,n), the rectangle at coordinates (2,1), (2,2), (2,3), ...(2,n), up to (n,n). The same goes with 1x2 rectangles. All 1x2 rectangles at all possible beginning coordinates are considered: (1,1), (1,2), (1,3), ... (1,n-1).

This is why 6 loops are needed: The first two outmost loops are for generating all dimensions: 1x1 rectangles, 1x2 rectangles, 1x3, 1x4, ..., 1xn, 2x1, 2x2, 2x3, ... 2xn, ... nxn. The next two for loops are for considering the rectangles at all possible beginning coordinates. For instance, for 1x2 rectangles, we consider such rectangles at coordinates (1,1), (1,2), (1,3), ... (1, n-1), (2,1), (2,2), (2, n-1), ... (n, n-1). The last two inmost for loops are for computing the sum of the cells in each rectangle considered. For instance, for computing the sum of the cells for the 1x2 rectangle which has beginning coordinates at say (2,3).

Here is the brute force implementation. Remember that this is O(n^6). Six embedded for loops, and it isn't accepted by UVA because of time limit problem. UVA requires solutions that take less than 3 seconds. Can you see the six embedded for loops in the code?

     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;
     8  int p, q, s, t, u, v;
     9  int max, sum;
    10  char *pch;
    11  int arr[150][150];
       
    12  fgets(line, lsize, stdin);
    13  sscanf(line, "%d", &n);
       
    14  r = c = 1;
    15  while (fgets(line, lsize, stdin)) {
    16    pch = strtok(line, " \t\n");
    17    while (pch) {
    18      x = atoi(pch);
    19      arr[r][c] = x;
       
    20      c += 1;
    21      if (c > n) {
    22        r += 1;
    23        c = 1;
    24      }
       
    25      pch = strtok(NULL, " \t\n");
    26    }
    27  }
       
    28 //  for (r = 1; r <= n; r += 1) {
    29 //    for (c = 1; c <= n; c += 1) {
    30 //      printf("%d ", arr[r][c]);
    31 //    }
    32 //    printf("\n");
    33 //  }
       
    34  max = arr[1][1];
    35  for (i = 1; i <= n; i += 1) {
    36    x = n - i + 1;
    37    for (j = 1; j <= n; j += 1) {
    38 //      printf("%d %d\n", i, j);
    39      y = n - j + 1;
    40      for (p = 1; p <= x; p += 1) {
    41        u = p + i - 1;
    42        for (q = 1; q <= y; q += 1) {
    43          sum = 0;
    44          v = q + j - 1;
    45          for (r = p; r <= u; r += 1) {
    46            for (c = q; c <= v; c += 1) {
    47              sum += arr[r][c];
    48            }
    49          }
    50 //          printf("%d %d %d %d = %d\n", i, j, p, q, sum);
    51          if (sum > max) {
    52            max = sum;
    53          }
    54        }
    55      }
    56    }
    57  }
       
    58  printf("%d\n", max);
       
    59  return 0;
    60 }


No comments:

Post a Comment