Доброго вечера всем участниками и наблюдателям сегодняшнего Яндекс.Алгоритма.
Огромное спасибо Мише Левину и Мише Мирзаянову за возможность принять участие в составлении контеста. Также отдельное спасибо Артему Рахову и Станиславу Паку за помощь в составлении задачи.
Итак, сегодня я был автором задачи B. Задача оказалась несложной, и многие участники с ней справились. Для тех, кому задача не поддалась, я сейчас расскажу её решение.
Огромное спасибо Мише Левину и Мише Мирзаянову за возможность принять участие в составлении контеста. Также отдельное спасибо Артему Рахову и Станиславу Паку за помощь в составлении задачи.
Итак, сегодня я был автором задачи B. Задача оказалась несложной, и многие участники с ней справились. Для тех, кому задача не поддалась, я сейчас расскажу её решение.
Сначала повторю определение хорошего множестве, данное в задаче. Множество точек на плоскости с целыми координатами называется хорошим, если для любых двух точек множества верно одно из следующих утверждений:
- точки лежат на одной горизонтали или вертикали;
- в прямоугольнике с углами в данных точках есть еще точки из множества помимо двух данных. Прямоугольник рассматривается вместе со своей границей.
В задаче требовалось найти хорошее надмножество заданного множества точек, не превосходящее по размеру 2· 105.
Задача решается с помощью классического алгоритма "разделяй и властвуй". Обозначим за X множество всех x-координат исходных точек. Проведем прямую с целой y-координатой. Множество точек разобьется на три части (некоторые из которых возможно пустые): лежащие на прямой, лежащие ниже прямой и лежащие выше прямой. Выберем прямую так, чтобы последние две части не превосходили по размеру половины исходного множества, и решим для них задачу реккурентно. Теперь ответ для исходной задачи строится как объединение ответов для двух подзадач и множество всех точек на прямой с координатами из множества X.
Задача решается с помощью классического алгоритма "разделяй и властвуй". Обозначим за X множество всех x-координат исходных точек. Проведем прямую с целой y-координатой. Множество точек разобьется на три части (некоторые из которых возможно пустые): лежащие на прямой, лежащие ниже прямой и лежащие выше прямой. Выберем прямую так, чтобы последние две части не превосходили по размеру половины исходного множества, и решим для них задачу реккурентно. Теперь ответ для исходной задачи строится как объединение ответов для двух подзадач и множество всех точек на прямой с координатами из множества X.
Покажем, что описанный выше алгоритм корректен. Во-первых он выдает множество точек, размер которого не превосходит 
, что строго меньше чем 200000 при условии, что n не превосходит 10000.
Теперь докажем, что множество точек, построенное алгоритмом, является хорошим. Сделаем это по индукции. Пусть мы решили задачу для множества точек под проведенной прямой и над проведенной прямой, и полученные там множества точек являются хорошими. Тогда объединение этих множеств друг с другом и с точками на прямой тоже будет хорошим. Действительно, рассмотрим две произвольные точки полученного множества, не лежащие на одной горизонтали или вертикали. Если обе эти точки лежат по одну сторону от прямой, то для них выполнено условие "хорошести" по предположению индукции. Если же одна из точек лежит на проведенной прямой или обе точки лежат по разные стороны от прямой, то прямоугольник с углами в этих точках обязательно содержит точки из проведенной прямой помимо двух рассматриваемых. Это следует из того, что мы в надмножество добавили все точки на прямой с x-координатами из нашего множества. Таким образом, корректность алгоритма доказана.
, что строго меньше чем 200000 при условии, что n не превосходит 10000. Теперь докажем, что множество точек, построенное алгоритмом, является хорошим. Сделаем это по индукции. Пусть мы решили задачу для множества точек под проведенной прямой и над проведенной прямой, и полученные там множества точек являются хорошими. Тогда объединение этих множеств друг с другом и с точками на прямой тоже будет хорошим. Действительно, рассмотрим две произвольные точки полученного множества, не лежащие на одной горизонтали или вертикали. Если обе эти точки лежат по одну сторону от прямой, то для них выполнено условие "хорошести" по предположению индукции. Если же одна из точек лежит на проведенной прямой или обе точки лежат по разные стороны от прямой, то прямоугольник с углами в этих точках обязательно содержит точки из проведенной прямой помимо двух рассматриваемых. Это следует из того, что мы в надмножество добавили все точки на прямой с x-координатами из нашего множества. Таким образом, корректность алгоритма доказана.
Время работы данного решения составляет 
. По причинам очень большого количества выходных точек для задачи были выбраны очень мягкие ограничения. В частности, в данной задаче проходило решение с квадратичной ассимптотикой времени работы.
Идея задачи была навеяна замечательной статьей. В ней вы можете узнать связь между деревьями поиска и хорошими множествами точек. Там же можно прочитать про жадные решения данной задачи. Интересный факт, что задача поиска минимального по размеру хорошего надмножества ялвяется NP-трудной.
. По причинам очень большого количества выходных точек для задачи были выбраны очень мягкие ограничения. В частности, в данной задаче проходило решение с квадратичной ассимптотикой времени работы. Идея задачи была навеяна замечательной статьей. В ней вы можете узнать связь между деревьями поиска и хорошими множествами точек. Там же можно прочитать про жадные решения данной задачи. Интересный факт, что задача поиска минимального по размеру хорошего надмножества ялвяется NP-трудной.
Comments (3)
+20
