Разбор задач финала Яндекс.Алгоритма 2017

в 11:45, , рубрики: Алгоритмы, Блог компании Яндекс, Занимательные задачки, контест, математика, ненормальное программирование, Программирование, Спортивное программирование, яндекс.алгоритм

На днях завершился Яндекс.Алгоритм 2017 — наш чемпионат по спортивному программированию. В финальном раунде 25 финалистам нужно было за два с половиной часа решить шесть задач. Первое место вновь завоевал Геннадий Короткевич из питерского ИТМО — это уже четвёртая его победа после состязаний 2013, 2014 и 2015 года. Никола Йокич из Швейцарской высшей технической школы Цюриха и выпускник Университета Токио Макото Соэдзима стали вторым и третьим, повторив свои прошлогодние результаты. Вот как распределились денежные призы: победа — 300 тысяч рублей, второе место — 150 тысяч, третье — 90 тысяч.

Разбор задач финала Яндекс.Алгоритма 2017 - 1

Заявки на участие в Алгоритме 2017 подали 4840 человек. Более 60% из них — россияне. На втором месте по количеству заявок — Беларусь, далее следуют Украина, Индия и Китай. В общей сложности на чемпионат зарегистрировались жители нескольких десятков стран, включая Сингапур, Камерун, Венесуэлу и Перу.

Мы по традиции публикуем формулировки и разобранные решения задач финала.

Задача A. Горная задача

Автор задачи: Глеб Евстропов (Яндекс, НИУ ВШЭ).

Имя входного файла: Имя выходного файла: Ограничение по времени: Ограничение по памяти:
стандартный ввод стандартный вывод 5 секунд (13 для Java) 512 мегабайт

Порядком устав от соревнований по программированию и решения алгоритмических задач, Аркадий решил взять небольшую паузу и кардинально сменить род деятельности. Нашего героя всегда тянуло в горы, поэтому, используя заработанные на различных соревнованиях призовые деньги, он прикупил себе небольшой горнолыжный курорт и занялся его подготовкой к зимнему сезону.

Единственная имеющаяся трасса состоит из $n$ контрольных пунктов, пронумерованных от $1$ до $n$. Контрольный пункт $i$ находится на высоте $h_i$, причём никакие два пункта не находятся на одной высоте. Поскольку на трассе только один подъёмник, то спуск всегда начинается в контрольном пункте номер $s$ и заканчивается в контрольном пункте номер $t$. Некоторые $m$ пар контрольных пунктов соединены участками трассы, которые ведут от более высокого контрольного пункта к более низкому.

Привлекательность участка трассы, непосредственно соединяющего контрольный пункт $u$ с контрольным пунктом $v$, равна разности высот пунктов, то есть $h_u - h_v$. При этом привлекательностью маршрута, последовательно посещающего контрольные пункты $v_1, v_2, ldots, v_k$, называется минимальная из привлекательностей его участков, то есть минимум среди величин $h_{v_1} - h_{v_2}, h_{v_2} - h_{v_3}, ldots, h_{v_k} - h_{v_{k - 1}}$.

Туристов, посещающих курорт Аркадия, с одной стороны волнует привлекательность маршрута, а с другой — его длина, которая определяется как количество участков трассы в маршруте. Поскольку Аркадий уже не силён в решении подобного рода задач, то именно вам придётся вычислить для каждой возможной длины маршрута $x$ от $1$ до $n - 1$ максимально возможную привлекательность маршрута из $s$ в $t$, имеющего длину не менее $x$.

Формат входных данных

В первой строке входных данных записаны четыре целых числа $n$, $m$, $s$ и $t$ ($2 leq n leq 100,000$, $1 leq m leq 200,000$, $1 leq s, t leq n$, $s ne t$) — количество контрольных пунктов на трассе, количество участков трассы, номер стартового контрольного пункта и номер финишного контрольного пункта соответственно.

Во второй строке записаны $n$ различных целых чисел $h_1, h_2, ldots, h_n$ ($0 leq h_i leq 100,000$) — высоты, на которых расположены контрольные пункты.

Далее следуют $m$ строк, описывающих участки трассы. В $i$-й из них записаны два числа $u_i$ и $v_i$ ($1 leq u_i, v_i leq n$, $u_i ne v_i$), означающих, что $i$-й участок трассы идёт от контрольного пункта $u_i$ к контрольному пункту $v_i$. Гарантируется, что никакие два участка трассы не соединяют напрямую одну и ту же пару контрольных пунктов, что высота контрольного пункта $u_i$ больше высоты контрольного пункта $v_i$, и что существует хотя бы один маршрут от контрольного пункта $s$ до контрольного пункта $t$.

Формат выходных данных

Выведите $n - 1$ чисел по одному в строке, $i$-е из которых должно равняться максимально возможной привлекательности маршрута из $s$ в $t$, имеющего длину не меньше $i$. Если для некоторого $i$ не существует маршрута длиной не меньше $i$, то выведите в соответствующей строке $-1$.

Примеры

стандартный ввод стандартный вывод
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

Замечание

В первом примере существует прямой участок трассы из стартового контрольного пункта в конечный. Привлекательность такого маршрута равна $3$, а длина $1$. Также существует путь длины $3$, проходящий через контрольные пункты $2$, $1$, $3$ и $4$, c привлекательностью равной $1$. Для $x=2$ ответом будет являться данный путь длины $3$, поскольку это самый привлекательный путь длиной не менее $2$.

