Explanation

Let $\texttt{possible}(i)$ be true if it's possible to connect a house to at least one fire hydrant after placing $k$ fire hydrants such that the length of each hose is $i$. We know that if $\texttt{possible}(i)$ is true, $\texttt{possible}(i + 1)$ is also true, because an increase in the length of the hose will not prevent a valid configuration of fire hydrants from being built. Consequently, $\texttt{possible}(i)$ is monotonic, and we can binary search for the smallest value of $i$ such that $\texttt{possible}(i)$ is true.

We use a greedy algorithm to find $\texttt{possible}(i)$. Firstly, we want to sort all houses by their address. For each $j$ from $1...n$, let $h_j$ be the address of the $j$th house. Place a fire hydrant at address $h_j + i$, and this hydrant will cover all houses in the range $[h_j, h_j + 2i]$. We can repeat this process for the first house to the right whose address does not fall into this range until every house can be connected with at least one first hydrant. Note that due to the circular nature of the street, we must do all calculations$\mod 1000000$. If the number of hydrants needed is greater than the number of fire hydrants allowed, $\texttt{possible}(i)$ is false; otherwise, it is true.

Implementation

Time Complexity: $\mathcal O(h^2\times log(\texttt{max}(H_i)))$

Copy
#include <bits/stdc++.h>
using namespace std;

const int MAX_H = 1000;
const int STREET_SIZE = 1000000;

int num_houses;
int num_hydrants;
int houses[MAX_H];

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

public class Firehose {
	private static final int MAX_H = 1000;
	private static final int STREET_SIZE = 1000000;

	private static boolean possible(int length, int numHydrants, int[] houses) {
		for (int i = 0; i < houses.length; i++) {
			int needed = 0;  // Number of fire hydrants that are needed.

Copy
MAX_H = 1000
STREET_SIZE = 1000000


def possible(length: int, num_hydrants: int, houses: list) -> bool:
	for i in range(len(houses)):
		# Number of fire hydrants that are needed.
		needed = 0
		# The house that we need to connect a fire hydrant to.
		start = houses[i]