Закончил на днях Яндекс.
Алгоритм 2017 — наш чемпионат по спортивному программированию.
В финальном туре 25 финалистам предстояло решить шесть задач за два с половиной часа.
Первое место вновь завоевал Геннадий Короткевич из Санкт-Петербурга ИТМО – это его четвертая победа после соревнований в 2013, 2014 и 2015 годах.
Второе и третье места заняли Никола Йокич из ETH Zurich и выпускник Токийского университета Макото Соэдзима, повторив свои В последние годы Результаты.
Вот как распределились денежные призы: победа – 300 тысяч рублей, второе место – 150 тысяч, третье – 90 тысяч.
Заявки на участие в «Алгоритме 2017» подали 4840 человек.
Более 60% из них — россияне.
Беларусь находится на втором месте по количеству заявок, за ней следуют Украина, Индия и Китай.
Всего на чемпионат зарегистрировались жители нескольких десятков стран, в том числе Сингапура, Камеруна, Венесуэлы и Перу.
Традиционно мы публикуем формулировки и анализ решений конечных задач.
Проблема А.
Проблема майнинга Автор проблемы : Глеб Евстропов (Яндекс, НИУ ВШ?).
| Имя входного файла: | Имя выходного файла: | Лимит времени: | Ограничение памяти: |
|---|---|---|---|
| стандартный ввод | стандартный вывод | 5 секунд (13 для Java) | 512 мегабайт |
Нашего героя всегда тянуло в горы, поэтому на призовые деньги, заработанные на различных соревнованиях, он купил себе небольшой горнолыжный курорт и начал готовить его к зимнему сезону.
Единственный доступный маршрут состоит из 
контрольно-пропускные пункты, пронумерованные от 
до
.
Контрольно-пропускной пункт 
находится на вершине 
, и никакие две точки не находятся на одинаковой высоте.
Поскольку подъемник на маршруте всего один, спуск всегда начинается с номера КПП.
и заканчивается на номере контрольно-пропускного пункта 
.
Некоторый 
пары контрольных точек соединяются участками маршрута, ведущими от более высокой контрольной точки к нижней.
Привлекательность участок маршрута, непосредственно соединяющий контрольную точку 
с КПП 
, равна разнице высот точек, т.е.
.
При этом привлекательность маршрута, последовательное посещение пунктов пропуска 
, называется минимум привлекательности своих сайтов, то есть минимальное среди значений 
.
Туристов, посещающих курорт Аркадия, волнует, с одной стороны, привлекательность маршрута, а с другой - его длина, которая определяется количеством участков пути в маршруте.
Так как Аркадий уже не умеет решать задачи такого рода, то придется рассчитывать для каждой возможной длины маршрута 
от
до 
максимально возможная привлекательность маршрута от
В
, имеющий длину Не меньше
.
Формат ввода
Первая строка входных данных содержит четыре целых числа,
,
И
(
,
,
,
) — количество КПП на маршруте, количество участков маршрута, номер стартового КПП и номер финишного КПП соответственно.
Вторая строка содержит
разные целые числа 
( 
) - высоты, на которых расположены контрольные точки.
С последующим
строки, описывающие участки маршрута.
В
-th из них записаны два числа 
И 
( 
, 
), означающий, что
- участок маршрута начинается от КПП
до контрольно-пропускного пункта
.
Гарантируется, что никакие два участка маршрута напрямую не соединяют одну и ту же пару контрольных точек, причем высота контрольной точки
больше высоты контрольной точки
, и что существует хотя бы один маршрут от контрольной точки
на КПП
.
Выходной формат
Выходцифры по одному в строке,
-е из которых должно быть равно максимально возможной привлекательности маршрута из
В
, имеющий длину не менее
.
Если для некоторых
нет маршрута длиннее, чем
, затем выведите в соответствующей строке 
.
Примеры
| стандартный ввод | стандартный вывод |
| 4 4 2 4 3 4 2 1 2 4 2 1 1 3 3 4 | 3 1 1 |
| 3 2 1 3 3 2 1 1 2 1 3 | 2 -1 |
| 5 10 1 5 8 6 4 3 1 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5 | 7 3 2 1 |
Комментарий
В первом примере имеется прямой участок маршрута от стартового КПП до конечного.
Привлекательность такого маршрута 
и длина
.
Существует также путь длиной
прохождение через контрольно-пропускные пункты 
,
,
И 
, с привлекательностью, равной
.
Для 
ответом будет заданный путь длины
, так как это наиболее привлекательный путь длиной не менее
.
Анализ проблемы А
Обратите внимание, что поскольку все контрольные точки расположены на разной высоте и все участки маршрута идут от более высоких точек к более низким, график является ацикличным.Найдём его топологическую сортировку (например, просто отсортировав вершины по высоте) и дальше поработаем с ней.
Опишем два способа решения задачи за квадратичное время.
Способ первый: перебрать все возможные значения.
интересность маршрута, а затем оставить в графе только ребра 
, такой, что 
и найдите самый длинный путь из
В
, используя только такие ребра.
Время работы этого решения 
, Где 
.
Способ второй: динамическое программирование 
— максимально возможная увлекательность длины маршрута 
от
В
.
Чтобы рассчитать стоимость
рассмотреть все исходящие ребра 
и используйте релаксацию 
.
Время работы этого решения 
.
Обратите внимание, что первое из описанных квадратичных решений позволит быстро найти ответ для малоинтересных путей, а второе решение лучше подходит для коротких путей, и давайте попробуем совместить эти два подхода.
Действительно, для пути длины
правда, его обаяние не превышает 
, и наоборот, путь увлечения 
не может иметь длину больше 
.
Давайте введем параметр 
.
Для любого пути из
В
правда, ни длина его, ни его очарование не превышают 
.
Давайте применим оба решения из второго параграфа, выполнив первое только для 
, а во втором — используя только значения 
.
Итоговая сложность полученного решения: 
.
Отметим, что при желании такое решение можно реализовать с помощью 
дополнительная память.
Задача Б: Беспилотный автомобиль
Автор проблемы : Максим Ахмедов (Яндекс, МГУ, НИУ ВШ?).
| Имя входного файла: | Имя выходного файла: | Лимит времени: | Ограничение памяти: |
|---|---|---|---|
| стандартный ввод | стандартный вывод | 4 секунды | 512 мегабайт |
Как известно, компания «Яндекс» в последнее время занимается разработкой беспилотного автомобиля, в чем смогут убедиться некоторые участники финала конкурса, присутствующие в Москве.
Производство беспилотного автомобиля невозможно без тщательного тестирования на специально оборудованном полигоне.
В рамках этого задания вам будет предложено проверить возможности перемещения беспилотного автомобиля по полигону, похожему на дерево.
Многоугольник состоит из
платформы подключены
дороги.
Сайты нумеруются от
до
, а беспилотный аппарат изначально находится в
-й сайт. Цель тестирования – проехать автомобиль за минимальное время по маршруту, проходящему через каждый из участков хотя бы один раз, если известно, что автомобиль преодолевает одну дорогу за одну минуту, а время на повороты и U -поворотами можно пренебречь.
Задача усложняется тем, что в рамках этого эксперимента навигация может осуществляться только с помощью специальных радиомаяков.
На каждой площадке имеется радиомаяк, а плата за включенный радиомаяк находится на площадке.
, хватит ровно на 
минут. В выключенном состоянии маяк не тратит заряд. Изначально все маяки выключены.
Процесс перемещения происходит следующим образом.
Одновременно может быть включен только один маяк.
Если в начале минуты машина находится на платформе
, а радиомаяк находится на площадке 
и включился на
минут, затем машина движется дальше
дороги в сторону уменьшения расстояния до участка
.
Если машина уже находится на том же месте, что и радиомаяк, то ничего не происходит. Каждый маяк может быть включен на целое число минут произвольное количество раз.
Определите, можно ли составить план включения и выключения маяков таким образом, чтобы автомобиль хотя бы один раз посетил все объекты, и если да, то найти минимально необходимое для этого количество минут. Вернуться к исходной точке не требуется .
Формат ввода
В первой строке записано целое число(
) — количество сайтов.
Вторая строка содержит целые числа 
( 
), Где
— количество минут, на которое держится заряд в радиомаяке на площадке
.
В последующем
строки содержат описания дорог, каждая из которых состоит из двух целых чисел
И
(
,
) — номера подключенных площадок.
Выходной формат
Если требуемое возможно, выведите одно целое число — минимальное время, необходимое для посещения всех сайтов.
В противном случае выведите число
.
Примеры
| стандартный ввод | стандартный вывод |
| 7 0 3 0 2 4 3 3 1 2 1 3 3 4 1 5 5 6 6 7 | 9 |
| 4 0 1 1 2 1 2 2 3 1 4 | -1 |
Комментарий
В первом тесте условию соответствует следующий маршрут:- Держим включенным радиомаяк на площадке 4 в течение 2 минут, в результате чего машина оказывается на площадке 4, а маяк разряжается.
- Держим включенным радиомаяк на площадке 2 в течение 3 минут, в результате чего машина оказывается на площадке 2, а маяк разряжается.
- Держим включенным радиомаяк на площадке 5 в течение 2 минут, в результате чего машина оказывается на площадке 5, а у маяка осталось 2 минуты заряда.
- Держим включенным радиомаяк на площадке 7 в течение 2 минут, в результате чего машина оказывается на площадке 7, а у маяка остается 1 минута заряда.
Анализ проблемы Б
Эта задача требует от вас понять, как можно передвигаться по дереву, используя необычные правила движения.Вместо используемого в легенде проблемы автомобиля будем считать, что на дереве находится чип, а в вершинах дерева расположены кнопки, и нажатие одной кнопки эквивалентно включению радиомаяка на 1 секунду.
.
Таким образом, у нас есть дерево, в вершине 1 которого находится фишка, которая также имеет набор кнопок: в вершине
располагается
кнопки, нажимая на которые нужно вести машину по всему дереву.
Полезным методом решения проблемы часто является рассмотрение более простой задачи, которая отличается некоторыми незначительными деталями.
В этом случае полезно рассмотреть ситуацию, при которой кусок в конце обязательно должен вернуться в начальную вершину.
Отличительной деталью этой постановки является то, что в такой постановке чипу потребуется пройти по каждому ребру как минимум дважды (в одну сторону и в другую), что неверно для исходной задачи.
По ряду причин эта задача проще исходной.
Обратите внимание, что после выбора маршрута, чтобы его правильно пройти, необходимо назначить каждому движению по ребру свою кнопку в части дерева, расположенной за концом проходимого ребра.
Нетрудно заметить, что оптимальный требуемый маршрут будет проходить по каждому ребру не просто как минимум дважды, а на самом деле ровно дважды, так как в противном случае нам придется сопоставлять кнопки большему числу рёбер, что, очевидно, сложнее.
И наоборот, если бы мы смогли связать каждое ориентированное ребро со своей кнопкой, то мы могли бы рассматривать произвольный т. н.
Эйлеров обход дерева, а затем, используя существующее сравнение, успешно завершить этот обход. Это значит, что ответом на нашу задачу (в упрощенной постановке) всегда будет 
(это длина любого эйлерова обхода дерева), и единственное, что нужно проверить, это наличие отображения кнопок на ребра, удовлетворяющего условию, что ребро соответствует кнопке в поддереве, на которое указывает данное ребро.
.
Эта задача, по сути, представляет собой задачу сопоставления в двудольном графе (одна часть которого представляет собой набор ориентированных ребер, а другая — набор кнопок), насыщающую одну из частей.
На вопрос о существовании такого паросочетания отвечает классический факт теории паросочетания, известный как лемма Холла.
Введем некоторые обозначения – пусть 
представляет собой множество ориентированных ребер дерева, 
- много кнопок и 
Для 
это набор кнопок, находящихся в поддереве, на которое указывает край 
(формально говоря, кнопка 
тогда и только тогда, когда конец ребра
лежит между началом ребра
и кнопка 
).
Тогда лемма Холла утверждает, что искомое паросочетание существует тогда и только тогда, когда для любого набора ориентированных ребер 
в объединении поддеревьев всех ребер в 
пуговиц столько, сколько ребер в наборе
Теги: #математика #Алгоритмы #программирование #спортивное программирование #Ненормальное программирование #Яндекс.
алгоритм #Занимательные задачи #конкурс
-
Сеай, Габриэль
19 Oct, 24 -
Как Настроить Vpn На Ipad И Iphone
19 Oct, 24 -
Как Выбрать Шаблоны Wordpress Для Бизнеса
19 Oct, 24 -
Обзор Блога №40. Блогер Беларуси
19 Oct, 24 -
Новые Тарифы От Эр-Телеком
19 Oct, 24