Разбор задачи A

Заметим, что поскольку все контрольные пункты расположены на различных высотах и все участки трассы идут от более высоких пунктов к более низким, то граф ацикличен. Найдём его топологическую сортировку (например, просто отсортировав вершины по высоте) и будем далее работать с ней.

Опишем два способа решить задачу за квадратичное время. Способ первый: перебрать все возможные значения $x$ увлекательности маршрута, после чего оставить в графе только рёбра $(u, v)$, такие что $h_u - h_v geq x$ и найти самый длинный путь из $s$ в $t$, использующий только такие рёбра. Время работы такого решения — $O(mC)$, где $C=h_s - h_t + 1$. Второй способ: динамическое программирование $d(v, len)$ — максимально возможная увлекательность маршрута длины $len$ из $v$ в $t$. Чтобы вычислить значение $d(v, len)$ рассмотрим все выходящие рёбра $(v, u)$ и используем релаксацию $d(v, len)=max(d(v, len), min(d(u, len - 1), h_v - h_u))$. Время работы такого решения — $O(nm)$.

Заметим, что первое из описанных квадратичных решений быстро найдёт ответ для путей с маленькой увлекательностью, а второе решение лучше подойдёт для коротких путей, и попробуем скомбинировать эти два подхода. Действительно, для пути длины $x$ верно, что его увлекательность не превосходит $C / x$, и наоборот, путь увлекательностью $y$ не может иметь длину, больше чем $C / y$. Введём параметр $k=sqrt{C}$. Для любого пути из $s$ в $t$ справедливо, что либо его длина, либо его увлекательность не превосходят $k$. Применим оба решения из второго абзаца, запуская первое только для $c leq k$, а во втором используя только значения $len leq k$. Итоговая сложность полученного решения: $O(msqrt{C})$. Отметим, что при желаниии такое решение можно реализовать с использованием $O(m)$ дополнительной памяти.

Задача B. Беспилотный автомобиль

Автор задачи: Максим Ахмедов (Яндекс, МГУ, НИУ ВШЭ).

Имя входного файла: Имя выходного файла: Ограничение по времени: Ограничение по памяти:
стандартный ввод стандартный вывод 4 секунды 512 мегабайт

Дисклеймер: ситуация, описываемая в задаче, имеет мало отношения к реальному проекту беспилотного автомобиля и является исключительно плодом фантазии авторов соревнования.

Как известно, компания Яндекс с недавних пор занимается разработкой беспилотного автомобиля, в чём некоторые из участников финала соревнования, присутствующие в Москве, имеют шанс убедиться лично. Производство беспилотного автомобиля невозможно без тщательного тестирования на специально оборудованном полигоне. В рамках данной задачи вам будет предложено проверить возможности для перемещения беспилотного автомобиля по полигону, имеющему вид дерева.

Полигон состоит из $n$ площадок, соединённых $n - 1$ дорогами. Площадки пронумерованы числами от $1$ до $n$, а беспилотный автомобиль исходно находится на $1$-й площадке. Цель тестирования состоит в том, чтобы провести за минимальное время автомобиль по маршруту, проходящему по каждой из площадок хотя бы раз, если известно, что автомобиль проезжает одну дорогу за одну минуту, а временем на повороты и развороты можно пренебречь.

Задача осложняется тем, что в рамках данного эксперимента навигация может осуществляться только по специальным радиомаякам. На каждой площадке находится радиомаяк, причём заряда включённого радиомаяка, расположенного на площадке $i$, хватает ровно на $a_i$ минут. Будучи выключенным, радиомаяк не тратит заряд. Изначально все радиомаяки выключены.

Процесс перемещения устроен следующим образом. В один момент времени может быть включён только один радиомаяк. Если в начале минуты автомобиль находится на площадке $i$, а радиомаяк расположен на площадке $j$ и включён в течение $t$ минут, то автомобиль перемещается по $t$ дорогам в сторону уменьшения расстояния до площадки $j$. Если автомобиль уже находится на одной площадке с радиомаяком, то ничего не происходит. Каждый радиомаяк можно включать на целое количество минут произвольное количество раз.

Определите, можно ли составить план включения-выключения радиомаяков таким образом, чтобы автомобиль посетил все площадки хотя бы по одному разу, и если да, то найдите минимальное необходимое количество минут для этого. Возвращаться на исходную площадку не требуется.

Формат входных данных

В первой строке находится целое число $n$ ($1 leq n leq 200,000$) — количество площадок.

Во второй строке находятся целые числа $a_1, a_2, ldots, a_n$ ($0 leq a_i leq 10^6$), где $a_i$ — количество минут, на которое хватает заряда в радиомаяке на площадке $i$.

В последующих $n - 1$ строках находятся описания дорог, каждое из которых состоит из двух целых чисел $u_i$ и $v_i$ ($1 leq u_i, v_i leq n$, $u_i neq v_i$) — номеров соединяемых площадок.

Формат выходных данных

Если требуемое возможно, выведите единственное целое число — минимальное время, необходимое для посещения всех площадок. В противном случае выведите число $-1$.

Примеры

стандартный ввод стандартный вывод
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

Замечание

