Checklist
Make sure to read all of How to ask for help on a problem before asking for help.
Problem Info
Haybale Feast: USACO
Question
I am not sure why my code works for some test cases but not others. The code works for cases 1,2,3 and 5,6,7, but not any others. I get ! marks on the other test cases.
What I’ve Tried
I’ve tried using a try-catch block on my while loop, because I thought I might have been getting array index out of bound errors, but that did not work.
My Work
/*
import java.io.*;
import java.util.*;
public class HaybaleFeast {
static TreeMap<Integer, Integer> multiset = new TreeMap<>();
static int n, m;
static int[] flavor;
static int[] spice;
public static void main(String[] args) throws IOException {
BufferedReader f = new BufferedReader(new FileReader("hayfeast.in"));
PrintWriter out = new PrintWriter(new FileWriter("hayfeast.out"));
StringTokenizer st = new StringTokenizer(f.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
flavor = new int[n];
spice = new int[n];
for(int i = 0; i < n; i++) {
StringTokenizer st1 = new StringTokenizer(f.readLine());
int fl = Integer.parseInt(st1.nextToken());
int sp = Integer.parseInt(st1.nextToken());
flavor[i] = fl;
spice[i] = sp;
}
// flavor stores the flavor of each haybale, spice stores the spicyness value
int left = 0;
int right = 0;
int sum = 0;
int min = Integer.MAX_VALUE;
// sum is the current meal flavor sum
// left is the leftmost haybale, right is the rightmost haybale
// min is set to max value so that Math.min will always choose the right value at first
try{
outer:
while(right < n) {
while(sum < m) {
sum+=flavor[right];
add(spice[right]);
if(right >= n) break outer;
right++;
// add each new haybale to the sum, add the spicyness to the multiset
}
min = Math.min(min, multiset.lastKey());
sum-=flavor[left];
remove(spice[left]);
left++;
// change the minimum if the new one is smaller (I used multiset.lastKey because that would be the largest spicyness value of a haybale within the meal)
// decrease sum by the leftmost haybale's flavor, since we are not using that one anymore
// remove the leftmost haybale's spicyness from the multiset because we are not using that anymore
// increment leftmost haybale
}`
}
catch(Exception e) {
}
out.println(min);
out.close();
f.close();
}
static void add(int x) {
if(!multiset.containsKey(x)) {
multiset.put(x,1);
}
else {
multiset.put(x, multiset.get(x)+1);
}
}
static void remove(int x) {
Integer current = multiset.get(x);
if(current != null) {
if(current == 1) multiset.remove(x);
else multiset.put(x, current - 1);
}
}
}*/
Add explanation of code here
I used a 2-pointer to calculate the minimum sums for each meal considering the left-most haybale. I also used a multiset to store the spice values to help calculate the minimums.
