Манхетенське парування (Розбір)

10pt

Блок 1

Є лише дві точки, які обов'язково потрібно об'єднати в пару. Відповіддю буде манхеттенська відстань між цими точками: d = |x_1 - x_2| + |y_1 - y_2|

Блок 2

Спочатку поєднати попарно точки, які мають однакові y-координати (однакові точки), оскільки їх манхеттенська відстань буде рівною 0. Якщо залишаться дві різні точки, їх доведеться об'єднати, і їхня манхеттенська відстань буде 1.

Блок 3

Оскільки $n$ не більше 4, то можна перебрати всі можливі варіанти розбиття точок на пари. Це можна уявити як множину перестановок, у яких кожні дві сусідні точки утворюють пару. Для кожної такої перестановки визначається максимальна манхеттенська відстань серед пар, і серед усіх варіантів вибирається той, у якому ця величина є найменшою.

Блок 4

Можна використати динамічне програмування по масках. Стан у цьому випадку визначається підмножиною точок, які вже поєднані у пари, і зберігається найменше можливе значення максимальної манхеттенська відстані серед усіх можливих способів парування цих точок. На кожному кроці вибираємо дві ще не використані точки, обчислює відстань між ними і додає їх у розбиття, оновлюючи значення $dp$.

Блок 5

Якщо всі точки мають y = 0, тобто вони всі лежать на горизонтальній прямій. У такому випадку достатньо впорядкувати точки за x і попарно поєднати сусідні. Максимальна відстань серед усіх пар буде визначатися найбільшою різницею між сусідніми значеннями $x$.

Блок 6

Манхеттенська відстань між будь-якими двома точками визначається як |x_1 - x_2| + |y_1 - y_2|. Оскільки всі значення x різні, найбільший внесок у відстань дає саме різниця між x-координатами, а y-координати можуть змінювати відстань лише на 0 або 1 (оскільки y може бути тільки 0 або 1).

Тоді можна спростити задачу, просто відсортувавши точки за x-координатою та поєднавши сусідні точки у списку. Це працює оптимально, тому що сортування гарантує, що точки, які знаходяться найближче одна до одної за x-координатою, будуть сусідами.

Блок 7 - 8

Давайте тимчасово проігноруємо y-координати та розрахуємо відповідь, наче всі точки лежать на одній прямій (тобто, всі y = 0).

Нехай отримане значення ми позначимо як $ans$, яке є мінімальним можливим значенням максимальної манхеттенська відстані між парними точками у цьому спрощеному випадку. Очевидно, що остаточна відповідь буде або $ans$, або ans + 1, оскільки різниця y-координатах може вплинути лише на 1.

Тепер нам потрібно перевірити, чи можливо досягти саме $ans$.

Для цього будемо проходити по префіксу точок, посортованих за $х$-координатою, для яких x_i \le pref. У процесі є три можливі ситуації:

• Всі точки з цього префіксу вже об'єднані у пари.

• Залишилася одна точка з y = 0.

• Залишилася одна точка з y = 1.

Оскільки точка, що залишилася, є крайньою правою серед оброблених, ми точно знаємо її $x$-координату. Для ефективного відстеження можна використовувати динамічний масив dp[pref][0/1/2], де:

• dp[pref][0] означає, що всі точки до pref вже об'єднані у пари.

• dp[pref][1] означає, що залишилася одна точка з y = 0.

• dp[pref][2] означає, що залишилася одна точка з y = 1.

Нехай cnt_0 це кількість точок з координатою (pref, 0), та cnt_1 з координатою (pref, 1).

Розглянемо переходи зі стану dp[prev\_pref][0]:

• якщо cnt_0 \mod 2 = cnt_1 \mod 2:

  • якщо cnt_0 \mod 2 = 0, то в стан dp[pref][0]

  • якщо cnt_0 \mod 2 = 1 в стан dp[pref][0], але тільки якщо ans \ge 1.

• якщо cnt_0 \mod 2 \neq cnt_1 \mod 2:

  • якщо не існує жодної точки з координатою (pref, 0), тобто cnt_0 = 0, то в стан dp[pref][2]

  • якщо не існує жодної точки з координатою (pref, 1), тобто cnt_1 = 0, то в стан dp[pref][1]

  • інакше можна перейти як в стан dp[pref][1] так і в стан dp[pref][2].

Переходи зі станів dp[prev\_pref][1] та dp[prev\_pref][2] є аналогічними, але потрібно ще розглянути обидва випадки, до якої з точок (pref, 0) та (pref, 1) з'єднується нез'єднана точка з префіксу prev\_pref (але дозволені тільки з'єднання для яких манхеттенська відстань буде не більшою за $ans$), та працювати вже з оновленими значеннями cnt_0 та cnt_1 (зі значеннями які враховують нове з'єднання, і відповідно зменшення однієї з кількостей на $1$).

Після обробки всіх точок, тобто коли ми дійшли до найбільшого значення pref_{max}, якщо dp[pref_{max}][0] рівне $1$, то значення $ans$ є досяжним, інакше відповіддю є ans + 1. Часова складність \mathcal{O}(n \cdot log(n)),