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:

(I)

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:

(II)

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:

(III)

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.

## Final thoughts

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.