Official Analysis (Java)

Video Solution

By Varun Ragunath

Solution 1

Let's have two lists of the cows: one sorted by x-coordinate, the other by y-coordinate.

Lets say that we had one cow at $\mathcal{x}$ = 1, and another cow at $\mathcal{x}$ = 999999. Notice that whatever vertical fence that we place between those two cows, they will always be in different regions. This same logic applies for horizontal fences. Thus, we we only need to consider fence positions at x + 1 or y + 1, because they will always split the cows into different regions, due to being odd positions.

So, we can brute force each possible vertical fence between adjacent cows in our list sorted by x-coordinates where there is at max $N - 1$ possibilities.

Now, for each vertical fence, we want to find the position of a horizontal fence that minimizes the answer. To do this, we can maintain two lists representing cows to the left and right of the vertical fence. We can then loop through our cow list sorted by y-coordinates, and if any cow is to the left of the vertical fence, we add it to the left list, and if they are to the right, we add them to the right list.

Again, we can brute force through each possible horizontal fence between adjacent cows in our list sorted by y-coordinates, where there is at max $N$ possibilites, while keeping track of how many cows are to the left and right. For each partition, we can find how many cows are in each quadrant by utilizing the sizes of the left and right lists, and the count of cows to the left and right. The answer at this case is the max out of all four quadrants.

The final answer is the minimum out of all such answers.

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];