2015 Dec Bronze Problem 3 Contaminated Milk

Official Problem Statement

Contaminated Milk

Problem

This problem is called "Contaminated Milk" from the USACO 2015 December contest, Bronze division.

In the problem, Farmer John's N cows (1 <= N <= 50) each drank some milk from a collection of M distinct milk producers (1 <= M <= 50) at various points in time (1 <= T <= 100). Unfortunately, some of the milk was contaminated and caused some cows to become sick. A cow becomes sick exactly P time units after drinking contaminated milk (1 <= P <= 100). Each cow either gets sick exactly once after drinking some milk, or does not get sick at all, and you know the time that each cow got sick, if it did.

The task is to determine which milk producer is responsible for causing the cows to get sick, and the number of cows that got sick from drinking contaminated milk.

Solution

The problem can be solved with a straightforward simulation approach.

We can simulate the process in the following steps:

• For each milk producer, we can iterate through each time unit and each cow. If the cow drank milk from that producer at that time, and if the cow gets sick at a later time exactly P units away, then we suspect that this milk producer might be the one that produced the contaminated milk.
• For each suspected milk producer, we can check if every cow who drank milk from this producer got sick exactly P units after drinking the milk. If so, we confirm this milk producer as a culprit.
• Finally, we output the maximum number of cows that got sick from drinking the milk of a confirmed milk producer.

This approach will find all the possible milk producers that may have caused the sickness and count the maximum number of cows that could have been infected by each of these producers. The solution runs in a reasonable time since the inputs are relatively small.

The key part of this solution is careful implementation: we must keep track of when each cow drank milk from each producer, and when each cow got sick. This can be done with simple array or list structures, with the indices representing the cows or milk producers, and the values representing the times.

Code

C++

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

using namespace std;

vector<int> personDrink;
vector<int> milkDrink;
vector<int> timeDrink;
vector<int> personSick;
vector<int> timeSick;

void initializeDrinkArrays(int d, ifstream &fin) {
    personDrink.resize(d);
    milkDrink.resize(d);
    timeDrink.resize(d);
    for(int i = 0; i < d; i++) {
        fin >> personDrink[i] >> milkDrink[i] >> timeDrink[i];
    }
}

void initializeSickArrays(int s, ifstream &fin) {
    personSick.resize(s);
    timeSick.resize(s);
    for(int i = 0; i < s; i++) {
        fin >> personSick[i] >> timeSick[i];
    }
}

bool isMilkBad(int milkType) {
    for(int i = 0; i < personSick.size(); i++) {
        bool personDrank = false;
        for(int j = 0; j < personDrink.size(); j++) {
            if(personDrink[j] == personSick[i] && milkDrink[j] == milkType && timeDrink[j] < timeSick[i]) {
                personDrank = true;
                break;
            }
        }
        if(!personDrank) {
            return false;
        }
    }
    return true;
}

int countPeopleWhoDrank(int milkType) {
    vector<bool> didDrink(51, false);
    for(int i = 0; i < personDrink.size(); i++) {
        if(milkDrink[i] == milkType) {
            didDrink[personDrink[i]] = true;
        }
    }
    int drinkCount = 0;
    for(bool drank : didDrink) {
        if(drank) {
            drinkCount++;
        }
    }
    return drinkCount;
}

int main() {
    ifstream fin("badmilk.in");
    ofstream fout("badmilk.out");

    int n, m, d, s;
    fin >> n >> m >> d >> s;

    initializeDrinkArrays(d, fin);
    initializeSickArrays(s, fin);

    int maxSick = 0;
    for(int i = 1; i <= m; i++) {
        if(isMilkBad(i)) {
            int sickCount = countPeopleWhoDrank(i);
            maxSick = max(maxSick, sickCount);
        }
    }

    fout << maxSick << endl;

    return 0;
}

Java

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

