Lunch in Grid City, or UVA 855, is a problem created for the Portuguese regional of the ACM-ICPC. The premise of the problem is that you are given a set of coordinates in a grid, and have to find a coordinate that minimizes the sum of the Manhattan distances between all points in and . Formally:
A naive approach would be to compute the distances of all points in to all possible points in the grid, and pick up the point with smaller score. This has complexity , where s and a are the height and width of the grid, respectively. Since , this approach would obviously not work.
Simplifying the definition
The summation that defines the score for a candidate can be broken down into two separate summations. This simplifies the problem and helps us to better analyse it:
What this equation tells us is that we can solve the problem by separately optimizing each axis, since they are independent. Let’s focus on the x axis for the sake of clarity:
Each component of p belongs to S
The problem specification gives a valuable hint: it gives the impression that . Although this is not entirely true, we can prove that and .
Suppose that there is a potential solution such that . The score on this particular dimension is given by:
Let be the amount of points to the left of , and the amount to its right. If we take the solution to be the closest point on its left, the new score would be:
where is the difference between the x coordinate from the closest point to the left and . Here we can notice that, if , then , which means the point to the left would be preferred over our hypothetical solution. Moreover, if , then picking up a point to the right would give us the new (and better) score
where is the difference computed by using the closest point to the right.
From this analysis, we conclude that our search space for is reduced to the x coordinates of all points . The same argument can be made for (where its search space is the y component of all points in ).
The solution as a median
Let be the value that minimizes the distances on the x axis. Its score is computed as given by (I). If we were to pick up the left neighbor of , the new score would be:
Since (otherwise, wouldn’t be a solution), we can say that:
This tells us that the amount of points by the left of should not be larger than the amount of points by its right. Another relation between $k$ and $l$ can be found by analyzing the score obtained by picking up the point to the right of :
In this case, . By exploring this relation:
By combining (II) and (III), we have that . If the total amount of points is odd, then , otherwise would be greater than 1. In the other hand, if is even, then can’t be equal to . Therefore, .
In general terms, if you have a sorted collection of x coordinates in X, the coordinate that gives the best score α is given by
considering an indexation that starts at 0. This is essentially the median of the collection X. Once again, the same argument also applies to the y coordinates.
We conclude that, in order to solve the Lunch in Grid City problem, we have to:
- Create two different vectors, one with all x coordinates and another with all y coordinates of the given points in (referred to as the list of friends in the problem description);
- Sort each vector;
- Return .
This solution has complexity , where the bottleneck is the sorting algorithm.