USACO 2016 February Contest Bronze Division - Load Balancing

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

The main observation is that we only care about points adjacent to the $n$ cows, so we can brute force the algorithm.

Source codes

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

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

int main()
{
    ifstream cin("balancing.in");
    ofstream cout("balancing.out");

    int n, b;
    cin >> n >> b;

    vector<int> vx(n+1), vy(n+1);

    for(int i = 1; i <= n; i++)
        cin >> vx[i] >> vy[i];

    int ans = n;

    for(int ii = 1; ii <= n; ii++)
        for(int jj = 1; jj <= n; jj++)
            for(int deltax = -1; deltax <= 1; deltax += 2)
                for(int deltay = -1; deltay <= 1; deltay += 2)
                {
                    int medianx = vx[ii] + deltax;
                    int mediany = vy[jj] + deltay;
                    int cnt[4] = {0};
                    for(int i = 1; i <= n; i++)
                    {
                        if(vx[i] < medianx && vy[i] < mediany)
                            cnt[0]++;
                        if(vx[i] < medianx && vy[i] > mediany)
                            cnt[1]++;
                        if(vx[i] > medianx && vy[i] < mediany)
                            cnt[2]++;
                        if(vx[i] > medianx && vy[i] > mediany)
                            cnt[3]++;
                    }

                    ans = min(ans, max(cnt[0], max(cnt[1], max(cnt[2], cnt[3]))));
                }

    cout << ans;
    return 0;
}

with open("balancing.in", "r") as fin:
    n, b = map(int, fin.readline().split())
    vx = [0] * (n + 1)
    vy = [0] * (n + 1)
    for i in range(1, n + 1):
        vx[i], vy[i] = map(int, fin.readline().split())

ans = n
for ii in range(1, n + 1):
    for jj in range(1, n + 1):
        for deltax in (-1, 1):
            for deltay in (-1, 1):
                medianx = vx[ii] + deltax
                mediany = vy[jj] + deltay
                cnt = [0, 0, 0, 0]
                for i in range(1, n + 1):
                    if vx[i] < medianx and vy[i] < mediany:
                        cnt[0] += 1
                    if vx[i] < medianx and vy[i] > mediany:
                        cnt[1] += 1
                    if vx[i] > medianx and vy[i] < mediany:
                        cnt[2] += 1
                    if vx[i] > medianx and vy[i] > mediany:
                        cnt[3] += 1
                ans = min(ans, max(cnt))

with open("balancing.out", "w") as fout:
    fout.write(str(ans))