Debugging Help on CCC Firehose Problem

Debugging Help
#1

Problem Info

CCC '10 S3 - Firehose - https://dmoj.ca/problem/ccc10s3

Question

My program passed the first 8 test cases and got wrong answer on the 9th one. I cannot find the error in my code.

What I’ve Tried

I don’t believe you can view CCC test cases. I’ve also tried copy pasting parts of the C++ solution code into my solution and converting it to java to help debug but I still haven’t gotten it to work.

My Work

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

public class firehose {
	static int N;
	static long[] ads;
	static int maxHydrant;
	static final int MAX = (int) 10e9;

	static boolean valid (int length) throws IOException {
		long hydrantPos;
		int numHydrant;
		int end;
		int n;
		boolean works;
		for (int start = 0; start < N; start++) {
			numHydrant = 0;
			n = start;
			end = start + N;
			works = true;
			while (n < end && works) {
				hydrantPos = ads[n % N] + (2 * length);
				while (n < end && ads[n % N] + ((n / N) * MAX) <= hydrantPos) {
					n++;
				}
				numHydrant++;
				if (numHydrant > maxHydrant) works = false;
			}
			if (works) return true;
		}
		return false;
	}

	public static void main (String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		N = Integer.parseInt(reader.readLine());
		ads = new long[N];
		for (int n = 0; n < N; n++) {
			ads[n] = Integer.parseInt(reader.readLine());
		}
		Arrays.sort(ads);
		maxHydrant = Integer.parseInt(reader.readLine());
		
		int lt = 0;
		int rt = MAX;
		int mid;
		while (lt < rt) {
			mid = (lt + rt) / 2;
			if (valid(mid)) rt = mid;
			else lt = mid + 1;
		}
		out.println(lt);
		out.close();
	}
}

I used binary search. During the validity check, I looped through all possible starting positions to start placing fire hydrants and checked if it was possible to connect each house to a fire hydrant with the given length.