USACO Bronze 2016 February - Load Balancing

C++

Explanation

We solve this problem by brute forcing over all possible placements of the two fences. Note that we only need to consider fence positions at $x + 1$ and $y + 1$ for each cow's at $(x, y)$ because these are the only positions that affect the regions without passing through a cow. For each pair of fences, we count the number of cows in each of the four regions and update our maximum accordingly.

Implementation

Copy
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <set>
#include <vector>

using namespace std;

int main() {
	freopen("balancing.in", "r", stdin);

Java

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

public class Balancing {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("balancing.in"));
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int cowNum = Integer.parseInt(initial.nextToken());
		// We won't use this variable
		int maxPos = Integer.parseInt(initial.nextToken());

Python

Copy
with open("balancing.in") as read:
	# max_pos won't be used
	cow_num, max_pos = [int(i) for i in read.readline().split()]

	x_vals = []
	y_vals = []
	v_fence = set()
	h_fence = set()
	for _ in range(cow_num):
		x, y = [int(i) for i in read.readline().split()]