My java solution to Contaminated Milk 2015 December Bronze follows similiar methodology as default solution but still fails on 9th testcase.
The design of my solution is to:
- organize the input by person, the index of the
pmts
array isp-1
- find for each person, what milks they drank before they got sick (
bad_milks
) - update the
bad_milks_common
ArrayList with new bad milks that were discovered and remove milks that are not bad anymore
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader r = new BufferedReader(new FileReader("badmilk.in"));
PrintWriter pw = new PrintWriter(new FileOutputStream("badmilk.out"));
StringTokenizer st = new StringTokenizer(r.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());
int[][][] pmts = new int[N][D][2];
int[] counters = new int[N];
for(int i = 0; i < D; i++) {
st = new StringTokenizer(r.readLine());
int p = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int t = Integer.parseInt(st.nextToken());
int[] pmt = new int[] {m, t};
pmts[p-1][counters[p-1]] = pmt;
counters[p-1]++;
}
int[] sts = new int[N];
for(int i = 0; i < S; i++) {
st = new StringTokenizer(r.readLine());
int p = Integer.parseInt(st.nextToken());
int t = Integer.parseInt(st.nextToken());
sts[p-1] = t;
}
ArrayList<Integer> bad_milks_common = new ArrayList<>();
for(int i = 0; i < sts.length; i++) {
if(sts[i]!=0) {
ArrayList<Integer> bad_milks = new ArrayList<>();
for (int j = 0; j < pmts[i].length; j++) {
if(pmts[i][j][1] < sts[i]) {
if(i==0) {
bad_milks_common.add(pmts[i][j][0]);
} else {
bad_milks.add(pmts[i][j][0]);
}
}
}
if(i!=0) {
for (int k = 0; k < bad_milks_common.size(); k++) {
if (!bad_milks.contains(bad_milks_common.get(k))) {
bad_milks_common.remove(k);
}
}
for(int k = 0; k < bad_milks.size(); k++) {
if(!bad_milks_common.contains(bad_milks.get(k))) {
bad_milks_common.add(bad_milks.get(k));
}
}
}
}
}
int res = 0;
for(int i = 0; i < bad_milks_common.size(); i++) {
if(bad_milks_common.get(i)!=0) {
int counter = 0;
for(int j = 0; j < pmts.length; j++) {
for(int k = 0; k < pmts[j].length; k++) {
if(pmts[j][k][0]==bad_milks_common.get(i)) {
counter++;
break;
}
}
}
if(counter>res) {
res = counter;
}
}
}
System.out.println(res);
pw.println(res);
pw.close();
}
}