Minimize max distance of Gas Station

Question

I'm working on this problem, and any advice on performance improvement, bugs or code style issues are appreciated.

Problem

Description

There are N gas stations on a straight, M kilo-meters long highway. The i-th gas station is Ai kilometers away from the beginning of the highway. (It is guaranteed that there is one gas station at each end of the highway.)

Now the mayor can build K more gas stations. He wants to minimize the maximum distance between two adjacent gas station. Can you help him?

Input:

The first line contains 3 integer N, M, k. (2 <= N <= 1000, 1 <= M, K <= 100000)

The second line contains N integer, A1, A2, ... AN. (0 = A1 <= A2 <= ... <= AN = M)

Output:

The minimized maximum distance rounded to one decimal place.

Sample Input

3 10 2  
0 2 10

Sample Output

2.7

My major ideas are:

1. Calculate lower and upper bound of gas station distance (lower bound 1, higher bound is current max distance between two existing gas stations)
2. Do a binary search for lower bound and higher bound, to see if we can fit with k gas stations
   1. If we can fit, then try to lower higher bound of binary search
   2. If we cannot fit, then try to higher lower bound of binary search
3. At the end, the number is minimal of max distance between gas stations
4. Since it requires one decimal place, I +/- 0.1 other than +/- 1

---

def max_gas_distance(distances, k):
    max_distance = 0
    for i, v in enumerate(distances):
        if i > 0:
            max_distance = max(max_distance, v - distances[i-1])
    # final result between 1 and max_distance
    l = 1.0
    h = max_distance
    while l <= h:
        mid = l + (h-l)/2.0
        if valid(distances, mid, k):
            h = mid - 0.1
        else:
            l = mid + 0.1
    return l
def valid(distances, mid, k):
    additional_gas_station = 0
    for i,v in enumerate(distances):
        if i > 0 and v - distances[i-1] > mid:
            additional_gas_station += (v - distances[i-1]) / mid
            if additional_gas_station >= k+1:
                return False
    return True

if __name__ == "__main__":
    existing_gas_stations = [0,2,10]
    k = 2.0
    print max_gas_distance(existing_gas_stations, k)

Answer 1

Bugs/Correctness

1. In the binary search, when a good value (that is when valid returns true) is found, your code doesn't save it before trying to optimize it further.

   if valid(distances, mid, k):
       h = mid - 0.1 # Now the best value is lost.
   

   The best way is to save the best distance you found so far.

   if valid(distances, mid, k):
       best_so_far = mid
       h = mid - 0.1
   ...
   return best_so_far
   

2. (v - distances[i-1]) / mid, now if the distance between the stations is 6 and mid is 3, the result will be 2, while you really only need to add 1 gas station. What you really wanna do is to get the ceiling of distance / mid which will give you the number of pieces of length mid, then subtract one to get the number of gas stations in the middle. So math.ceil(distance / mid) - 1.

Code Style

Overall I think the code is really clean, with clear variable names and good modularity.

1. The part that gets the max distance between every 2 elements

   max_distance = 0
   for i, v in enumerate(distances):
     if i > 0:
       max_distance = max(max_distance, v - distances[i-1])
   

   Could be written in a more pythonic way as:

   max_distance = max(a + b for a, b in zip(distances, distances[1:]))
   

2. The method name valid is not really readable, also the variable names mid and k are not expressive. So I would rename it to something like.

   is_solvable(distances, distance_required, additional_stations)