USACO 2021 January Contest Silver Division - Spaced Out

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

The condition is met when the free and occupied places alternate between columns/rows, not both at once, otherwise there will be either one cow per area or \(3\). Thus, we can apply a greedy algorithm in which we check for each way of placing the cows (alternating on columns, rows) which is the largest sum between the occupied areas/(future) free areas.

Source code

The source code in C++ can be seen below.

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

int n, mat[1005][1005], used[1005][1005];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> mat[i][j];
        }
    }
    int mx1 = 0;
    for (int i = 1; i <= n; i++) {
        int s[2] = {0};
        for (int j = 1; j <= n; j++) {
            s[j % 2] += mat[i][j];
        }
        mx1 += max(s[1], s[0]);
    }
    int mx2 = 0;
    for (int j = 1; j <= n; j++) {
        int s[2] = {0};
        for (int i = 1; i <= n; i++) {
            s[i % 2] += mat[i][j];
        }
        mx2 += max(s[0], s[1]);
    }
    cout << max(mx1, mx2);
    return 0;
}