USACO Bronze 2015 December - Contaminated Milk

Official Analysis (Java)

Video Solution

By Yifan Ma

Explanation

We can do a simple brute force to find out which milk could possibly be bad, and then see how many people that milk could have infected in total.

Since FJ needs one medicine for each person who could possibly get sick, we can just take the maximum possible number of infected people over all milk types that could have possibly gone bad.

The main issue is checking if a milk could have been the one that went bad. To resolve this, let's treat both a person drinking milk and a person getting sick as a type of event. Then, we can have a list of events sorted by time. Note that sick events must be before drinking events if they occur at the same time because one can only get sick if they drank the milk at a strictly earlier point in time. The sample case in this format would be as follows:

With this list of events, we can then go through marking the people that could have possibly gotten sick and checking each event where a person got sick if they could have possibly gotten sick.

Implementation

Time Complexity: $\mathcal{O}(M(D+N))$

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

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

/*

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

public class BadMilk {
	/*
	 * Let's treat someone drinking milk and someone getting sick
	 * as both "events".
	 * We can differentiate the two by setting the value of milk
	 * as -1 for someone getting sick.
	 */

Copy
from functools import cmp_to_key

with open("badmilk.in") as read:
	data = [int(i) for i in read.readline().split()]
	people_num, milk_num, drink_times, sick_times = data

	"""
	Let's treat someone drinking milk and someone getting sick
	as both "events".
	An event will be represented by a 3-tuple formatted like so: