USACO Platinum 2016 February - Load Balancing

Official Analysis (C++)

Solution 1: With Segment Tree

Explanation

The problem can be solved by sweeping a line from bottom to top. This line divides the farm into two regions, north and south. At the beginning, all cows belong to the northern region.

For each of these lines, we need an efficient way to determine the optimal west/east partition to divide the farm into four pieces with the maximum number of cows appearing in one of the four regions, $M$, being minimized. To achieve this, we use two segment trees as our frequency tables to store the number of cows on a certain $x$ coordinate which belong to one of the two regions, north and south, respectively.

Then, we do a binary search on both segment trees to find the best west/east partition which minimizes $M$. In particular, we begin from the root of the segment trees and always add either the left or right subtrees to the western or eastern region, depending on which of these two options leads to the smallest increase of $M$.

At the end, we update our overall best solution and move the line to the next $y$-coordinate of interest. We add all cows with current $y$ coordinate to the southern region and remove them from the northern region.

Implementation

Time Complexity: $\mathcal{O}(N\log N)$

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

struct SegmentTree {
	int size;
	vector<int> tree;
	SegmentTree() : size(1 << 20) { tree.assign(size * 2, 0); }

	/**
	 * Increase the value at x by value, i.e. a[x] += value

Copy
import java.io.*;
import java.util.*;

public class Balancing {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("balancing.in"));

		int N = Integer.parseInt(br.readLine());
		Pair[] cows = new Pair[N];
		for (int i = 0; i < N; i++) {

Solution 2: With Binary Search

Explanation

Alternatively, we can also just binary search on the answer without using a PURQ data structure. To check if a chosen maximum number of cows in any of the four regions, henceforth referred to as $M^*$, is feasible, we calculate the maximum height of all four regions for each possible $x$ partition with at most $M^*$ cows in the region. We then go through every $x$ coordinate and check if the sum of the heights of the southern and northern regions is larger than the height of the farm. As there are each two regions in the north and south, we always take the minimum between north-west/north-east and south-west/south-east. If there is such an $x$ partition that leads to the sum being larger than the height of the farm, then there is one solution with the current $x$ and $y$ partition.

We do a coordinate compression on the $x$ and $y$ coordinates to simplify the implementation.

Implementation

Time Complexity: $\mathcal{O}(N\log N)$

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

/**
 * Calculate the maximum height of the left bottom region for each possible
 * partion based on the x coordinate which has maximum max_cows cows
 * in the region.
 * @return bound[i] is the maximum possible height for the region 0..i,
 * 0..bound[i], in which the number of cows is less than or equal to max_cows
 */