Manhattan Pairing (Editorial)

10pt

Block 1

There are only two points that must be paired: the answer will be the Manhattan distance between these points: d = |x_1 - x_2| + |y_1 - y_2|

Block 2

First, pair together points with the same y-coordinates (identical points) since their Manhattan distance will be 0. If there are two different points left, they will have to be paired, and their Manhattan distance will be 1.

Block 3

Since $n$ is no more than 4, we can enumerate all possible ways to split the points into pairs. This can be imagined as a set of permutations where every two adjacent points form a pair. For each such permutation, the maximum Manhattan distance among the pairs is determined, and among all variants, the one with the smallest maximum distance is chosen.

Block 4

Dynamic programming on masks can be used. In this case, the state is determined by the subset of points that have been paired, and the smallest possible value of the maximum Manhattan distance among all possible pairing methods for these points is stored. At each step, we select two unused points, calculate the distance between them, and add them to the pairing, updating the $dp$ value.

Block 5

If all points have y = 0, meaning they all lie on a horizontal line. In this case, simply sort the points by $x$ and pair adjacent points. The maximum distance among all pairs will be determined by the largest difference between adjacent $x$ values.

Block 6

The Manhattan distance between any two points is defined as |x_1 - x_2| + |y_1 - y_2|. Since all $x$ values are different, the largest contribution to the distance is the difference in $x$ coordinates, while the $y$ coordinates can change the distance by only 0 or 1 (as $y$ can only be 0 or 1).

Therefore, the task can be simplified by just sorting the points by $x$ coordinates and pairing neighboring points in the list. This works optimally because sorting ensures that nearby points in terms of $x$ coordinates will be neighbors.

Block 7 - 8

Let's temporarily ignore the y-coordinates and calculate the result as if all the points lie on one line (i.e., all y = 0).

Let's denote the obtained value as $ans$, which is the minimum possible value of the maximum Manhattan distance between paired points in this simplified case. Obviously, the final answer will be either $ans$ or ans + 1 since the difference in y-coordinates can only affect the distance by 1.

Now we need to check if it is possible to achieve exactly $ans$.

For this, we will go through the prefix of points sorted by $x$ coordinate where x_i \le pref. During the process, there are three possible situations:

• All points in this prefix are already paired.

• One point with y = 0 remains.

• One point with y = 1 remains.

Since the remaining point is the rightmost among the processed ones, we know its $x$ coordinate exactly. To track this effectively, we can use a dynamic array dp[pref][0/1/2], where:

• dp[pref][0] means all points up to $pref$ are already paired.

• dp[pref][1] means one point with y = 0 remains.

• dp[pref][2] means one point with y = 1 remains.

Let cnt_0 be the number of points with the coordinates (pref, 0), and cnt_1 the number with (pref, 1).

Consider transitions from the state dp[prev\_pref][0]:

• if cnt_0 \mod 2 = cnt_1 \mod 2:

  • if cnt_0 \mod 2 = 0, then to the state dp[pref][0]

  • if cnt_0 \mod 2 = 1, then to the state dp[pref][0], but only if ans \ge 1.

• if cnt_0 \mod 2 \neq cnt_1 \mod 2:

  • if there is no point with the coordinates (pref, 0), i.e., cnt_0 = 0, then to the state dp[pref][2]

  • if there is no point with the coordinates (pref, 1), i.e., cnt_1 = 0, then to the state dp[pref][1]

  • otherwise, it is possible to transition to both the state dp[pref][1] and the state dp[pref][2].

The transitions from the states dp[prev\_pref][1] and dp[prev\_pref][2] are similar, but both cases need to be considered as to which of the points (pref, 0) and (pref, 1) the unpaired point from the prev\_pref prefix connects to (but only connections where the Manhattan distance will be no more than $ans$ are allowed), and work with updated values of cnt_0 and cnt_1 (with values that account for the new connection and reduce one of the counts by 1 respectively).

After processing all points, that is, when we reach the largest value pref_{max}, if dp[pref_{max}][0] is equal to 1, then the value of $ans$ is achievable; otherwise, the answer is ans + 1. The time complexity is \mathcal{O}(n \cdot \log(n)).