USACO Bronze 2018 December - The Bucket List

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

Edit This Page

Official Analysis (C++)

Implementation 1 - Brute Force

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


"""

Implementation 2 - Sweep

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

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.

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