# Placing K gas stations among n cities to minimize distance

There are $$n$$ cities on a highway with coordinates $$x_1$$ , . . . , $$x_n$$ and we aim to build $$K < n$$ gas stations to cover these cities. Each gas station has to be built in one of the cities, and we hope to minimize the average distance from each city to the closest gas station. Please give an algorithm to compute the optimal way to place these $$K$$ gas stations. The algorithm should run in $$O(n^2K)$$ time.

I brute forced the answer by finding every single possible placement of gas stations and returning the minimum combo. Then I spent way too long fiddling with different ideas in Python to try and reduce the big-$$O$$ notation to no avail. Eventually I found a thread on the subject, but the formula isn't working for me.

How to minimize the average distance between pumps and cities?

I tried replicating the formula given in this thread in Python and it just doesn't work. It comes close but no dice. Here's my code (assume "cities" is the list of cities):

def f(n, k):
if k == 1: # if k is 1, return total distance from the cities to the median
pump = n // 2
return sum([abs(loc - cities[pump]) for loc in cities[:n]])

min_list = []
for i in range(n-1):
sum_list = []
for j in range(i+1, n):
pumpk = ((j + 1) + (n-1)) // 2
sum_list.append(abs(cities[j] - cities[pumpk]) + f(i, k-1))
min_list.append(sum(sum_list))
return min(min_list)


I'm at such a loss! How can I solve the problem with the required time-complexity?

• Where did you encounter this problem statement? We require you to credit the original source of all quoted material or material originally written by others: cs.stackexchange.com/help/referencing. Can I ask you to edit your question to comply with that policy? Thank you.
– D.W.
Mar 23 at 1:56

It looks that the recurrence relation is not implemented correctly in the code given in the question.

Here is a correct implementation.

# cities is a list of increasing integers that gives the
# locations of all cities such as follows
cities = [1, 5, 20, 22, 40, 100, 110]
K = 2

def min_sum_distances(start, end):
""" Cities between start inclusive and end exclusive. One pump is installed."""
pump_loc = start + end >> 1
return sum(abs(city - cities[pump_loc]) for city in cities[start:end])

def min_sum(total_pumps):
n = len(cities)

# dp[c][p] is the minimum sum of distances from the first c cities
# to the nearest pump when p pumps are installed.
# 1 <= c <= n and 1 <= p <= K
dp = [[float("infinity")] * (K + 1) for number_of_pumps in range(n + 1)]
for c in range(1, n + 1):
dp[c] = min_sum_distances(0, c)
for p in range(2, min(c + 1, total_pumps + 1)):
for cities_covered_before in range(p - 1, c):
dp[c][p] = min(dp[c][p], dp[cities_covered_before][p - 1]
+ min_sum_distances(cities_covered_before, n))
return dp[n][total_pumps]

print(min_sum(K) / len(cities))
# 9.42857142857


The implementation runs in $$O(n^3K)$$ time.

In order to spend up the performance, we can reimplement min_sum_distance so that it runs in $$O(1)$$ instead of $$O(n)$$. We can use precomputed prefix sums of cities.

from itertools import accumulate
pre_sums = list(accumulate(cities, initial=0))

def min_sum_distances(start, end):
pump_loc = start + end >> 1
return pre_sums[start] + pre_sums[end] - 2 * pre_sums[pump_loc] \
- (cities[pump_loc] if (end - start) & 1 else 0)


With the improvement, the implementation runs in $$O(n^2K)$$ time.

• Could you explain what this algorithm does and why? Mar 24 at 19:21