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?