USACO 2013 Silver Perimeter

Problems and Contests
#1

This USACO 2013 Silver problem is unlike a problem I have seen before. We have only 50,000 cows but each x and y coordinates are up to 1e6.

I tried to use floodfill and resize the grid so it’s just large enough to fit all the cows. Even so, the length and width could possibly be 25,000, which exceeds the memory limit.

I receive a runtime error or memory limit out-of-bounds exception when I run the following code.

int rows, columns;
vt<vt<bool>> grid, visited;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int perimeter;
void floodfill(int x, int y) {
  if (x < 0 || x >= rows || y < 0 || y >= columns) return;
  if (visited[x][y]) return;
  if (grid[x][y] == 1) {
    perimeter++;
    return;
  }
  visited[x][y] = 1;
  F0R(i, 4) floodfill(x + dx[i], y + dy[i]);
}

int main()
{
    setIO("perimeter");
    int n;
    vt<pi> order(n);
    pi X = {1e6, 0}, Y = {1e6, 0};
    auto bound = [] (pi& A, int p) {
      A.f = min(A.f, p);
      A.s = max(A.s, p);
    };
    cin >> n;
    F0R(i, n) {
      int x, y;
      cin >> x >> y;
      order[i] = {x, y};
      bound(X, x);
      bound(Y, y);
    }
    rows = X.s - X.f + 3;
    columns = Y.s - Y.f + 3;
    grid.resize(columns);
    F0R(i, columns) grid[i].resize(rows);
    visited.resize(columns);
    F0R(i, columns) visited[i].resize(rows);
    pair<int, int> change = {X.f-1, Y.f-1};
    F0R(i, n) {
      int a = order[i].s - change.s;
      int b = order[i].f - change.f;
      grid[a][b] = 1;
    }
    /*F0R(i, columns) {
      F0R(j, rows) cout << grid[i][j] << " ";
      cout << endl;
    }*/
    //floodfill(0, 0);
    cout << perimeter << endl;
}
  • If the print statements are left commented, I receive a runtime error or memory limit exceeded exception regardless of the floodfill.
  • If I uncomment only the print statements, the grid outputs correctly.
  • If I uncomment both the print statements and the floodfill, a runtime error or memory limit exceeded exception occurs.

I could not find an issue with either my floodfill function or the way I set up my grid. Is there some undefined behavior? Can you please help?

I am also confused as to how this problem can require such severe compression. It seems true that the memory limit will certainly be exceeded. The way I did the compression also seems way too time-consuming and error-prone for a regular silver problem. Was there a mistake in this problem statement? Can you please clarify?

#2

Here’s a hint: You don’t need to use coordinate compression or flood fill for this problem.

#3

I think you receive memory errors because your grid can go up to 25000 x 25000, which is about 1.25GB, and the memory limit is 256MB. So you don’t have to call the floodfill function to get MLEs.
To solve this problem correctly, you don’t need to resize your grid and do a flood fill, but using an idea similar to flood fill, and “walk” on the outer border of the bales.

#4

Btw, the second silver problem from that contest is a good problem for practicing flood fill: Tractor