Analysis: Figure Eight by Nathan Pinsker


This problem immediately suggests a DP approach. We need to choose two rectangles A and B such that the top edge of B completely contains the bottom edge of A, and the aesthetic score of A and B together is maximized. At first this seems difficult because the choice of A severly limits our choices for B, and simply storing large rectangles does not allow us to efficiently choose the second rectangle of our set once we have chosen the first. However, note that if we fix the bottom-left and bottom-right points of A, then we can calculate both A and B independently of each other and greedily. We will simply take A to be the largest rectangle with those points as its bottom corners, and B to be the largest rectangle with both those points on its top edge and neither as corners. Both of those values need to be calculated for O(N^3) possible pairs of points, but we will have solved the problem once we calculate them.

The first of these can be calculated fairly easily. We start by setting c = 0 and increasing it each iteration. For each pair of points (a, c) and (b, c) as the bottom corners of a rectangle A (where a < b), we check whether all points between (a, c) and (b, c) are flawless. If they are, we can simply add b-a+1 to the already- calculated optimal choice of A for the points (a, c-1) and (b, c-1); otherwise, our calculated value will be 0. We can check whether these points are filled in O(1) time using some quick precomputation, so each of these values takes O(1) time overall and our total runtime is O(N^3).

Luckily, the second value is not much harder to compute. We start by calculating, in the same way as above, the optimal choice of bottom rectangle, assuming the rectangle's top-left and top-right points are fixed. Then, for each pair of points (a, c) and (b, c) that we want our top edge to intersect (such that a < b), we will let F(a, b, c) denote our optimal choice of B. We know that the top edge will either also contain (a-1, c) or contain (b+1, c) as a non-corner, or will contain both (a-1, c) and (b+1, c) as corners. If the first case is true, then F(a, b, c) = F(a-1, b, c) or F(a, b, c) = F(a, b+1, c). If the second case is true, then F(a, b, c) is equal to the optimal choice of bottom rectangle with a-1 and b+1 as its top corners, which we have just calculated. Thus, our values of F can be computed in O(1) time as well and we are done.

Below is Travis Hance's solution. He uses best_down and best_up a little differently than the above solution, but the basic idea is exactly the same.


/*
LANG: C++
*/

#include 
#include 
using namespace std;

#define NMAX 200

int n;
bool grid[NMAX][NMAX];
int rowcmp[NMAX][NMAX];

short best_down[NMAX][NMAX][NMAX];
short best_up[NMAX][NMAX][NMAX];

short best_up_total[NMAX][NMAX][NMAX];

int main() {
#ifndef HOME
  freopen("eight.in", "r", stdin);
  freopen("eight.out", "w", stdout);
#endif

  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      char c;
      do { c = fgetc(stdin); } while (c != '.' && c != '*');
      grid[i][j] = (c == '.');
    }
  }

  int rcmp = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (!grid[i][j]) {
        rcmp++;
      }
      rowcmp[i][j] = rcmp;
    }
  }

  for (int i = 0; i < n; i++) {
    for (int j1 = 0; j1 < n; j1++) {
      bool okay = grid[i][j1];
      for (int j2 = j1 + 1; j2 < n; j2++) {
        okay = okay && grid[i][j2];
        if (grid[i][j1] && grid[i][j2]) {
          if (i > 0 && best_up[i-1][j1][j2] != -1) {
            best_up[i][j1][j2] = 1 + best_up[i-1][j1][j2];
          } else {
            best_up[i][j1][j2] = okay ? 0 : -1;
          }
        } else {
          best_up[i][j1][j2] = -1;
        }
      }
    }
  }

  for (int i = n-1; i >= 0; i--) {
    for (int j1 = 0; j1 < n; j1++) {
      bool okay = grid[i][j1];
      for (int j2 = j1 + 1; j2 < n; j2++) {
        okay = okay && grid[i][j2];
        if (grid[i][j1] && grid[i][j2]) {
          if (i < n-1 && best_down[i+1][j1][j2] != -1) {
            best_down[i][j1][j2] = 1 + best_down[i+1][j1][j2];
          } else {
            best_down[i][j1][j2] = okay ? 0 : -1;
          }
        } else {
          best_down[i][j1][j2] = -1;
        }
      }
    }
  }

  long long ans = 0;

  for (int i = 0; i < n; i++) {
    for (int l = 1; l < n; l++) {
      for (int j1 = 0; j1 + l < n; j1++) {
        int j2 = j1 + l;
        if (grid[i][j1] && grid[i][j2]) {
          best_up_total[i][j1][j2] = (best_up[i][j1][j2] < 2 ? -1 :
(best_up[i][j1][j2] - 1) * (j2 - j1 - 1));
          if (l > 1) {
            best_up_total[i][j1][j2] = max(best_up_total[i][j1][j2],
max(best_up_total[i][j1+1][j2], best_up_total[i][j1][j2-1]));
          }
        } else {
          best_up_total[i][j1][j2] = -1;
        }

        if (rowcmp[i][j1] == rowcmp[i][j2] && best_up_total[i][j1][j2] != -1 &&
best_down[i][j1][j2] >= 2) {
          ans = max(ans, (long long) best_up_total[i][j1][j2] * (long long)
(best_down[i][j1][j2] - 1) * (long long) (j2 - j1 - 1));
        }
      }
    }
  }

  printf("%lld\n", ans);
}

You can also reduce the memory requirements to O(N^2), although it was not required. Here is Mark Gordon's solution demonstrating this:

/*
LANG: C++
*/
#include 
#include 
#include 

using namespace std;

#define MAXN 300

string A[MAXN];
bool B[MAXN][MAXN];
int DP[MAXN][MAXN];
int DPO[MAXN][MAXN];

int main() {
  freopen("eight.in", "r", stdin);
  freopen("eight.out", "w", stdout);

  int N; cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> A[i];
  }
  for(int i = 0; i + 1 < N; i++) {
    for(int j = 0; j < N; j++) {
      B[i][j] = A[j][i] == '.' && A[j][i + 1] == '.';
    }
  }

  long long result = 0;
  for(int sz = 3; sz <= N; sz++) {
    memcpy(DPO, DP, sizeof(DP));
    for(int i = 0; i + sz <= N; i++) {
      int mn = N;
      for(int j = 0; j < N; j++) {
        B[i][j] = B[i][j] && A[j][i + sz - 1] == '.';
        if(B[i][j]) {
          mn = min(mn, j);
        }
      }
      int pr = -1, tpr = -1;
      int mx = mn;
      for(int j = mn; j < N; j++) {
        for(mx = max(mx, j); mx < N && A[mx][i] == '.' &&
                                       A[mx][i + sz - 1] == '.'; mx++) {
          if(B[i][mx]) {
            tpr = mx;
          }
        }

        if(B[i][j]) {
          DP[i][j] = max(DPO[i][j], DPO[i + 1][j]);
          if(pr == -1) {
            pr = j;
          } else {
            DP[i][j] = max(DP[i][j], max(0, j - pr - 1) * (sz - 2));
          }
          long long r = (long long)DP[i][j] * max(0, tpr - j - 1) * (sz - 2);
          result = max(result, r);
        } else if(A[j][i] != '.' || A[j][i + sz - 1] != '.') {
          pr = -1;
        }
      }
    }
  }

  cout << (result == 0 ? -1 : result) << endl;
  return 0;
}