В задаче нужно было разделить множество точек (мощностью n) на плоскости на два множества так, что бы в каждом множестве расстояние между парой самых удаленных точек было d, которое нужно минимизировать. А затем, уже при найденном минимальном d, посчитать количество способов разбиения с сохранением вышеописанного инварианта.
Для начала научимся решать задачу за более медленную асимптотику. Зафиксируем бинарным поиском искомое расстояние d и рассмотрим граф из n вершин (вершины соответствуют точкам), в котором есть ребро между вершинами i и j, если |xi - xj| + |yi - yj| > d. Тогда понятно, что если полученный граф будет двудольным, то исходное множество можно разбить на две части так, что расстояние между парой самых удаленных точек в каждой части будет не больше d. Пусть мы определили минимальное значение d, при котором вышеописанный граф будет оставаться двудольным, тогда подсчет количества разбиений сводится, как несложно видеть, к подсчету количества раскрасок двудольного графа в два цвета. Время работы данного решения составляет O(n2log(n)).
Попробуем ускорить данный алгоритм следующим образом. Предположим, что мы отсортировали все попарные расстояния между точками в порядке уменьшения. Данную операцию можно сделать за линейное время от количества пар, т.е. за время O(n2), используя сортировку подсчетом. Теперь для каждой пары точек (i, j) (в отсортированном порядке) будем добавлять ребро в граф между вершинами i и j, до тех пор пока он будет оставаться двудольным. Расстояние между парой точек, на которой мы остановились и будет оптимальным значением d. Остался лишь одни неясный момент, как быстро (за O(1)) проверять остается ли граф двудольным после добавления очередного ребра? Это можно делать используя CНМ. Как известно в двудольном графе нет циклов нечетной длины, а поэтому, нам достаточно модифицировать СНМ так, что бы она не учитывала циклы четной длины, а реагировала лишь на нечетные. Для этого для каждой вершины заведем пометку, которая будет указывать на четность длины пути от вершины до корня ее дерева, которую несложно пересчитывать после изменения СНМ. Реализовав такую структуру данных, мы получим быстрый способ ответа на интересующий нас вопрос. Итого, сложность вышеописанного решения O(n2).
На самом деле, при использовании манхетенской метрики, данную задачу можно решать за линейное время, т.е. O(n). Преобразуем систему координат следующим образом:
x’ = x - y
y’ = x + y
Тогда задачу можно свести к покрытию всех точек двумя квадратами одинакового размера (возможно пересекающимися) со сторонами параллельными осям новой системы координат. Ответом на задачу будет наименьшая длина стороны квадратов, которыми можно покрыть все точки, а количество способов разбиения равно 2k + 1, где k - число точек, которые принадлежат сразу двум квадратам.
На самом деле, при использовании манхетенской метрики, данную задачу можно решать за линейное время, т.е. O(n). Преобразуем систему координат следующим образом:
x’ = x - y
y’ = x + y
Тогда задачу можно свести к покрытию всех точек двумя квадратами одинакового размера (возможно пересекающимися) со сторонами параллельными осям новой системы координат. Ответом на задачу будет наименьшая длина стороны квадратов, которыми можно покрыть все точки, а количество способов разбиения равно 2k + 1, где k - число точек, которые принадлежат сразу двум квадратам.
Отличную реализацию данного алгоритма можно увидеть в решении участника Sammarize во время раунда.
Comments (0)
