USACO Gold 2016 Open - Splitting the Field

Official Analysis (Java)

Copy
 Code Snippet: Test Case (Click to expand)

Explanation

Since the enclosures must be rectangular, there must be a vertical or horizontal line that separates the two. Otherwise, we'd have a case where one enclosure would have to overlap the other in order to enclose all the cows.

Thus, we'll perform two sweeps, one checking vertical splits, and the other checking horizontal splits. To keep track of the best answer, we'll keep prefix and suffix minimums and maximums to calculate each possible solution in $\mathcal{O}(1)$ time.

We can also use a binary search tree instead of prefix/suffix minimums and maximums. To do this, we can create two ordered sets: a set representing the current enclosure, and a set representing the other enclosure. As we sweep across these coordinates, we'll add them to the current set and remove them from the other enclosure. To query, we'll fetch the minimum and maximum values from the sets.

Implementation

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

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

using ll = long long;

int n;
ll ans = 0;
vector<pair<int, int>> cows;

/** returns the maximum area saved by testing splits along cows[i].first */

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

public class SplittingTheField {
	// returns updated min/maxs when considering a new coordinate
	public static Pair upd(Pair a, long b) {
		return new Pair(Math.min(a.first, b), Math.max(a.second, b));
	}

	public static void main(String[] args) throws Exception {

Copy
with open("split.in") as read:
	n = int(read.readline())
	cows = [list(map(int, read.readline().split())) for _ in range(n)]

ans = 0


def search():
	"""
	returns the maximum area saved by testing splits along cows[i].first