public class badmilk {
    private static int[] personDrink;
    private static int[] milkDrink;
    private static int[] timeDrink;
    private static int[] personSick;
    private static int[] timeSick;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("badmilk.in"));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("badmilk.out")));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        int s = Integer.parseInt(st.nextToken());

        initializeDrinkArrays(d, br);
        initializeSickArrays(s, br);
        
        int maxSick = 0;
        for(int i = 1; i <= m; i++) {
            if(isMilkBad(i)) {
                int sickCount = countPeopleWhoDrank(i);
                maxSick = Math.max(maxSick, sickCount);
            }
        }
        
        pw.println(maxSick);
        pw.close();
    }
    
    private static void initializeDrinkArrays(int d, BufferedReader br) throws IOException {
        personDrink = new int[d];
        milkDrink = new int[d];
        timeDrink = new int[d];
        for(int i = 0; i < d; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            personDrink[i] = Integer.parseInt(st.nextToken());
            milkDrink[i] = Integer.parseInt(st.nextToken());
            timeDrink[i] = Integer.parseInt(st.nextToken());
        }
    }
    
    private static void initializeSickArrays(int s, BufferedReader br) throws IOException {
        personSick = new int[s];
        timeSick = new int[s];
        for(int i = 0; i < s; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            personSick[i] = Integer.parseInt(st.nextToken());
            timeSick[i] = Integer.parseInt(st.nextToken());
        }
    }

    private static boolean isMilkBad(int milkType) {
        for(int i = 0; i < personSick.length; i++) {
            if(!didPersonDrinkBefore(personSick[i], milkType, timeSick[i])) {
                return false;
            }
        }
        return true;
    }

    private static boolean didPersonDrinkBefore(int person, int milkType, int time) {
        for(int i = 0; i < personDrink.length; i++) {
            if(personDrink[i] == person && milkDrink[i] == milkType && timeDrink[i] < time) {
                return true;
            }
        }
        return false;
    }

    private static int countPeopleWhoDrank(int milkType) {
        boolean[] didDrink = new boolean[51];
        for(int i = 0; i < personDrink.length; i++) {
            if(milkDrink[i] == milkType) {
                didDrink[personDrink[i]] = true;
            }
        }
        int drinkCount = 0;
        for(boolean drank : didDrink) {
            if(drank) {
                drinkCount++;
            }
        }
        return drinkCount;
    }
}

Python

def initialize_drink_arrays(d, lines):
    global personDrink, milkDrink, timeDrink
    personDrink = [0]*d
    milkDrink = [0]*d
    timeDrink = [0]*d
    for i in range(d):
        personDrink[i], milkDrink[i], timeDrink[i] = map(int, lines[i].split())

def initialize_sick_arrays(s, lines):
    global personSick, timeSick
    personSick = [0]*s
    timeSick = [0]*s
    for i in range(s):
        personSick[i], timeSick[i] = map(int, lines[i].split())

def is_milk_bad(milkType):
    for i in range(len(personSick)):
        personDrank = False
        for j in range(len(personDrink)):
            if (personDrink[j] == personSick[i] and milkDrink[j] == milkType and timeDrink[j] < timeSick[i]):
                personDrank = True
                break
        if not personDrank:
            return False
    return True

def count_people_who_drank(milkType):
    didDrink = [False]*51
    for i in range(len(personDrink)):
        if milkDrink[i] == milkType:
            didDrink[personDrink[i]] = True
    drinkCount = sum(didDrink)
    return drinkCount

def main():
    with open("badmilk.in", "r") as fin:
        lines = fin.readlines()
    n, m, d, s = map(int, lines[0].split())
    initialize_drink_arrays(d, lines[1:d+1])
    initialize_sick_arrays(s, lines[d+1:])
    maxSick = 0
    for i in range(1, m+1):
        if is_milk_bad(i):
            sickCount = count_people_who_drank(i)
            maxSick = max(maxSick, sickCount)
    with open("badmilk.out", "w") as fout:
        fout.write(str(maxSick)+"\n")

if __name__ == "__main__":
    main()