USACO Silver 2018 December - Convention

Official Analysis (C++)

Explanation

Consider a possible maximum waiting time $X$, if we can't file all of the cows into the buses with this constraint, we can't process the cows with a smaller $X$ either. It remains to find how to check if some $X$ can be processed.

Instead of the problem being:

Is it possible to file the cows in $M$ buses with a maximum waiting time of $X$?

We'll transform the problem into:

What's the minimum number of buses needed to transport the cows with a maximum waiting time of $X$?

This simplification allows us to break processing a cow into three cases:

1. Adding this cow will cause the first cow to exceed the maximum waiting time.
2. Adding this cow will overflow the bus capacity.
3. Adding this cow will satisfy all of the constraints.

It takes $\mathcal{O}(\log N)$ time to binary search on $X$ and $\mathcal{O}(N)$ time to validate a possible time constraint, so this leaves us with a $\mathcal{O}(N\log N)$ solution, which fits comfortably under the time limit.

Implementation

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

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

public class convention {
	static int N;
	static int numBus;
	static int cap;
	static int[] cow;
	public static void main(String[] args) throws IOException {
		InputReader in = new InputReader("convention.in");

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

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

int n, m, c;
vector<int> arrivals;

Copy
def validate(k: int) -> bool:
	bus = 0  # number of buses needed
	cow = 0  # current cow
	lcow = 0  # earliest cow on this bus

	while cow < n:
		if cow == lcow:
			bus += 1

		# can't satisfy time constraint by adding this cow