Manhattan Pairing#395

Manhattan Pairing (Editorial)

Problem Author:

Anton Trygub

Prepared by:

Anastasia Tovtyn

Analysis written by:

Anastasia Tovtyn

10pt

Block 1

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

Block 2

First, points with the same -coordinates (identical points) must be paired together, as their Manhattan distance will be . If two different points remain, they must be paired, and their Manhattan distance will be .

Block 3

Since is at most , all possible pairings of points can be enumerated. 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 options, the one with the smallest value is selected.

Block 4

Dynamic programming with masks can be used. The state in this case is defined by the subset of points that have already been paired, and it stores the smallest possible value of the maximum Manhattan distance among all possible ways of pairing these points. At each step, two unused points are chosen, the distance between them is calculated, and they are added to the partition, updating the value of .

Block 5

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

Block 6

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

Thus, the problem can be simplified by simply sorting the points by their -coordinates and pairing adjacent points in the list. This works optimally because sorting guarantees that the points that are closest to each other in terms of -coordinates will be neighbors.

Block 7 - 8

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

Let the obtained value be denoted as , which is the minimum possible value of the maximum Manhattan distance between paired points in this simplified case. It is clear that the final answer will be either or ans + 1, since the difference in -coordinates can only affect it by .

Now we need to check whether it is possible to achieve exactly .

To do this, we will go through the prefix of points sorted by their -coordinates, for which x_i \le pref. 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 definitely know its -coordinate. For efficient tracking, we can use a dynamic array dp[pref][0/1/2], where:

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

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

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

Let cnt_0 be the number of points with coordinates (pref, 0), and cnt_1 with coordinates (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 state dp[pref][0]

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

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

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

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

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

Transitions from states dp[prev\_pref][1] and dp[prev\_pref][2] are similar, but both cases must be considered regarding which of the points (pref, 0) and (pref, 1) is paired with the unpaired point from the prefix prev\_pref (but only connections for which the Manhattan distance will not exceed are allowed), and work with the updated values of cnt_0 and cnt_1 (with values that account for the new connection, and accordingly decrease one of the counts by ).

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