USACO 2016 February Contest Silver Division - Load Balancing

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Unlike the bronze version, we can't use the \(O(n^3)\) algorithm anymore.

Instead, let's process points based on \(x\) and then we can sweep through \(y\)'s to optimize the bronze algorithm. Basically, what we want to do is to rely on the fact that the only relevant positions where we should perform a split along the Ox axis are around the coordinates of points and because of this, we only have to run the splitting algorithm \(n\) times.

After that, in order to simulate the distribution of cells across the four regions generated by the two cuts, we will run a algorithm similar in style (but much easier) to a sweep line method where we move numbers between the regions as each point can be moved at most once based on its \(y\) coordinate.

Source code

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

#include <algorithm>
#include <fstream>
using namespace std;

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

    int n;
    cin >> n;

    vector<pair<int, int> > v(n + 1);

    for (int i = 1; i <= n; i++) {
        cin >> v[i].first >> v[i].second;
    }
    sort(v.begin() + 1, v.begin() + n + 1);

    int ans = n;

    for (int ii = 1; ii <= n; ii++) {
        vector<int> v12, v34;
        for (int i = 1; i <= n; i++) {
            if (v[i].first <= v[ii].first) {
                v12.push_back(v[i].second);
            }
            else {
                v34.push_back(v[i].second);
            }
        }
        sort(v12.begin(), v12.end());
        sort(v34.begin(), v34.end());
        int L = 0, L2 = 0;
        ans = min(ans, max((int)v12.size(), (int)v34.size()));
        while (L < v12.size() || L2 < v34.size()) {
            int mini = (1 << 30);
            if (L < v12.size()) {
                mini = min(mini, v12[L]);
            }
            if (L2 < v34.size()) {
                mini = min(mini, v34[L2]);
            }
            while (L < v12.size() && v12[L] == mini) {
                L++;
            }
            while (L2 < v34.size() && v34[L2] == mini) {
                L2++;
            }
            ans = min(ans, max(L, max(L2, max((int)v12.size() - L, (int)v34.size() - L2))));
        }
    }

    cout << ans;
    return 0;
}