В первом тесте из условия подходит, например, следующий маршрут:

  • В течение 2 минут держим включённым радиомаяк на площадке 4, в результате чего машина оказывается на площадке 4, а маяк разряжается.
  • В течение 3 минут держим включённым радиомаяк на площадке 2, в результате чего машина оказывается на площадке 2, а маяк разряжается.
  • В течение 2 минут держим включённым радиомаяк на площадке 5, в результате чего машина оказывается на площадке 5, а у маяка остаётся 2 минуты заряда.
  • В течение 2 минут держим включённым радиомаяк на площадке 7, в результате чего машина оказывается на площадке 7, а у маяка остаётся 1 минута заряда.

Таким образом за 9 минут можно посетить все площадки.

Разбор задачи B

Данная задача предлагает разобраться с тем, как можно перемещаться по дереву с использованием необычных правил перемещения. Вместо используемого в легенде задачи автомобиля будем считать, что на дереве расположена фишка, а в вершинах дерева расположены кнопки, причём нажатие одной кнопки эквивалентно включению радиомаяка на 1 секунду.

Таким образом, у нас имеется дерево, в вершине 1 которого находится фишка, в котором также имеется набор кнопок: в вершине $i$ находится $a_i$ кнопок, нажимая на которые, надо провести автомобиль по всему дереву.

Полезным приёмом при решении задачи часто оказывается рассмотрение более простой задачи, отличающейся на какую-то незначительную деталь. В данном случае полезно рассмотреть постановку, в которой фишка в конце должна обязательно вернуться в стартовую вершину. Отличительной деталью данной постановки является то, что в такой постановке по каждому ребру фишка будет обязана пройти минимум два раза (в одну и в другую сторону), что неверно для исходной задачи. По ряду причин такая задача проще исходной.

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

Обратно, если мы смогли сопоставить каждому ориентированному ребру свою кнопку, то тогда можно рассмотреть произвольный т.н. эйлеров обход дерева, а дальше, используя имеющееся сопоставление, успешно совершить этот обход.

Значит, ответ на нашу задачу (в упрощённой постановке) всегда $2n - 2$ (такова длина любого эйлерова обхода дерева), и единственное, что надо проверить — что существует сопоставление кнопок рёбрам, удовлетворяющее условию, что ребру соответствует кнопка в поддереве, на которое указывает данное ребро. Данная задача является, на самом деле, задачей о паросочетании в двудольном графе (одной долей которого является множество ориентированных рёбер, а другой — множество кнопок), насыщающего одну из долей. На вопрос о наличии подобного паросочетания даёт ответ классический факт теории паросочетаний, известный как лемма Холла.

Введём обозначения — пусть $E$ это множество ориентированных рёбер дерева, $B$ — множество кнопок, а $s(e)$ для $e in E$ это множество кнопок, которые находятся в поддереве, на которое указывает ребро $e$ (формально говоря, кнопка $b in s(e)$ тогда и только тогда, когда конец ребра $e$ лежит между началом ребра $e$ и кнопкой $b$). Тогда лемма Холла гласит, что искомое нами паросочетание существует тогда и только тогда, когда для любого набора ориентированных рёбер $A subseteq E$ в объединении поддеревьев всех рёбер в $A$ присутствует не меньше кнопок, чем рёбер в множестве $E$:

$|A| leq left| bigcuplimits_{e in A} s(e)right|$

Будем для краткости обозначать объединение множеств кнопок в правой части этого неравенства за $s(A)$. Пока неясно, как этот критерий можно эффективно проверить, потому что он состоит из экспоненциального количества условий, соответствующих вариантам выбора подмножества $A$. Однако, как мы увидим, большая часть проверяемых условий является излишней.

Во-первых, если множество $A$ таково, что в $A$ есть одно и то же ребро в двух направлениях, либо есть два ребра $e_1$ и $e_2$, "смотрящих" друг на друга, то тогда $s(A)$ совпадает с множеством всех кнопок в дереве, а значит, вне зависимости от выбора такого множества $A$, в правой части неравенства будет стоять одно и то же ребро. Значит, из всех данных неравенств достаточно проверить одно наиболее сильное, а именно то, в котором $A$ совпадает с $E$, причём эта проверка имеет наглядный смысл — фактически мы проверяем, что ориентированных рёбер не больше, чем всего кнопок имеется в дереве. Обозначим это условие за $(1)$.

В противном случае, поступим похожим образом. Если $e in A$, то аналогичным образом можно добавить в $E$ все рёбра, которые лежат в поддереве $e$ и смотрят в ту же сторону, что и $e$ (то есть, добавление которых не приводит к случаю, описанному выше). Действительно, добавление таких рёбер не изменяет множества покрываемых поддеревьями кнопок, а значит, это только усиливает проверяемое нами условие.

Теперь понятно, какую структуру имеет множество $A$ и соответствующее ему множество кнопок $s(A)$. Множество $A$ состоит из набора непересекающихся поддеревьев, в каждом из которых взяты все рёбра, смотрящие в направлении от корня поддерева, а $s(A)$ является объединением кнопок по всем этим поддеревьям. Заметим, что если всё множество $A$ не удовлетворено (то есть, $|A| > |s(A)|$), то тогда хотя бы в одно из поддеревьев в составе $A$ тоже не удовлетворено, иначе можно суммированием соответствующих неравенств для всех поддеревьев показать, что множество $A$ тоже должно быть удовлетворено.

