2
\$\begingroup\$

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)
\$\endgroup\$
5
\$\begingroup\$

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)
    
\$\endgroup\$
  • \$\begingroup\$ Thanks for the comments Hesham, but I think my code will return the same value comparing to your best_so_far method, and my code just needs one more round of iteration of binary search. Is there an example to show my code returns the wrong result? \$\endgroup\$ – Lin Ma Feb 13 '17 at 4:48
  • \$\begingroup\$ BTW, do you think about any faster solutions comparing to using binary search? \$\endgroup\$ – Lin Ma Feb 13 '17 at 4:48
  • \$\begingroup\$ I think there is another bug where you set l to 1.0 in your binary search. However, I think there could be a distance less than 1.0, ex. stations = [0, 1], and k = 1, the minimum distance in that case is 0.5. when you fix this bug, you could try stations = [0, 10], and k = 1, and you will find your code returning 4.9 instead of 5. \$\endgroup\$ – Hesham Attia Feb 13 '17 at 10:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.