Merthyr Tunnel by Pictonart

8 мая состоялся первый квалификационный раунд чемпионата Russian Code Cup 2016. Напоминаем, что в этом году состязание программистов впервые проводится и на английском языке, так что языковой барьер теперь не является препятствием для наших зарубежных участников. Для прохождения первого квалификационного раунда было необходимо решить пять задач. На решение отводилось не более двух часов. Учитывалась не только правильность, но и скорость решения. Всего в раунде приняли участие 3559 человек, из которых занявшие первые 200 мест переходят на следующий этап соревнований. А пока давайте рассмотрим решения предложенных задач:

1. Двоичная строка
2. Поезд и туннель
3. Красивое разбиение
4. Подготовка задач
5. Похожее метро

Задача A. Двоичная строка

Условие:

Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

Петя написал на доске строку длины n из нулей и единиц. После этого он посмотрел на все пары стоящих подряд символов и выяснил, что пара 00 встречается a раз, пара 01 встречается b раз, пара 10 встречается c раз, а пара 11 — d раз (a?+?b?+?c?+?d?=?n?-?1).

Хулиган Гриша стер его строчку. Погрустив, Петя теперь хочет восстановить какую-нибудь строчку, для которой выполняются те же условия на количество пар соответствующих соседних символов. Помогите ему!

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

На ввод подаётся несколько тестовых примеров. Первая строка содержит целое положительное число t (1???t???10?000) — количество тестовых примеров.

Каждый тестовый пример описывается одной строкой, содержащей четыре числа a, b, c и d (0???a,?b,?c,?d???20) — количество пар соседних символов, равных 00, 01, 10, 11, соответственно.

Гарантируется, что a?+?b?+?c?+?d???1.

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

Выведите t строк. Для каждого тестового примера выведите искомую строку, состоящую из нулей и единиц, или impossible в случае, если такой строки не существует.

Примеры:

Входные данные
5
0 0 1 0
1 0 0 1
1 1 1 1
2 1 1 2
1 2 3 4

Выходные данные
10
impossible
00110
0001110
11111001010

Решение:

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

• • Либо |b?-?c|?>?1
• • Либо b?=?0, c?=?0, и при этом a???0 и d???0

Для остальных случаев будем решать в два этапа: Сначала соберем минимальную строку, которая будет удовлетворять условиям на строки 01 и 10, а затем допишем после первого встреченного нуля a?-?1 ноль, а после первой встреченной единицы d?-?1 единицу. Очевидно, что условия на 01 и 10 от таких действий не испортятся.

Задача B. Поезд и туннель

Условие:

Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

Петя решил отправиться в путешествие. Сейчас он едет в поезде. Поезд состоит из n вагонов, длина i-го вагона — a_i метров. Расстоянием между вагонами можно пренебречь.

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

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

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

Входные данные содержат несколько тестовых примеров. Первая строка содержит одно число t (1???t???100) –— количество тестов. Далее следуют описания тестов.

Каждый тест задается следующим образом: первая строка содержит два натуральных числа n, h (1???n???10⁵, 1???h???10⁹) — количество вагонов в поезде и длину туннеля в метрах. Следующая строка теста содержит n натуральных чисел a_i (1???a_i???10⁹) — длины вагонов в метрах. Следующая строка содержит n чисел, i-е из который равно 1, если в i-м вагоне изначально включен свет, и 0 в противном случае. Вагоны перечисленны от головы к хвосту поезда.

Сумма значений n по всем тестам не превышает 10⁶.

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

Для каждого тестового примера выведите единственное число — наименьшее количество вагонов, в которых нужно включить свет.

Примеры:

Входные данные
2
7 10
5 3 4 5 9 9 9
1 0 0 0 1 0 0
5 2
1 2 3 1 1
1 1 0 1 1

Выходные данные
2
1

Решение:

Разобьем весь поезд на отрезки вагонов без света. Будем идти по каждой группе из таких вагонов, и в том вагоне, на котором суммарная длина вагонов становится не меньше h, будем включать свет. Очевидно, что данная стратегия дает наименьший результат. Также нужно не забыть включить свет в первом и последнем вагонах: при въезде в туннель и выезде из него, соответственно, эти вагоны образуют темный момент времени.

Задача C. Красивое разбиение

Условие:

Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

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

Так, на уроке информатике учитель выписал на доску массив целых чисел, а Петя сразу же заметил, что его элементы можно разбить на два набора M₁ и M₂ так, что gcd(M₁) и gcd(M₂) довольно большие. Здесь gcd(M), где M — непустой набор чисел, означает наибольший общий делитель всех чисел из M.

