Input: towns and is a number.

Output: find the stations such that we minimize the farthest town to the closest station, for any given .

Intuitively, if we pick any , we should not travel any further to get to a center than any other .


Solution space: all the possible tuples

Objective function :

This says that for each town , we pick the closest station among and consider the distance between them. We want to minimize for all towns.

High-level question

We can ask “where to place the first station?” or (almost equivalently) “which towns should the first station serve?”

  • Question is good because we decompose our problem: after placing the first station, we recurse and consider the remaining stations
  • In addition, we consider the remaining set of towns that aren’t covered by a station yet
  • The first phrasing of the question is not that good because it implies an infinite number of answers (because it’s a real number)

The possible answers are , where signifies the last town that should cover. For each , the payment of towns is given by

This is because we want to minimize the distance from the furthest town to station . We have two towns on either end, so the median is the best.


The -function in this problem is given by

We don’t know how much the remaining towns will pay. If we choose to use the first station to cover up to town , then

Remember that the output only considers the maximum distance that any given town has to travel to its station, so we take the max of the first station, and however much the remaining towns have to pay for the remaining stations.

Generalization: “proof of correctness”

We can generalize for any station last town and number of stations :

where is the last town covered by station from to .

We have two base cases so that doesn’t infinitely recurse. Consider if we have no towns left. Then we would be recursing on town , which doesn’t exist, so for any .

Furthermore, if we run out of stations, then , in which case we’ve failed to cover all towns, and so this should not be considered. Then for any town .

Caching subproblems

We use a 2D array to store any previously calculated values for in .

Runtime analysis

There are towns and problems, so there are subproblems. For each subproblem, we need to recurse through towns to consider each as the last town for that particular station. When , this is towns, so total runtime is given by