USACO 2021 February Contest Bronze Division - Comfortable Cows

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

The key observation for this problem is that the only cells that could be affected by the new cow are the cow itself, its four neighbors and the neighbors of those neighbors.

Source codes

The source codes in C++ and Python can be seen below.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int OFFSET = 10;        
int comfortableCount = 0;

bool occupied[1020][1020];
bool comfortable[1020][1020];

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

bool isComfortable(int x, int y) {
    if (!occupied[x][y]) {
        return 0;
    }
    int count = 0;
    for (int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (occupied[nx][ny]) {
            count++;
        }
    }
    return (count == 3);
}

void updateCell(int x, int y) {
    if (x < 1 || x >= 1020 || y < 1 || y >= 1020 || occupied[x][y] == 0) {
        return;
    }
    if (!occupied[x][y]) {
        return;
    }

    bool wasComfortable = comfortable[x][y];
    bool nowComfortable = isComfortable(x, y);

    if (wasComfortable && !nowComfortable) {
        comfortable[x][y] = false;
        comfortableCount--;
    }
    else if (!wasComfortable && nowComfortable) {
        comfortable[x][y] = true;
        comfortableCount++;
    }
}

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        a += OFFSET;
        b += OFFSET;

        occupied[a][b] = true;

        vector<pair<int,int>> toCheck;
        toCheck.push_back({a, b});
        for (int j = 0; j < 4; j++){
            int nx = a + dx[j], ny = b + dy[j];
            toCheck.push_back({nx, ny});
            for (int k = 0; k < 4; k++){
                int nnx = nx + dx[k], nny = ny + dy[k];
                toCheck.push_back({nnx, nny});
            }
        }

        sort(toCheck.begin(), toCheck.end());
        toCheck.erase(unique(toCheck.begin(), toCheck.end()), toCheck.end());
        for (auto cell: toCheck){
            updateCell(cell.first, cell.second);
        }

        cout << comfortableCount << "\n";
    }
    return 0;
}

OFFSET = 10
SIZE = 1020
comfortableCount = 0
occupied = [[False] * SIZE for _ in range(SIZE)]
comfortable = [[False] * SIZE for _ in range(SIZE)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def isComfortable(x, y):
    if not occupied[x][y]:
        return False
    count = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if occupied[nx][ny]:
            count += 1
    return count == 3

def updateCell(x, y):
    global comfortableCount
    if x < 1 or x >= SIZE or y < 1 or y >= SIZE or not occupied[x][y]:
        return
    wasComfortable = comfortable[x][y]
    nowComfortable = isComfortable(x, y)
    if wasComfortable and not nowComfortable:
        comfortable[x][y] = False
        comfortableCount -= 1
    elif not wasComfortable and nowComfortable:
        comfortable[x][y] = True
        comfortableCount += 1

n = int(input())
for _ in range(n):
    a, b = map(int, input().split())
    a += OFFSET
    b += OFFSET
    occupied[a][b] = True

    toCheck = []
    toCheck.append((a, b))
    for j in range(4):
        nx = a + dx[j]
        ny = b + dy[j]
        toCheck.append((nx, ny))
        for k in range(4):
            nnx = nx + dx[k]
            nny = ny + dy[k]
            toCheck.append((nnx, nny))
    toCheck = set(toCheck)
    for cell in toCheck:
        updateCell(cell[0], cell[1])
    print(comfortableCount)