Петя решил обобщить задачу: по данному массиву чисел он хочет найти разбиение его элементов на два непустых набора M₁ и M₂, чтобы min(gcd(M₁),?gcd(M₂)) был как можно больше. Помогите ему с этой задачей.

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

Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t (1???t???1000).
Каждый из тестов описывается следующим образом: в первой строке описания теста содержится число n (2???n???5•10⁴) — количество элементов массива. В следующей строке содержатся n чисел a_i (1???a_i???10⁹) — элемент1 массива.

Сумма значений n во всех тестах одних входных данных не превышает 5•10⁴.

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

Для каждого теста в отдельной строке выведите ответ на него — максимальное возможное значение min(gcd(M₁),?gcd(M₂)).

Примеры:

Входные данные
3
5
3 2 4 6 9
3
3 5 14
4
6 4 6 6

Выходные данные
2
1
4

Решение:

Первый элемент массива входит либо в M₁, либо в M₂. Не умаляя общности, будем считать, что он входит в M₁. Тогда a[1] делится на gcd(M₁), то есть gcd(M₁) — делитель a[1].

Переберем все делители a[1] (их не больше 1344 для чисел до 10⁹). Рассматривая текущий делитель d, возьмем все элементы массива, делящиеся на d, в M₁ (так как от этого gcd(M₁) не станет меньше d, а чем меньше элементов в M₂, тем gcd(M₂) больше), а все остальные элементы в M₂ и обновим ответ величиной min(gcd(M₁),?gcd(M₂)). Заметим, что мы можем пренебречь тем, что M₂ будет пустым, считая в этом случае gcd для него равным бесконечности, поскольку все элементы в таком случае делятся на d, то и gcd(M₂) будет не меньше d.

Асимптотика решения — O(sqrt(a[1])?+?d(a[1])•n), где d(a[1])???1344.

Задача D. Подготовка задач

Условие:

Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

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

Он пока не знает, сколько именно друзей ему будут помогать, но хочет справедливо распределить работу между помощниками. Поэтому для каждой задачи он хочет определить такое целое число x_i, чтобы каждый из друзей потратил на её подготовку ровно x_i минут. Андрей считает, что задача i получится качественной, если все друзья в сумме потратят на её подготовку хотя бы t_i минут.

Иногда Андрей понимает, что неправильно оценил время, которое необходимо для качественной разработки какой-то задачи, и увеличивает или уменьшает t_i на 1. Вам необходимо помогать Андрею оценить, сколько суммарно времени потребуется для подготовки задач.

Заданы начальные оценки времени на подготовку задач t_i. Требуется обработать m запросов. Каждый запрос описывается следующим образом:

• 1 i — Андрей решил увеличить значение t_i на один;
• 2 i — Андрей решил уменьшить значение t_i на один;
• 3 k — Андрей хочет узнать, сколько суммарно времени потребуется одному другу на подготовку задач, если ему будут помогать k его друзей.

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

В первой строке задано два целых числа n и m (1???n,?m???10⁵) — количество задач и количество запросов.

В следующей строке заданы n целых чисел t_i (1???t_i???5•10⁵) — время, которое необходимо для подготовки i-й задачи по начальной оценке Андрея.

В следующих m строках следуют запросы. Каждый из них описывается двумя числами, первое из которых — его тип. Если тип 1 или 2, то второе число i (1???i???n) является номером задачи. А если тип 3, то второе число k (1???k???5•10⁵) это количество друзей, которые собираются помогать Андрею.

Гарантируется, что t_i всегда находится в пределах от 1 до 5•10⁵.

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

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

Примеры:

Входные данные
5 11
1 2 3 4 5
3 1
3 2
3 3
1 1
3 1
3 2
3 3
2 5
3 1
3 2
3 3

Выходные данные
15
9
7
16
9
7
15
8
7

Решение:

Для начала решим задачу, если нет запросов на изменение времен. Из массива t_i сгенерируем новый массив cnt_j, в котором будем хранить количество задач, на которые необходимо потратить j минут, а также предподсчитаем массив его префиксных сумм. Тогда количество времени, которое потратит каждый друг, если их всего k, можно посчитать за O(MAX?/?k), где MAX — максимальное необходимое на задачу время (просто перебрав, на какие задачи потребуется 1, 2,… MAX?/?k минут). Как известно, суммарное время работы такого алгоритма для всех k от 1 до MAX равно O(MAXlog(MAX)).

Теперь посмотрим, что происходит, когда время, необходимое на задачу, изменяется с t на t?+?1. Ответы поменяются только для k являющихся делителями t. Поскольку максимальное количество делителей у чисел до 5•10⁵ равно 200, то можно просто их все перебрать за время пропорциональное их количеству и обновить ответ только для них.

