# Comfortable Cows USACO 2021 February Contest

Page Contents

## Comfortable Cows USACO Solution

Farmer Nhoj’s pasture can be regarded as a large 2D grid of square “cells” (picture a huge chessboard). Initially, the pasture is empty.

Farmer Nhoj will add NN (1≤N≤1051≤N≤105) cows to the pasture one by one. The iith cow will occupy a cell (xi,yi)(xi,yi) that is distinct from the cells occupied by all other cows (0≤xi,yi≤10000≤xi,yi≤1000).

A cow is said to be “comfortable” if it is horizontally or vertically adjacent to exactly three other cows. Unfortunately, cows that are too comfortable tend to lag in their milk production, so Farmer Nhoj wants to add additional cows until no cow (including the ones that he adds) is comfortable. Note that the added cows do not necessarily need to have xx and yy coordinates in the range 0…10000…1000.

For each ii in the range 1…N1…N, please output the minimum number of cows Farmer Nhoj would need to add until no cows are comfortable if initially, the pasture started with only cows 1…i1…i.

#### INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains a single integer NN. Each of the next NN lines contains two space-separated integers, indicating the (x,y)(x,y) coordinates of a cow’s cell.

#### OUTPUT FORMAT (print output to the terminal / stdout):

The minimum number of cows Farmer Nhoj needs to add for each ii in 1…N1…N, on NN separate lines.

```9
0 1
1 0
1 1
1 2
2 1
2 2
3 1
3 2
4 1
```

#### SAMPLE OUTPUT:

```0
0
0
1
0
0
1
2
4
```

For i=4i=4, Farmer Nhoj must add an additional cow at (2,1)(2,1) to make the cow at (1,1)(1,1) uncomfortable.

For i=9i=9, the best Farmer Nhoj can do is place additional cows at (2,0)(2,0), (3,0)(3,0), (2,−1)(2,−1), and (2,3)(2,3).

Problem credits: Benjamin Qi

Whenever there exists a cow horizontally or vertically adjacent to three other cows, Farmer Nhoj is forced to place a cow at the fourth spot.

```...    .C.
CCC -> CCC
.C.    .C.
```

So this is essentially a flood fill problem; while there exists a location that should contain a cow but does not, add a cow at that location.

My solution maintains a 2D boolean array of which locations currently contain cows, as well as a queue of locations in the pasture where a cow needs to be added. While the queue is nonempty, pop the top element (x,y)(x,y) of the queue and check whether a cow has already been added at (x,y)(x,y). If not, add the cow at (x,y)(x,y), and check whether any of the locations (x,y),(x,y−1),(x,y+1),(x−1,y),(x+1,y)(x,y),(x,y−1),(x,y+1),(x−1,y),(x+1,y) contain cows and are adjacent to exactly three cows. If so, add all such locations to the queue and repeat.

• The cows that will eventually be present on the pasture after the first ii cows are added is a superset of the cows that will eventually be present on the pasture after the first i−1i−1 cows are added.
• This means that we don’t need to reset the array between the addition of each cow.
• If all cells in [0,1000]×[0,1000][0,1000]×[0,1000] are initially occupied, Farmer Nhoj will need to add cows at all locations (x,y)(x,y) satisfying x+y≥0,x+y≤2000,x−y≤1000,x−y≥−1000x+y≥0,x+y≤2000,x−y≤1000,x−y≥−1000 (in other words, a diamond with vertices at (−500,500),(500,−500),(1500,500),(−500,500),(500,−500),(1500,500), and (500,1500)(500,1500)). So if we increase the xx and yy cow locations by 500500, then all of these locations will lie in the range [0,2000]×[0,2000][0,2000]×[0,2000].
• In my solution, I use 10001000 instead of 500500.

Time Complexity: O(N+(grid size)2)O(N+(grid size)2).

```#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second

const int dx = {1,0,-1,0}, dy = {0,1,0,-1};

bool present; // which locations contain cows

int main() {
int N; cin >> N;
queue<pair<int,int>> cows_to_place;
int total_cows = 0;
for (int initial_cows = 1; initial_cows <= N; ++initial_cows) {
pair<int,int> p; cin >> p.f >> p.s;
p.f += 1000, p.s += 1000;
cows_to_place.push(p);
auto re_evaluate = [&](int x, int y) {
// if cow adjacent to exactly three others
// add fourth location to queue
if (!present[x][y]) return;
int num_adj = 0;
for (int d = 0; d < 4; ++d)
if (num_adj == 3)
for (int d = 0; d < 4; ++d) {
pair<int,int> nex{x+dx[d],y+dy[d]};
if (!present[nex.f][nex.s])
cows_to_place.push(nex);
}
};
while (!cows_to_place.empty()) {
pair<int,int> loc = cows_to_place.front();
cows_to_place.pop();
if (present[loc.f][loc.s]) continue;
++ total_cows; present[loc.f][loc.s] = 1;
re_evaluate(loc.f,loc.s);
for (int d = 0; d < 4; ++d)
re_evaluate(loc.f+dx[d],loc.s+dy[d]);
}
cout << total_cows-initial_cows << "\n";
}
}
```

Here is an alternative solution by Danny Mittal that does not use a queue:

```import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class LonelyPastureSilver {
static final boolean[][] cows = new boolean;
static final int[][] adj = new int;
static int answer = 0;

static void add(int x, int y) {
if (!cows[x][y]) {
cows[x][y] = true;
if (cows[x][y] && adj[x][y] == 3) {
for (int[] another : new int[][]{{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}}) {
int w = another;
int z = another;
}
}
for (int[] other : new int[][]{{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}}) {
int u = other;
int v = other;
if (cows[u][v] && adj[u][v] == 3) {
for (int[] another : new int[][]{{u - 1, v}, {u + 1, v}, {u, v - 1}, {u, v + 1}}) {
int w = another;
int z = another;
}
}
}
}
}

public static void main(String[] args) throws IOException {
StringBuilder out = new StringBuilder();
int n = Integer.parseInt(in.readLine());
for (int j = 0; j < n; j++) {
StringTokenizer tokenizer = new StringTokenizer(in.readLine());
int x = Integer.parseInt(tokenizer.nextToken()) + 1000;
int y = Integer.parseInt(tokenizer.nextToken()) + 1000;
}
System.out.print(out);
}
}```