Hi Everyone,
I am doing the USACO Gold problem Snow Boots. I am experiencing inconsistency in my code between the USACO judge and the IntelliJ IDEA CE runTime environment.
My solution is very similar to the solution for Bit Inversions. Using binary search, I created a matrix depthIndices that stores all indices for each snow depth in sortedDepths. For each possible depth, I used the Bit Inversions algorithm to find the width of the maximum “gap”, a contiguous sequence of tiles whose snow depth exceeds the possible depth. One more than this is the minimum step size for that depth. The results are stored in minStep.
Then, for each boot, I used binary search to find the greatest recorded depth less than or equal to its depth, and determined whether FJ can make the trek. My code is below:
import java.io.*;
import java.util.*;
public class SnowBoots {
public static void main(String[] args) throws IOException {
// BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
// PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
BufferedReader in = new BufferedReader(new FileReader("snowboots.in"));
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("snowboots.out")));
StringTokenizer st = new StringTokenizer(in.readLine());
int numTiles = Integer.parseInt(st.nextToken());
int numBoots = Integer.parseInt(st.nextToken());
int[] tileDepths = new int[numTiles];
HashSet<Integer> distinctDepths = new HashSet<>();
StringTokenizer stt = new StringTokenizer(in.readLine());
for (int i = 0; i < numTiles; i++) {
tileDepths[i] = Integer.parseInt(stt.nextToken());
distinctDepths.add(tileDepths[i]);
}
Integer[] sortedDepths = distinctDepths.stream().sorted().toArray(Integer[]::new);
// Given a depth, all indexes in tiles with that depth
ArrayList<ArrayList<Integer>> depthIndices = new ArrayList<>(sortedDepths.length);
for (int i = 0; i < sortedDepths.length; i++) {
depthIndices.add(new ArrayList<>());
}
for (int i = 0; i < numTiles; i++) {
int index = Arrays.binarySearch(sortedDepths, tileDepths[i]);
depthIndices.get(index).add(i);
}
// Given an index of sortedDepths, minimum step needed to pass
int[] minStep = new int[sortedDepths.length];
minStep[minStep.length - 1] = 1;
// TreeSet containing start and ends of gaps
// As standard end is one more than actual end
TreeSet<GapPoint> gaps = new TreeSet<>();
// Max Heap containing lengths of gaps
PriorityQueue<Integer> gapLengths = new PriorityQueue<>(Collections.reverseOrder());
// Array containing frequency of gaps
int[] gapFrequencies = new int[numTiles];
for (int i = minStep.length - 2; i >= 0; i--) {
int start = depthIndices.get(i + 1).get(0);
for (int index = 1; index < depthIndices.get(i + 1).size(); index++) {
if (depthIndices.get(i + 1).get(index) - depthIndices.get(i + 1).get(index - 1) > 1) {
add(gaps, gapLengths, gapFrequencies, start, index);
start = index;
}
}
add(gaps, gapLengths, gapFrequencies, start, depthIndices.get(i + 1).get(depthIndices.get(i + 1).size() - 1) + 1);
while (gapFrequencies[gapLengths.peek() - 1] == 0) gapLengths.poll();
minStep[i] = gapLengths.peek() + 1;
}
// For each boot, binary search to find largest depth smaller than it
for (int b = 0; b < numBoots; b++) {
StringTokenizer stb = new StringTokenizer(in.readLine());
int maxDepth = Integer.parseInt(stb.nextToken());
int maxStep = Integer.parseInt(stb.nextToken());
int index = Arrays.binarySearch(sortedDepths, maxDepth);
if (index < 0) index = -index - 2;
out.println(maxStep >= minStep[index] ? "1" : "0");
}
out.close();
}
static void add(TreeSet<GapPoint> gaps, PriorityQueue<Integer> gapLengths, int[] gapFrequencies, int start, int end) {
GapPoint floor = gaps.floor(new GapPoint(start, true));
GapPoint ceiling = gaps.ceiling(new GapPoint(end, false));
// Determine left side of gap
if (floor != null) {
assert !floor.start;
if (floor.index == start) {
gaps.remove(floor);
GapPoint begin = gaps.lower(floor);
gapFrequencies[floor.index - begin.index - 1]--;
start = begin.index;
}
}
// Determine right side of gap
if (ceiling != null) {
assert ceiling.start;
if (ceiling.index == end) {
gaps.remove(ceiling);
GapPoint ending = gaps.higher(ceiling);
gapFrequencies[ending.index - ceiling.index - 1]--;
end = ending.index;
}
}
gaps.add(new GapPoint(start, true));
gaps.add(new GapPoint(end, false));
gapLengths.add(end - start);
gapFrequencies[end - start - 1]++;
}
}
class GapPoint implements Comparable<GapPoint> {
public int index;
public boolean start;
public GapPoint(int index, boolean start) {
this.index = index;
this.start = start;
}
public int compareTo(GapPoint gp) {
return this.index - gp.index;
}
}
When run on USACO judges, the first four test cases get AC, but test cases 5-12 get an exclamation mark. I checked my code and it only stores at most 13 * 10^5 ints, which is below the memory limit. This means that there must be a runtime error.
When I ran the code on IntelliJ IDEA CE using the Command Line app, it does not have any runtime errors. I was wondering why this inconsistency is happening. Below are the two screenshots of the runs.
Thanks,
rayfish