USACO 2021 February Contest, Bronze Problem 2. Comfortable Cows

USACO 2021 February Contest, Bronze Problem 2. Comfortable Cows

Farmer John's pasture can be regarded as a large 2D grid of square "cells" (picture a huge chessboard). Initially, the pasture is empty.

Farmer John 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. Farmer John is interested in counting the comfortable cows on his farm. For each ii in the range 1…N1…N, output the total number of comfortable cows after the iith cow is added to the pasture.

 

 

 

SAMPLE INPUT:

8
0 1
1 0
1 1
1 2
2 1
2 2
3 1
3 2

SAMPLE OUTPUT:

0
0
0
1
0
0
1
2

After the first four cows are added, the cow at (1,1)(1,1) is comfortable.

After the first seven cows are added, the cow at (2,1)(2,1) is comfortable.

After the first eight cows are added, the cows at (2,1)(2,1) and (2,2)(2,2) are comfortable.

 

 

Problem credits: Benjamin Qi

 USACO 2021 February Contest, Bronze Problem 2. Comfortable Cows 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Dhruv Rohatgi )

Let's add the cows one by one into a 1000×10001000×1000 boolean array AA, where a 11 in position A[x][y]A[x][y] indicates that there is a cow at (x,y)(x,y), and otherwise A[x][y]=0A[x][y]=0.

When a new cow is added, there are at most five cows who might either become comfortable or become uncomfortable: the new cow, plus any neighbors she might have. So before adding a cow into position (x,y)(x,y), we can count the number of neighbors who are comfortable; after adding we count the number of neighbors (or the new cow) who are comfortable, and we update a running counter (of comfortable cows) by the difference.

To make the code simpler, it helps to have a function which, given a position in the array, determines whether there is a comfortable cow at this location.

This algorithm runs in linear time, with only one pass through the input.

 

#include <iostream>
using namespace std;
#define MAXN 1001
 
int N;
bool A[MAXN][MAXN];
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
 
bool valid_position(int x,int y)
{
	return x>=0 && x<=N && y>=0 && y<=N;
}
 
bool comfortable(int x,int y)
{
	if(A[x][y] == 0) return 0;
	int neighbors = 0;
	for(int d=0;d<4;d++)
		if(valid_position(x+dx[d],y+dy[d]))
			if(A[x+dx[d]][y+dy[d]])
				neighbors++;
	return neighbors == 3;
}
 
int main()
{
	int x,y;
	cin >> N;
	int nComfortable = 0;
	for(int i=0;i<N;i++)
	{
		cin >> x >> y;
		for(int d=0;d<4;d++)
			if(valid_position(x+dx[d],y+dy[d]))
				nComfortable -= comfortable(x+dx[d],y+dy[d]);
		A[x][y] = 1;
		for(int d=0;d<4;d++)
			if(valid_position(x+dx[d],y+dy[d]))
				nComfortable += comfortable(x+dx[d],y+dy[d]);
		nComfortable += comfortable(x,y);
		cout << nComfortable << '\n';
	}
}

[/hide]