Comfortable Cows USACO 2021 February Contest

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.

See Also : USACO 2021 Challenges

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.

SAMPLE INPUT:

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.

Additional notes:

  • 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[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};

bool present[3000][3000]; // 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) 
				num_adj += present[x+dx[d]][y+dy[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.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class LonelyPastureSilver {
    static final boolean[][] cows = new boolean[3000][3000];
    static final int[][] adj = new int[3000][3000];
    static int answer = 0;
 
    static void add(int x, int y) {
        if (!cows[x][y]) {
            cows[x][y] = true;
            answer++;
            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[0];
                    int z = another[1];
                    add(w, z);
                }
            }
            for (int[] other : new int[][]{{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}}) {
                int u = other[0];
                int v = other[1];
                adj[u][v]++;
                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[0];
                        int z = another[1];
                        add(w, z);
                    }
                }
            }
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        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;
            answer--;
            add(x, y);
            out.append(answer).append('\n');
        }
        System.out.print(out);
    }
}

USACO 2021 February Contest

Weekly Contest 247

Biweekly Contest 55

Codechef Long Challenge Solutions

July Long Challenge 2021 Solutions

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

Leave a Comment