Задача 8. Разбиение на пары ≡

Условие

Космические археологи обнаружили на планете в соседней звездной системе n древних артефактов, которые они пронумеровали от 1 до n. Каждый артефакт имеет k различных параметров, каждый параметр характеризуется целым числом. Артефакт i имеет параметры a_i,1, a_i,2, …, a_i,k. Оказалось, что первые параметры у всех артефактов различны: для всех i ≠ j выполнено a_i,1 ≠ a_j,1, при этом другие параметры у артефактов могут совпадать.

Учёные также обнаружили текст, в соответствии с которым для активации артефактов их необходимо особым образом разбить на пары и совместить. Разбиение артефактов на пары является корректным, если для каждого t от 1 до k можно выбрать такое число b_t, что оно лежит на отрезке между значениями t-го параметра артефактов каждой пары. То есть, если артефакты i и j образуют пару, должно выполняться условие a_i,t ≤ b_t ≤ a_j,t или условие a_i,t ≥ b_t ≥ a_j,t.

Теперь ученые хотят выяснить, верно ли расшифрован текст. Для этого необходимо проверить, существует ли корректное разбиение артефактов на пары. Каждый артефакт должен войти ровно в одну пару в разбиении.

Требуется написать программу, которая по описанию параметров артефактов определяет, можно ли разбить их на пары таким образом, чтобы для каждого параметра существовало значение, лежащее между значениями этого параметра артефактов каждой пары, и в случае положительного ответа выводит такое разбиение.

Формат входных данных

В первой строке заданы целые числа n и k — количество артефактов и количество параметров.

В следующих n строках задано по k целых чисел a_i,1, a_i,2, …, a_i,k — параметры артефактов.

Формат выходных данных

Выведите NO, если требуемого разбиения на пары не существует.

В противном случае выведите YES в первой строке. Далее выведите n / 2 строк, в каждой строке выведите по два числа — номера артефактов, из которых следует составить пару. Каждый артефакт должен быть выведен ровно один раз.

Если существует несколько корректных разбиений артефактов на пары, разрешается вывести любое из них.

Ограничения

2 ≤ n ≤ 2 ⋅ 10⁵, n чётно, 1 ≤ k ≤ 7

 − 10⁹ ≤ a_i,j ≤ 10⁹, все значения a_i,1 различны

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Пояснения к примерам

В первом примере пары имеют следующие параметры (8,6) − (3,1), (1,5) − (7,2), (6, 3) − (4,7). При указанном разбиении на пары подойдут, например, значения b₁ = 4, b₂ = 4,

Примеры тестов

6 2
8 6
1 5
6 3
3 1
4 7
7 2

YES
1 4
2 6
3 5

4 3
1 -1 -1
2 1 1
3 -1 1
4 1 -1

NO

Разбор

Рассмотрим искомое разбиение на пары. Для каждого j есть n / 2 индексов i, таких что a_i,j ≤ b_j и n / 2 индексов i, таких что a_i,j ≥ b_j.

Таким образом, если решение существует, то в качестве b_j можно выбрать median(a_1,j,…,a_n,j), где median  — медиана набора чисел, в наборе чётное количество чисел, поэтому медиана — это среднее арифметическое n / 2-й и n / 2 + 1-й порядковых статистик значений соответствующего параметра, хотя можно выбрать и просто n / 2-ю порядковую статистику.

Для решения подзадачи 1 можно перебрать все разбиения на пары и для каждого проверить корректность.

В подзадаче 2 параметр всего один, поэтому артефакты можно разбить на пары жадно: первый и последний, второй и предпоследний, и так далее. Решение всегда существует.

В подзадаче 3 все значения каждого параметра различны. Для каждого артефакта построим битовый вектор длины k, j-я координата равна 0 или 1, в зависимости от того, больше или меньше значение j-го параметра, чем соответствующее медианное значение. Заметим, что артефакты надо разбить на пары, которым соответствуют битовые вектора, являющиеся отрицанием друг друга. Это можно попытаться сделать жадным алгоритмом, если решение не найдено, то его не существует.

Трудность решения оставшихся подзадач заключается в том, что все параметры, кроме первого, могут принимать равные значения. Каждый артефакт, значение параметра которого равно соответствующей медиане, может быть как меньшим, так и большим по этому параметру в паре.

В подзадаче 4 параметров два. Разделим артефакты по первому параметру на два множества, условно назовём их красным и синим: первые n / 2 по первой координате и вторые n / 2 по первой координате. В каждую пару должен войти один красный и один синий артефакт. Сопоставим каждому артефакту значение 0, 1 или  − 1, в зависимости от того, равно, больше или меньше значение его второго параметра медианному. Получаем 6 множеств: красные R₀, R₁, R_− 1 и, соответственно, синие B₀, B₁, B_− 1. Артефакты из R₁ должны войти в пары с B_− 1, из R_− 1  — в пары с B₁. Артефакты из R₀ могут войти в пары с любыми синими, а из B₀ с любыми красными. Их можно распределить жадно.

Альтернативное решение: отсортируем артефакты по второму параметру (при равенстве произвольным образом), и первые n / 2 назовём малыми, а последние n / 2 большими. Тогда красные большие входят в пары с синими малыми, а красные малые с синими большими. Легко показать, что их количество соответственно совпадает.

В подзадачах 5 и 6 параметров больше и жадный алгоритм перестаёт работать. Рассмотрим решение на основе алгоритмов поиска паросочетаний в двудольных графах и потоков.

Решение подзадачи 5. Для каждой пары артефактов проверим, можно ли создать из них пару.Проведём ребро между в случае, если можно. Как и прежде разделим артефакты на красные и синие, в зависимости от первого параметра. Заметим, что ребра соединяют артефакты разного цвета, следовательно граф двудольный. Найдём в получившемся графе полное паросочетание алгоритмом Куна. В графе O(n²) рёбер, поэтому решение работает за O(n³).

Решение подзадачи 6. Сопоставим каждому артефакту строку длины k из 0, 1 и  − 1: j-е число равно  − 1, если a_i,j < b_j, 1, если a_i,j > b_j и 0, если a_i,j = b_j. Заметим, что первое число в строке не может быть равно 0. Таким образом, точки разбиваются на 2 ⋅ 3^k − 1 групп. Заведём вершину для каждой группы. Вершины, которые соответствуют точкам, у которых a_i,1 < b₁ — это первая доля, остальные — вторая. Также заведём исток и сток. В вершины первой доли проведём рёбра из истока с весом, равным числу точек в соответствующей группе. Из вершин второй доли в сток — аналогично. Между вершинами из разных долей проведём рёбра веса  + ∞, если соответствующие им точки можно объединить в пары. Найдём в таком графе максимальный поток. Чтобы восстановить ответ, нужно найти декомпозицию этого потока.