FireHose (S3) from CCC

Question

This grade 11 problem has been bothering me since 2010 and I still can't figure out/find a solution even after university.

Problem Description

There is a very unusual street in your neighbourhood. This street forms a perfect circle, and the circumference of the circle is 1,000,000. There are H (1 ≤ H ≤ 1000) houses on the street. The address of each house is the clockwise arc-length from the northern-most point of the circle. The address of the house at the northern-most point of the circle is 0. You also have special firehoses which follow the curve of the street. However, you wish to keep the length of the longest hose you require to a minimum. Your task is to place k (1 ≤ k ≤ 1000) fire hydrants on this street so that the maximum length of hose required to connect a house to a fire hydrant is as small as possible.

Input Specification

The first line of input will be an integer H, the number of houses. The next H lines each contain one integer, which is the address of that particular house, and each house address is at least 0 and less than 1,000,000. On the H + 2nd line is the number k, which is the number of fire hydrants that can be placed around the circle. Note that a fire hydrant can be placed at the same position as a house. You may assume that no two houses are at the same address. Note: at least 40% of the marks for this question have H ≤ 10.

Output Specification
On one line, output the length of hose required so that every house can connect to its nearest fire hydrant with that length of hose.

Sample Input
4
0
67000
68000
77000
2

Output for Sample Input
5000

Link to original question

I can't even come up with a brutal force algorithm since the placement might be float number. For example if the houses are located in 1 and 2, then the hydro should be placed at 1.5 and the distance would be 0.5

Answer 1

Here is quick outline of an answer.

First write a function that can figures out whether you can cover all of the houses with a given maximum length per hydrant. (The maximum hose will be half that length.) It just starts at a house, covers all of the houses it can, jumps to the next, and ditto, and sees whether you stretch. If you fail it tries starting at the next house instead until it has gone around the circle. This will be a O(n^2) function.

Second create a sorted list of the pairwise distances between houses. (You have to consider it going both ways around for a single hydrant, you can only worry about the shorter way if you have 2+ hydrants.) The length covered by a hydrant will be one of those. This takes O(n^2 log(n)).

Now do a binary search to find the shortest length that can cover all of the houses. This will require O(log(n)) calls to the O(n^2) function that you wrote in the first step.

The end result is a O(n^2 log(n)) algorithm.

And here is working code for all but the parsing logic.

#! /usr/bin/env python

def _find_hoses_needed (circle_length, hose_span, houses):
    # We assume that houses is sorted.
    answers = [] # We can always get away with one hydrant per house.
    for start in range(len(houses)):
        needed = 1
        last_begin = start
        current_house = start + 1 if start + 1 < len(houses) else 0
        while current_house != start:
            pos_begin = houses[last_begin]
            pos_end = houses[current_house]
            length = pos_end - pos_begin if pos_begin <= pos_end else circle_length + pos_begin - pos_end
            if hose_span < length:
                # We need a new hose.
                needed = needed + 1
                last_begin = current_house
            current_house = current_house + 1
            if len(houses) <= current_house:
                # We looped around the circle.
                current_house = 0
        answers.append(needed)
    return min(answers)

def find_min_hose_coverage (circle_length, hydrant_count, houses):
    houses = sorted(houses)

    # First we find all of the possible answers.
    is_length = set()
    for i in range(len(houses)):
        for j in range(i, len(houses)):
            is_length.add(houses[j] - houses[i])
            is_length.add(houses[i] - houses[j] + circle_length)
    possible_answers = sorted(is_length)

    # Now we do a binary search.
    lower = 0
    upper = len(possible_answers) - 1
    while lower < upper:
        mid = (lower + upper) / 2 # Note, we lose the fraction here.
        if hydrant_count < _find_hoses_needed(circle_length, possible_answers[mid], houses):
            # We need a strictly longer coverage to make it.
            lower = mid + 1
        else:
            # Longer is not needed
            upper = mid
    return possible_answers[lower]

print(find_min_hose_coverage(1000000, 2, [0, 67000, 68000, 77000])/2.0)