Аналогично, если время изменяется с t на t?-?1, то ответы меняются для чисел, которые являются делителями t?-?1.

Задача E. Похожее метро

Условие:

Ограничение по времени 3 секунды
Ограничение по памяти 256 мегабайт

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

Чтобы доказать другу Пете, что карты метро обоих городов действительно похожи, Вася хочет предъявить ему связный набор из k станций a_i в Байтляндии, и соответствующий набор из k станций b_i в Байтовии, такие, что для любых i, j между станциями a_i и a_j в Байтляндии есть тоннель тогда и только тогда, когда есть тоннель между станциями b_i и b_j в Байтовии. Набор станций называется связным, если от любой станции этого набора можно доехать до любой другой станции набора, проезжая только по станциям этого набора.

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

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

В первой строке дано одно целое число n (1???n???50) — количество станций метро в Байтляндии.

В следующих n?-?1 строках даны пары чисел u_i, v_i (1???u_i,?v_i???n) — номера станций в Байтляндии, между которыми есть тоннель. Гарантируется, что между любой парой станций есть ровно один простой путь.

В следующей строке дано одно целое число m (1???m???50) — количество станций метро в Байтовии.

В следующих m?-?1 строках даны пары чисел u_i, v_i (1???u_i,?v_i???m) — номера станций в Байтовии, между которыми есть тоннель. Гарантируется, что между любой парой станций есть ровно один простой путь.

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

Выведите одно целое число k — максимально возможный размер пары похожих наборов станций.

Примеры:

Входные данные
3
1 2
2 3
3
1 3
3 2

Выходные данные
3

Входные данные
5
4 1
2 4
4 3
3 5
5
1 2
2 3
3 4
4 5

Выходные данные
4

Решение:

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

Посчитаем для пары ориентированных ребер (u₁,?v₁) в первом дереве и (u₂,?v₂) во втором дереве значение dp[u₁][v₁][u₂][v₂], равное размеру наибольшей пары изоморфных поддеревьев, если вершина u₁ перейдет в вершину u₂, а вершины v₁ и v₂ обязательно не войдут в выбранные поддеревья. Кроме того, разрешим v_i быть равной какой-нибудь фиктивной вершине -1, это будет значить, что удаленного поддерева v_i нет, и можно использовать для общего поддерева все вершины. Если мы посчитаем такую величину, ответом будет максимум по всем парам вершин u₁, u₂ величины dp[u₁][-1][u₂][-1].

Чтобы посчитать dp[u₁][v₁][u₂][v₂], нужно каким-то образом сопоставить поддеревья u₁ и u₂ друг другу. Заметим, что если e₁ — сын вершины u₁, отличный от v₁, то поддерево e₁ содержит меньше вершин, чем поддерево u₁, при подвешивании дерева за v₁. Для сыновей e₁ вершины u₁ и e₂ вершины u₂ мы по предположению индукции уже посчитали dp[e₁][u₁][e₂][u₂], так что мы знаем, сколько вершин можно добавить в искомое поддерево, если вершине e₁ в нем будет соответствовать e₂. Если у вершины u₁ — k сыновей, у u₂ — m сыновей, то мы получаем матрицу a_i,?j размера k•m, в которой нужно выбрать несколько ячеек с максимальной суммой, при условии, что в каждом столбце и в каждой строке выбрано не больше одной ячейки. Это стандартная задача о назначении, которая решается Венгерским алгоритмом.

Итоговая сложность решения — O(n⁵), n² способов выбрать пару ребер в двух деревьях и O(n³) — время работы Венгерского алгоритма. Для оптимизации можно не решать задачу о назначении для одинаковых (изоморфных) пар деревьев несколько раз, а запомнить ответ.

* * *

Если вы не подали заявку на участие в чемпионате, у вас ещё есть время! Регистрируйтесь на сайте Russian Code Cup до 29 мая и примите участие во втором квалификационном раунде.

Чемпионат Russian Code Cup входит в число инициатив Mail.Ru Group, направленных на развитие российской IT-отрасли и объединённых ресурсом IT.Mail.Ru. Платформа IT.Mail.Ru создана для тех, кто увлекается IT и стремится профессионально развиваться в этой сфере. Проект объединяет чемпионаты Russian Ai Cup, Russian Code Cup и Russian Developers Cup, образовательные проекты Технопарк в МГТУ им. Баумана, Техносфера в МГУ им. М.В. Ломоносова и Технотрек в МФТИ. Кроме того, на IT.Mail.Ru можно с помощью тестов проверить свои знания по популярным языкам программирования, узнать важные новости из мира IT, посетить или посмотреть трансляции с профильных мероприятий и лекции на IT-тематику.