Ignat's blog

By Ignat, 13 years ago, In Russian
Доброго вечера всем участниками и наблюдателям сегодняшнего Яндекс.Алгоритма.

Огромное спасибо Мише Левину и Мише Мирзаянову за возможность принять участие в составлении контеста. Также отдельное спасибо Артему Рахову и Станиславу Паку за помощь в составлении задачи.

Итак, сегодня я был автором задачи B. Задача оказалась несложной, и многие участники с ней справились. Для тех, кому задача не поддалась, я сейчас расскажу её решение.


Сначала повторю определение хорошего множестве, данное в задаче. Множество точек на плоскости с целыми координатами называется хорошим, если для любых двух точек множества верно одно из следующих утверждений:
  1. точки лежат на одной горизонтали или вертикали;
  2. в прямоугольнике с углами в данных точках есть еще точки из множества помимо двух данных. Прямоугольник рассматривается вместе со своей границей.
В задаче требовалось найти хорошее надмножество заданного множества точек, не превосходящее по размеру 2· 105.

Задача решается с помощью классического алгоритма "разделяй и властвуй". Обозначим за X множество всех x-координат исходных точек. Проведем прямую с целой y-координатой. Множество точек разобьется на три части (некоторые из которых возможно пустые): лежащие на прямой, лежащие ниже прямой и лежащие выше прямой. Выберем прямую так, чтобы последние две части не превосходили по размеру половины исходного множества, и решим для них задачу реккурентно. Теперь ответ для исходной задачи строится как объединение ответов для двух подзадач и множество всех точек на прямой с координатами из множества X.

Покажем, что описанный выше алгоритм корректен. Во-первых он выдает множество точек, размер которого не превосходит , что строго меньше чем 200000 при условии, что n не превосходит 10000.

Теперь докажем, что множество точек, построенное алгоритмом, является хорошим. Сделаем это по индукции. Пусть мы решили задачу для множества точек под проведенной прямой и над проведенной прямой, и полученные там множества точек являются хорошими. Тогда объединение этих множеств друг с другом и с точками на прямой тоже будет хорошим. Действительно, рассмотрим две произвольные точки полученного множества, не лежащие на одной горизонтали или вертикали. Если обе эти точки лежат по одну сторону от прямой, то для них выполнено условие "хорошести" по предположению индукции. Если же одна из точек лежит на проведенной прямой или обе точки лежат по разные стороны от прямой, то прямоугольник с углами в этих точках обязательно содержит точки из проведенной прямой помимо двух рассматриваемых. Это следует из того, что мы в надмножество добавили все точки на прямой с x-координатами из нашего множества. Таким образом, корректность алгоритма доказана.

Время работы данного решения составляет . По причинам очень большого количества выходных точек для задачи были выбраны очень мягкие ограничения. В частности, в данной задаче проходило решение с квадратичной ассимптотикой времени работы.

Идея задачи была навеяна замечательной статьей. В ней вы можете узнать связь между деревьями поиска и хорошими множествами точек. Там же можно прочитать про жадные решения данной задачи. Интересный факт, что задача поиска минимального по размеру хорошего надмножества ялвяется NP-трудной.
  • Vote: I like it
  • +33
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it +20 Vote: I do not like it
Did you write the checker for this problem? How does it work?
  • 13 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I guess it's quite simple:
    1. Let's find the nearest points on both vertical rays from each point and on both horizontal rays and draw the rectangle on it (if there's no point on any of rays we define this point infinitely far on this ray)
    2. If there are no points strictly inside any of rectangles the solution is correct

    Am I right?
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      You are nearly right.

      Take all points P = (p1, ..., pn) in ascending order. For (p1, ..., pk - 1) support interval tree I that gets maximal x coordinate on interval. Than for pk = (x, y) find nearest points with same x coordintate in Equinoxe maneur. We have ya < y < yb. Check that I(y) ≥ I(y + 1, ya) and I(y) ≥ I(yb, y - 1). If all such conditions are satisfied than P is good.