USACO Bronze 2020 December - Stuck in a Rut

Official Analysis (C++ and Java)

Explanation

Since $x, y \leq 10^9$, we can't simulate each time period. Instead, let's try to identify when pairs of cows are going to intersect.

One important observation is that cows can't move backwards, so the only way for two cows to collide is if $n[x] > e[x]$ and $n[y] < e[y]$.

In other words, a cow can only run into the rut of another cow when the two cows are positioned like so:

Now we can sort cows by their starting coordinates, which ensures that earlier collisions will execute first (i.e., simulating left to right), and then simulate those collisions.

Implementation

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

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

struct Cow {
	int x, y;
	int ind;
};

int main() {
	int n;

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

public class StuckInARut {
	public static void main(String[] args) throws IOException {
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(r.readLine());
		List<int[]> nCows = new ArrayList<>();
		List<int[]> eCows = new ArrayList<>();

Copy
n = int(input())
n_cows = []
e_cows = []

for i in range(n):
	dir_, d, y = input().split()
	if dir_ == "N":
		n_cows.append((int(d), int(y), i))
	elif dir_ == "E":
		e_cows.append((int(d), int(y), i))

Video Solution

By Melody Yu