frost_nova's blog

By frost_nova, 8 years ago, In Russian,

В задаче нужно было разделить множество точек (мощностью 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 - число точек, которые принадлежат сразу двум квадратам. 
Отличную реализацию данного алгоритма можно увидеть в решении участника Sammarize во время раунда.


Read more »

 
 
 
 
  • Vote: I like it
  • +30
  • Vote: I do not like it

By frost_nova, 8 years ago, translation, In English,

We are glad to welcome all contestants of a qualifying contest "Yandex.Algorithm 2011 - Round 1".

Today's round authors are Vitaly Goldshteyn, Ignat Kolesnichenko, Stanislav Pak and Denis Yarets. All we are employees or interns of Yandex. We really appreciate Artem Rakhov, Maria Belova and Mike Mirzayanov who helped us to prepare the contest. We hope that our tasks will be quite interesting and you will get much fun solving them.

As you may know top 200 contestants after this round will be able to continue fighting for spots in the final round.

Please pay attention that as well as during the previous qualifying round Codeforces functionality will be a little cut down for the time of the competition. Do not worry, all will return into place after the end of the round.

Round will be rated for the official participants, and for those who failed to qualify and participate out of competition (unofficial).

Good luck and high rating for everyone!

Tasks analysis: C

Read more »

 
 
 
 
  • Vote: I like it
  • +116
  • Vote: I do not like it

By frost_nova, 8 years ago, In Russian,
 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it