USACO Bronze 2018 December - The Bucket List

Authors: Ananth Kashyap, Sathvik Chundru, Brad Ma, Aadit Ambadkar

Edit This Page

Official Analysis (C++)

Solution 1 - Brute Force

Iterate over all possible times and calculate the number of buckets required at each time. We calculate the number of buckets by looping over all cows and checking which cows need to be milked.

The maximum number of buckets needed across all time is our answer.

Implementation

Time Complexity: O(N⋅T)\mathcal{O}(N \cdot T), where TT is the maximum time in the input.

C++

#include <fstream>
#include <iostream>
#include <vector>


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


const int MAX_TIME = 1000;

Java

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


public class BList {
	static final int MAX_TIME = 1000;


	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("blist");
		int n = io.nextInt();
		int[][] cows = new int[n][];

Python

MAX_TIME = 1000


with open("blist.in") as read:
	n = int(read.readline())
	cows = [[int(i) for i in read.readline().split()] for _ in range(n)]


# The maximum number of buckets needed
max_buckets = 0


"""

Solution 2 - Sweep

Solution 1 does a lot of unnecessary work, as we don't actually have to recount the buckets for every time step. This implementation keeps track of all the changes in milking times and iterates through all the time steps at once.

Implementation

Time Complexity O(N+T)\mathcal{O}(N + T)

C++

#include <fstream>
#include <iostream>
#include <vector>


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


const int MAX_TIME = 1000;

Java

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


public class BList {
	static final int MAX_TIME = 1000;


	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("blist");
		int n = io.nextInt();
		int[] change = new int[MAX_TIME + 1];

Python

MAX_TIME = 1000


change = [0 for _ in range(MAX_TIME + 1)]
with open("blist.in") as read:
	n = int(read.readline().strip())
	for _ in range(n):
		start, end, amt = map(int, read.readline().strip().split())


		# at the start, we'll need some additional buckets
		change[start] += amt

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum