USACO Silver 2016 February - Load Balancing

Official Analysis (Java)

Video Solution

By Varun Ragunath

Solution 1

Similar to the analysis.

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

Copy
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

struct Cow {

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"));
		int cowNum = Integer.parseInt(read.readLine());
		// The array of cows (to be sorted by x-pos)
		int[][] byX = new int[cowNum][2];
		for (int c = 0; c < cowNum; c++) {

Copy
from typing import List, Tuple


with open("balancing.in") as read:
	# The array of cows (to be sorted by x-pos)
	by_x = []
	for _ in range(int(read.readline())):
		by_x.append(tuple(int(i) for i in read.readline().split()))

Solution 2

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

The solution to the Bronze version of this problem runs in $\mathcal O(N^3)$ time, but is not fast enough to pass the Silver version. One way to speed up the Bronze solution is to check only a constant number of $x$ and $y$-coordinates that are close to the median $x$ or $y$, respectively. This would improve the time complexity to $\mathcal O(N)$. However, such a solution cannot be correct. For example, consider the case where $N=999$ and $x_i=y_i=2i-1$. Then $M=333$, and the $x$ and $y$ coordinates we need to select to obtain this $M$ are rather far away from their respective medians.

Nevertheless, we can still speed up the Bronze solution by a constant factor by checking fewer $x$ and $y$ coordinates. Note that if we increase the $x$-coordinate of the north-south fence by two and there are still at most $\frac{N}{3}$ cows to the left of the fence, then $M$ stays the same or decreases. Thus, we can reduce the number of $x$-coordinates we need to check to $\frac{N}{3}+\mathcal O(1)$. Similarly, the number of $y$-coordinates we need to check is also $\frac{N}{3}+\mathcal O(1)$. This reduces the number of operations in the Bronze solution by a factor of 9, which is enough to pass the Silver version.

Copy
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

struct Cow {

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"));
		int cowNum = Integer.parseInt(read.readLine());

		int[][] cows = new int[cowNum][2];
		int[] xPos = new int[cowNum];