Значит, мы окончательно поняли, для каких подмножеств $A$ достаточно проверять критерий из леммы Холла: достаточно рассмотреть $2n - 2$ подмножества, каждое из которых задаётся "корневым" ориентированным ребром $e$, и содержит все рёбра, смотрящие в направлении $e$ в поддереве $e$. Опять же, у неравенства для данного подмножества есть понятный физический смысл — необходимо, чтобы для любого поддерева кнопок в нём было не меньше, чем неориентированных рёбер в нём плюс один (здесь плюс один берётся от самого корневого ребра). Обозначим это условие для ориентированного ребра $e$ за $(2_e)$.

Условие $(1)$ очевидно можно проверить за линейное время. Условий $(2_e)$ самих по себе линейное количество, но несложным предподсчётом размеров поддеревьев дерева и количеств кнопок в них все условия можно проверить за линейное время в совокупности.

Таким образом, мы научились решать упрощённую версию задачи. Вернёмся к исходной — её отличает от нашей то, что теперь не по каждому ребру мы пройдём в обоих направлениях. Легко видеть, что наш путь теперь характеризуется финальной вершиной $t$, которая обязательно будет листовой, и тогда из множества посещаемых нами ореинтированных рёбер исчезнут рёбра, лежащие на пути от $t$ до стартовой вершины $1$. Подвесим дерево за вершину $1$, тогда по-другому можно сказать, что исчезнут все восходящие рёбра от $t$ до $1$.

Аналогичным образом применим критерий Холла и посмотрим, что изменится. Рассуждение про рёбра, смотрящие друг на друга, по-прежнему верно, и оно даёт нам условие $(1')$: ориентированных рёбер, которые мы пройдём, должно быть не больше, чем кнопок всего. Отметим здесь, что мы пройдём ровно $2n - 2 - depth(t)$ рёбер, таким образом, это условие задаёт нижнюю границу на глубину искомой терминальной вершины $t$: $depth(t) geq 2n - 2 - |B|$ (заметим, что это условие может быть выполнено автоматически, если $2n - 2 leq |B|$).

Рассуждение про независимую проверку критерия для подномжеств, задаваемых ориентированным ребром и всеми, которые лежат в его поддереве, по-прежнему верно, но теперь чуть-чуть изменится форма этих подмножеств. А именно, если $e$ — ребро, смотрящее вниз, то для него ничего не поменяется (потому как у нас по сравнению с упрощённой задачей исчезли только рёбра, смотрящие вверх). Если же $e$ — ребро, смотрящее вверх, то в зависимости от выборе вершины $t$ ребро $e$ может либо исчезнуть из двудольного графа (тогда соответствующее ему условие просто проверять не надо), либо же, левая часть соответствующего ему условия уменьшится на количество выпавших рёбер, которые лежат в поддереве $e$ и смотрят в ту же сторону, что и $e$. Нетрудно понять, что величина уменьшения левой части составляет $depth(lca(e, t))$, где $lca(e, t)$ — наименьший общий предок ребра $e$ и терминальной вершины $t$ в подвешенном дереве с корнем в $1$.

Таким образом, мы имеем набор условий следующего вида:

$ 2n - 2 - depth(t) leq |B| quad (1') $

Для рёбер, смотрящих вниз:

$ |edgesBelow(e)| + 1 leq |buttonsBelow(e)| quad (2_{edownarrow}') $

Для рёбер, смотрящих вверх:

$ |edgesAbove(e)| + 1 - depth(lca(e, t)) leq |buttonsAbove(e)|~text{или}~t~text{в поддереве}~e quad (2_{euparrow}') $

Условия $(2_{edownarrow}')$ проверим за линейное время сразу, так как они не зависят от выбора $t$. Оставшиеся два вида условий переформулируем в виде условия на положение вершины $t$. $(1')$, как уже было отмечено, эквивалентно тому, что вершина $t$ достаточно низко, то есть, находится на глубине минимум $2n - 2 - |B|$. Условие $(2_e')$, оказывается, эквивалентно принадлежности $t$ некоторому поддереву нашего дерева: действительно, перенеся в левую часть неравенства $(2_{euparrow}')$ слагаемое $depth(lca(e, t))$, получим ограничение снизу на глубину вершины, в которой путь до $t$ ответвляется от пути до $e$. Это означает, что $t$ должно быть ниже ($|edgesAbove(e)| + 1 - |buttonsAbove(e)|$)-й вершины на пути от $s$ до $e$, что тоже является условием принадллежности некоторому поддереву.

Заметим, что набор условий вида "$t$ принадлежит заданному поддереву" можно проверить за линейное время — достаточно обойти дерево, поддерживая количество удовлетворённых условий, и следить за вершинами, к которых это количество совпадает с количеством условий вообще.

Наконец, надо из всех подходящих вершин выбрать самую глубокую, проверить в ней выполнение условия $(1')$, и она и будет искомым ответом. Данное решение можно реализовать за линейное время от входных данных.

Задача C. Не менее плотный, чем требуется

Автор задачи: Максим Ахмедов (Яндекс, МГУ, НИУ ВШЭ).

Имя входного файла: Имя выходного файла: Ограничение по времени: Ограничение по памяти:
стандартный ввод стандартный вывод 3 секунда 512 мегабайт

Плотность неориентированного графа — естественная величина, полагаемая равной отношению количества рёбер к количеству вершин. Важной задачей при изучении различных графов, берущихся, в том числе, из реальной жизни (таких, как граф отношения дружбы в социальной сети, граф соавторства в научной среде или сеть белок-белковых взаимодействий в биоинформатике), является нахождение плотных подграфов — то есть, таких наборов вершин, что сужение графа на этот набор имеет высокую плотность. Нахождение подграфов высокой плотности является хорошо изученной, но довольно сложной задачей, а мы предложим вам необычный взгляд на этот сюжет — мы предложим найти подграф не менее чем заданной плотности.

Рассмотрим неориентированный граф, состоящий из $n$ вершин, пронумерованных целыми числами от $1$ до $n$, и $m$ рёбер $(u_{1}, v_{1}), (u_{2}, v_{2}), ldots, (u_{m}, v_{m})$. Пусть задан набор из $n$ неотрицательных вещественных чисел $x_1, x_2, ldots, x_n$, удовлетворяющий условию $x_1 + ldots + x_n=1$. Положим:

$lambda=sum limits_{i=1}^{m} min{x_{u_i}, x_{v_i}}$

Требуется найти подграф данного графа, имеющий плотность по меньшей мере $lambda$. Формально, требуется найти такое непустое множество вершин $A subseteq {1, 2, ldots, n}$, что $frac{|E(A)|}{|A|} geq lambda$, где $E(A)={(u_i, v_i)~mid~u_i, v_i in A}$.

Формат входных данных

В первой строке находятся два целых числа $n$ и $m$ ($1 leq n leq 200,000$, $0 leq m leq 200,000$), количество вершин и рёбер в графе.

Во второй строке находятся $n$ вещественных чисел $x_1, x_2, ldots, x_n$ ($x_i geq 0$, $x_1 + ldots + x_n=1$), заданных с не более чем шестью знаками после десятичной точки.

В $i$-й из последующих $m$ строк находятся два целых числа $u_i, v_i$ ($1 leq u_i, v_i leq n$, $u_i neq v_i$), задающих вершины, соединённые $i$-м ребром графа. Гарантируется, что в графе отсутствуют кратные рёбра и петли.

Гарантируется, что в графе существует подграф, удовлетворяющий требованию задачи.

Формат выходных данных

В первой строке выведите целое число $k$ ($1 leq k leq n$) — количество вершин в искомом множестве $A$.

Во второй строке выведите $k$ целых чисел $d_1, d_2, ldots, d_k$ — номера вершин, образующих подграф плотности хотя бы $lambda$.

Ваш ответ будет признан корректным, если плотность выведенного вами подграфа не меньше, чем $lambda - 10^{-7}$. Вершины разрешается выводить в любом порядке. Если возможных ответов несколько, разрешается вывести любой правильный.

Примеры

стандартный ввод стандартный вывод
4 4
0.2 0.1 0 0.7
1 2
2 3
3 1
3 4 		3
1 2 4
5 6
0.25 0 0.25 0.25 0.25
2 1
1 3
3 5
5 4
4 1
1 5 		4
1 5 3 4

Замечание

В первом тесте из условия: $lambda=min{0.2, 0.1} + min{0.1, 0} + min{0, 0.2} + min{0, 0.7}=0.1 + 0 + 0 + 0=0.1$

В подграфе, состоящем из вершин $1$, $2$ и $4$, присутствует единственное ребро $(1, 2)$, поэтому его плотность равна $1/3 > 0.1$.

Во втором тесте из условия:

$begin{eqnarray} lambda=min{0, 0.25} + min{0.25, 0.25} + min{0.25, 0.25} + min{0.25, 0.25} + min{0.25, 0.25} + min{0.25, 0.25} nonumber \=0 + 0.25 + 0.25 + 0.25 + 0.25 + 0.25=1.25 nonumber end{eqnarray}$

В подграфе, состоящем из вершин $1, 5, 3, 4$, присутствует 5 рёбер $(1, 3), (3, 5), (5, 4), (4, 1), (1, 5)$, поэтому его плотность равна $5/4=1.25$.

Разбор задачи C

Отметим очевидный факт: если бы мы могли эффективно найти подграф максимальной плотности в данном нам графе, он бы точно подходил в качестве ответа вне зависимости от набора значений $x_i$ (так как нам гарантируется, что ответ существует). Однако, раз задача нахождения подграфа наибольшей плотности является довольно трудной, о чём нам явно сказано в условии задачи, значит, надо каким-то образом использовать данные нам значения $x_i$ в качестве подсказки.

Верен следующий факт. Положим $A(t)={v~mid~x_v leq t}$. Утверждается, что ответ всегда можно найти среди всевозможных $A(t)$, то есть, среди подграфов, образованных каким-то суффиксом вершин в порядке сортировки по $x_i$ всегда есть хотя бы один подграф плотности не меньше $lambda$. Покажем этот факт.

Положим, аналогично, $E(t)=E(A(t))={(u, v)~mid~x_u leq t, x_v leq t}$. Рассмотрим функцию $f(t)=|E(t)| - lambda |A(t)|$. Будем рассуждать от противного — предположим, что она строго меньше нуля в каждой точке полуинтервала $[0, M)$ (что как раз значит, что для любого $t$ плотность подграфа $A(t)$, равная $frac{|E(t)|}{|A(t)|}$ строго меньше $lambda$).

Обозначим за $M$ максимальное из чисел $x_i$. Тогда $intlimits_{0}^{M} f(t) dt < 0$. Однако верна следующая цепочка равенств:

$begin{eqnarray} intlimits_{0}^{M} f(t) dt=& intlimits_{0}^{M} |E(t)| - lambda intlimits_{0}^{M} |A(t)| nonumber \=& intlimits_{0}^{M} sumlimits_{(u, v) in E} mathbf{1}{x_u leq t, x_v leq t}~dt - lambda intlimits_{0}^{M} sumlimits_{v=1}^{n} mathbf{1}{x_v leq t}~dt nonumber \=& sumlimits_{(u, v) in E} intlimits_{0}^{M} mathbf{1}{x_u leq t, x_v leq t}~dt - lambda sumlimits_{v=1}^{n} intlimits_{0}^{M} mathbf{1}{x_v leq t}~dt nonumber \=& sumlimits_{(u,v) in E} min{x_u, x_v} - lambda sumlimits_{v=1}^n x_v nonumber \=& lambda - lambda=0 nonumber end{eqnarray}$

Таким образом, мы получаем противоречие, значит, хотя бы в одной точке полуинтвервала $[0, M)$ верно неравенство $f(t) > 0$, что доказывает наше утверждение.

Таким образом, решение принимает следующий вид: упорядочиваем вершины по убыванию $x_i$, добавляем вершины одну за одной и поддерживаем количество вершин в текущем подграфе. Если плотность стала не меньше $lambda$, выводим ответ. Сложность получившегося решения — $O(n log n + m)$.

Задача D. Магазин шляп

Автор задачи: Михаил Тихомиров (МФТИ)

Имя входного файла: Имя выходного файла: Ограничение по времени: Ограничение по памяти:
стандартный ввод стандартный вывод 2 секунды 512 мегабайт

На витрине магазина выложено $n$ шляп, пронумерованных слева направо от $1$ до $n$. Шляпы бывают трёх видов: мужские, женские и универсальные. В магазин по очереди заходят покупатели, причём каждый следующий покупатель может оказаться как мужчиной, так и женщиной.

Каждый покупатель идет вдоль витрины слева направо и выбирает первую подходящую ему шляпу. Так, покупатель-мужчина выберет самую левую среди мужских и универсальных шляп, а покупатель-женщина выберет самую левую среди женских и универсальных шляп. Если ни одной подходящей шляпы на витрине нет, покупатель уходит без покупки. Каждый раз, когда кто-то покупает одну из шляп, продавец записывает номер купленной шляпы.

К концу дня все шляпы были раскуплены, и у продавца оказалась записана перестановка чисел от $1$ до $n$. Сколько существует возможных вариантов этой перестановки? Так как ответ может быть довольно большим, определите остаток от его деления на $10^9 + 7$.

Формат входных данных

В первой строке записано одно целое число $n$ ($1 leq n leq 5000$) — количество шляп на витрине.

Во второй строке записано $n$ символов — типы шляп в порядке нумерации. Символ "M" означает мужскую шляпу, символ "W" — женскую шляпу, а символ "U" — универсальную шляпу.

Формат выходных данных

Выведите остаток от деления ответа на $10^9 + 7$.

Пример

стандартный ввод стандартный вывод
3
UMW 		2
3
MWU 		4

Замечание

В первом примере первый покупатель обязательно купит первую шляпу (независимо от пола). Оставшиеся две шляпы могут быть куплены в любом порядке.

Во втором примере возможны следующие перестановки: $(1, 2, 3)$, $(1, 3, 2)$, $(2, 1, 3)$, $(2, 3, 1)$.

Разбор задачи D

В каждый момент времени должно быть продано сколько-то самых левых мужских, женских и универсальных шляп, поэтому можно придумать простое решение за $O(n^3)$ методом динамического программирования: посчитать количество $dp_{m, w, u}$ — сколько существует способов оказаться в конфигурации, в которой продано $m$ первых мужских, $w$ первых женских и $u$ первых универсальных шляп.

Оказывается, что только $O(n^2)$ состояний в этой схеме ДП достижимо. Мы приведем другое решение при помощи ДП. В текущей конфигурации обозначим $i$ и $j$ позиции самых левых непроданных шляп, которые подходят мужчинам и женщинам соответственно (если подходящих шляп не осталось, положим соответствующий индекс равным $n + 1$). Легко убедиться, что все универсальные шляпы левее позиции $max(i, j)$ обязаны быть проданными. Предположим, что $i geq j$. Если мужчина купит шляпу, то мы просто подвинем индекс $i$ на ближайшую слева подходящую шляпу. Однако, если шляпу купит женщина, то мы должны двигать вперед $j$, пропуская универсальные шляпы. Кроме того, если $i=j$, то $i$-ая шляпа универсальная и следующий покупатель (независимо от пола) ее купит, поэтому единственный ход — двигать $i$ и $j$ одновременно до ближайших подходящих позиций. В результате получаем решение с асимптотикой $O(n^2)$.

Задача E. Время делить камни

Автор задачи: Олег Христенко (МГУ, МФТИ).

Имя входного файла: Имя выходного файла: Ограничение по времени: Ограничение по памяти:
стандартный ввод стандартный вывод 1 секунд 512 мегабайт

На одной планете в далёкой галактике существует следующая легенда:

В начале времён демиург Ян Декс создал на самой высокой горе мира храм. В центре храма есть алтарь, на котором лежит куча из $n$ драгоценных камней. Каждое утро два жреца — учитель и ученик — начинают делить эти камни, беря ненулевое количество камней из кучки по очереди. Учитель делает первый ход; при этом ученик ни в какой момент времени не может иметь больше камней, чем учитель. В итоге камни должны быть поделены поровну, а на алтаре не должно остаться ни одного камня.

В момент, когда жрецы не смогут выполнить задание или же в точности повторят все действия, сделанные при дележе в какой-то из предыдущих дней, злой дух-разрушитель Баг выйдет на свободу и разрушит планету.

По заданному количеству камней $n$ вычислите максимально возможное время существования этого мира с момента начала времён и до пришествия Бага. Так как ответ может быть очень большим, выведите его остаток от деления на $10^9 + 7$.

Формат входных данных

Единственная строка ввода содержит одно целое число $n$ ($1 le n le 10^6$) — количество драгоценных камней на алтаре.

Формат выходных данных

Выведите одно целое число — максимальное возможное время существования планеты в соответствии с легендой в днях по модулю $10^9 + 7$.

Примеры

стандартный ввод стандартный вывод
6 5
1 0

Разбор задачи E

Данная задача является самой простой задачей соревнования. Фактически, в ней надо увидеть необычную переформулировку известной математической конструкции.

Переформулируем процесс деления камней. Будем считать, что учитель и ученик ходят не по очереди, а в произвольном порядке, но по-прежнему выполняется условие, что ни в один момент времени количество камней у ученика не превзойдёт количество камней у учителя. Нетрудно видеть, что такая переформулировка является эквивалентной — каждому варианту развития событий исходной задачи взаимно однозначно соответствует вариант развития событий переформулированной задачи.

Теперь легко видеть, что условие на количества камней эквивалентно условию правильности скобочной последовательности строки, в которой символ texttt{'('} соответствует взятию камня учителем, а символ texttt{')'} соответствует взятию камня учеником. Как хорошо известно из комбинаторики, количество правильных скобочных последовательностей длины $k$ равно $k$-му числу Каталана, формула для которого выглядит как $frac{(2k)!}{k!(k+1)!}$. Теперь необходимо аккуратно произвести вычисления по модулю $10^9 + 7$, и получить ответ на задачу, не забыв разобрать случай, когда число $n$ нечётно и ответ, очевидно, 0.

Задача F. Игра с XOR

Автор задачи: Lewin Gan (Dropbox)

Имя входного файла: Имя выходного файла: Ограничение по времени: Ограничение по памяти:
стандартный ввод стандартный вывод 2 секунды 512 мегабайт

Алиса и Боб играют со списком из $n$ целых чисел $a_1, a_2, ldots, a_n$.

Сначала Алиса выбирает положительное целое число $k$ (не обязательно из списка) и сообщает его Бобу. Затем Алиса и Боб по очереди совершают ходы, забирая себе целые числа из списка до тех пор, пока список не станет пустым, первым ходит Боб.

В конце игры определяется, может ли Алиса выбрать среди её чисел подмножество с поразрядной $operatorname{XOR}$-суммой ровно $k$, и если да, она выигрывает, а иначе выигрывает Боб.

Помогите Алисе определить, для каких значений $k$ она может выиграть в этой увлекательной игре.

Формат входных данных

В первой строке находится единственное целое число $n$ ($2 leq n leq 15$).

В следующей строке находятся $n$ целых чисел $a_1, a_2, ldots, a_n$ ($1 leq a_i leq 10^9$).

Формат выходных данных

Выведите единственное целое число — количество значений $m$, при которых выигрывает Алиса.

В следующей строке выведите $m$ целых чисел в возрастающем порядке, обозначающих значения $k$, при которых Алиса выигрывает.

Примеры

стандартный ввод стандартный вывод
4
3 1 3 2 		3
1 2 3

Замечание

В первом примере Алиса может выиграть, выбрав в качестве $k$ любое из чисел $1$, $2$ и $3$. К примеру, предположим, Алиса выбирает $k=1$. У Боба нет иного выбора, кроме как взять $1$, иначе Алиса сама возьмёт $1$ и тут же выиграет. Алиса ответит, взяв $2$. После этого Боб и Алиса возьмут по одному числу $3$, и Алиса сможет представить $1$ в виде $2 operatorname{XOR} 3$.

Разбор задачи F

Сначала введём некоторые обозначения:

  • Под множествами в данной задаче будем понимать мультимножества.
  • Для двух множеств $A,B$ будем обозначать за $A+B$ объединение множеств и за $A-B$ разность множеств.
  • Обозначим за $span(A)$ набор чисел, которые можно получить взятием xor-суммы по некоторому подмножеству $A$ (возможно, пустому).
  • Обозначим за $rank(A)$ минимальный размер множества, имеющего такой же $span$, как $A$.

Предположим, у Алисы на текущий момент имеется множество $A$. Мы покажем, что данное состояние является выигрышным для Алисы тогда и только тогда, когда существуют два непересекающихся множества $B_1$ и $B_2$ оставшихся чисел, такие что $span(A+B_1)=span(A+B_2)$ и $k in span(A+B_1)$. Можно считать, что ни один элемент из $B_1$ и $B_2$ не лежит в $span(A)$, так как их удаление не меняет $span$ объединения с $A$.

Предположим, существуют два непересекающихся подмножества $B_1,B_2$ такие что $span(A+B_1)=span(A+B_2)$ и $k in span(A+B_1)$, и покажем, что у Алисы есть выигрышная стратегия.

Докажем это утверждение индукцией сначала по $rank(A+B_1) - rank(A)$, а затем по количеству оставшихся чисел. Если эта величина равна 0, то $k$ уже принадлежит $span(A)$, то есть Алисы выиграла.

Для шага индукции предположим, что имеются два требуемых непересекающихся множества $B_1,B_2$. Если Боб не берёт ничего из $B_1$ или $B_2$, то Алисе подходит любой возможный ход. Действительно, если Алиса тоже возьмёт число не из $B_1$ и $B_2$, то прежние подмножества $B_1$ и $B_2$ будут подходить, однако количество чисел уменьшится, значит, по предположению индукции состояние будет выигрышным. Если же Алиса возьмёт число $p$ из, например, $B_1$, то $span((A+{p}) + B_1 - {p})=span(A+B_1)=span(A+B_2)=span((A+{p})+B_2)$ так как $p in span(A+B_2)$. Значит, можно воспользоваться предположением индукции для $B_1'=B_1-{p}, B_2'=B_2$.

Предположим, Боб возьмёт число $p$ из $B_1$. Из предположения в начале задачи, $p notin span(A)$, поэтому $rank(A+{p}) > rank(A)$. Из линейной алгебры известно, что, раз $A + B_1$ и $A + B_2$ порождают одно и то же линейное пространство и $p in (A + B_1) - (A + B_2)=B_1$, то существует такой элемент $q$ в $(A + B_2) - (A + B_1)=B_2$, что $span(A + B_2 - {q} + {p})=span(A + B_2)$. Таким образом, можно воспользоваться предположением индукции для $B_1'=B_1 - p, B_2'=B_2 - q$.

Теперь докажем в обратную сторону. Предположим, у Алисы на текущий момент есть множество $A$, а также у Алисы имеется выигрышная стратегия. Тогда мы покажем, что существуют непересекающиеся множества оставшихся чисел $B_1,B_2$, такие что $span(A+B_1)=span(A+B_2)$ и $k in span(A+B_1)$.

Будем считать раундом игры ход Боба, за которым следует ход Алисы. Будем вести индукцию по количеству раундов, которые Алисе предстоит провести, чтобы выиграть игру. Как окажется, это будет эквивалентно ведению индукции по $rank(A+B_1) - rank(A)$ (заметим, что $B_1$ нам пока здесь не известно, наша цель — продемонстрировать его существование).

Если $k in span(A)$, то есть, до победы 0 ходов, то подходят два пустых (не пересекающихся по определению) множества $B_1$ и $B_2$.

Предположим, что $k notin span(A)$. Предположим, что если Боб на своём ходу удалит некоторое число $p$, то тогда у Алисы есть возможность взять число $q$ и выиграть. По предположению индукции существуют два подмножества $X_1$ и $X_2$, такие что $span(A+X_1+{q})=span(A+X_2+{q})$ и $k in span(A+X_1+{q})$. Дополнительно, мы можем предположить, что $k notin span(A+X_1)$ (в противному случае можно сразу положить $B_1=X_1$, $B_2=X_2$).

Рассмотрим случай, в котором Боб, наоборот, возьмёт число $q$. Алиса должна иметь возможность взять некоторое число $r$ и выиграть. Таким образом, также существуют два непересекающихся множества $Y_1$ и $Y_2$, такие что $span(A+Y_1+{r})=span(A+Y_2+{r})$ и $k in span(A+Y_1+{r})$ (и, аналогично, $k notin span(A+Y_1)$).

Мы знаем, что $q$ не лежит ни в одном из множеств $X_1, X_2, Y_1, Y_2$.

Рассмотрим множества $Z_1=Y_2 + X_2 + {r}$ и $Z_2=Y_1 + X_1 + {r}$.

Заметим, что $k in span(A+Z_1)$ так как $k in span(A+Y_2+{r})$ и $A+Y_2+{r} subseteq A+Z_1$. Также отметим, что $span(A+Z_1)=span(A+Y_2+X_2+{r})=span(A+Y_2+X_2+{k})=span(A+Y_1+X_1+{k})=span(A+Z_2)$.

Положим $Z_1'=Z_1 - Y_1$ и $Z_2'=Z_2 - Y_2$. Отметим, что $Z_1' cap Z_2'={r}$. Дополнительно заметим, что $rank(A+Z_1')=rank(A+Z_1)$, так как любой $y in Y_1$ лежит в $span(A+Y_2+{r})$, и таким образом, $span(A+Z_1')=span(A+Z_2')$.

Проверим, что два подмножества $B_1=Z_1' + {q} - {r}$ и $B_2 Z_2'$ являются хорошей парой непересекающихся подмножеств. Это подтверждается тем, что $k notin span(A+Z_1'-{r})$, тогда как $q in span(A+Z_1')$, что завершает рассуждение.

Таким образом, критерий доказан, и единственное, что требуется для решения задачи — применить его. Посчитаем с помощью алгоритма Гаусса $span$ для каждого из $2^n$ подмножеств, после чего явно переберём $3^n$ пар непересекающихся подмножеств и для подходящих из них (содержащих $k$ в своём $span$'е) отметим весь их $span$ как подходящий к включению в ответ. Итоговая сложность решения — $O(3^n cdot n)$.

Автор: Яндекс

Источник

* - обязательные к заполнению поля

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js