Разбор задач второго квалификационного раунда RCC 2016
29 мая прошёл второй квалификационный раунд чемпионата Russian Code Cup 2016, который впервые проводится на английском языке. В этот раз участникам снова нужно было в течение двух часов решить пять задач. Во втором квалификационном раунде сражались 3891 человек, и 200 лучших получили право участвовать в отборочном раунде, который состоится 19 июня. А сегодня мы предлагаем вам ознакомиться с решениями предложенных задач.
- Петя и учебник
- Григорий и банк
- Генераторы имён
- Футболки
- Тестирование мостов
Условие
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт
Убираясь сегодня в комнате, Петя нашёл свой старый учебник русского языка. Так как он с детства недолюбливает этот предмет, он начал вырывать из него страницы.
В учебнике n страниц, пронумерованных от 1 до n, которые скреплены переплётом так, что i и n — i + 1 страницы связаны друг с другом — если вырвать одну из них, вторая тоже выпадает из учебника. Пете очень нравится процесс вырывания страниц из учебника, однако он всё-таки хочет его контролировать, а именно в некоторые моменты времени ему интересно знать, какой номер у p-й по порядку страницы из оставшихся. Помогите ему с этой задачей.
Формат входных данных
Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t (1 ≤ t ≤ 1000).
Каждый из следующих t тестов описывается следующим образом: в первой строке описания теста содержатся два числа n, q (2 ≤ n ≤ 100, n — чётное; 1 ≤ q ≤ 100) — количество страниц в учебнике и количество запросов соответственно. В следующих q строк содержатся запросы двух типов:
- — i — Петя вырывает страницу с номером i;
- ? p — Петя хочет узнать, какой номер у p-й по порядку из оставшихся страниц.
Гарантируется, что в запросе первого типа удаляемая страница существует, а в запросе второго типа текущее количество страниц не меньше p.
Формат выходных данных
На каждый запрос второго типа в отдельной строке выведите номер искомой страницы.
Примеры
Входные данные
2
4 4
? 3
— 2
? 2
? 1
6 5
— 3
? 3
— 1
? 2
? 1
Выходные данные
3
4
1
5
5
2
Решение
В этой задаче нужно было просто написать то, что просят. Достаточно хранить массив isDeleted размера n, где isDeleted[i] означает, вырвана ли уже страница с номером i. Для обработки первого запроса достаточно присвоить isDeleted[i] и isDeleted[n — i + 1] значение false, а для обработки второго запроса — найти индекс p-го true в массиве isDeleted.
Асимптотика решения: O (t • q • n).
Условие
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт
Григорий работает в бухгалтерии на одном крупном предприятии. Он получает банковские переводы от покупателей и переводит деньги продавцам.
Все переводы Григорий получает и отправляет через единственное доступное отделение банка, в котором обслуживается его предприятие. Работа этого отделения устроена довольно странно. Каждый день банк работает одним из двух способов: разрешает клиентам либо отправлять, либо только принимать денежные переводы. При этом Григорий может выполнить не более одной операции: получить один перевод или сделать один перевод, в зависимости от разрешённого типа операции в этот день. Контрагента можно выбрать на своё усмотрение. При этом начальник Григория заставляет его обязательно ходить в банк и отправлять или принимать переводы каждый день, иначе он решит, что Григорий не работает, и уволит его.
Григорий должен обработать n запросов на получение денег от покупателей и m запросов на отправку денег продавцам. Григорий знает расписание работы банка, а также может договориться с каждым покупателем и продавцом о том, когда будут перечислены деньги.
В начальный момент на счёте, которым управляет Григорий, нет денег. Затем он каждый день приходит в банк и либо получает деньги на счёт, либо отправляет их с него. При этом он понимает, что может получиться так, что он не сможет расплатиться с некоторыми продавцами. Григорий не сможет расплатиться, если при наступлении оговорённого дня выплаты у него на счету денег меньше, чем требуется для оплаты услуг продавца. В таком случае деньги со счёта не переводятся, а Григорий получает выговор от начальства. Обиженный продавец отказывается поставлять товар и больше не взаимодействует с фирмой Григория.
Григорий хочет договориться о днях расчётов с продавцами и покупателями так, чтобы продавцов, с которыми он не сможет расплатиться, было как можно меньше. Помогите ему это сделать!
Формат входных данных
Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t (1 ≤ t ≤ 1000).
Каждый из тестов описывается следующим образом: в первой строке описания теста содержатся числа n и m (1 ≤ n, m ≤ 100) — количество покупателей и продавцов соответственно. Во второй строке содержится n чисел ai (1 ≤ ai ≤ 1000) — сумма, которую должен перечислить i-й покупатель. В третьей строке содержится m чисел bj (1 ≤ bj ≤ 1000) — сумма, которую нужно перечислить j-му продавцу. В последней строке описания теста содержится строка s (длина s равна n + m, s содержит n символов + и m символов -). s[k] равно +, если в k-й день банк позволяет только принимать переводы денег, а если банк работает только на отправку переводов, то s[k] равно -.
Формат выходных данных
Для каждого теста в отдельной строке выведите ответ на него — минимальное возможное количество продавцов, с которыми Григорий не сможет расплатиться.
Примеры
Входные данные
3
2 1
1 5
4
±+
1 3
1
2 2 2
-±-
2 2
2 2
3 3
±+-
Выходные данные
0
3
1
Решение
Идея решения этой задачи основана на жадных алгоритмах. Рассмотрим случайную расстановку покупателей и продавцов.
Пусть у нас есть пара покупателей ai и aj, i < j и ai < aj. i и j — позиции в выбранной случайной расстановке. Если поменять их местами, очевидно, что ответ не ухудшится, так как количество денег на счету Григория увеличится на отрезке с i по j. Поэтому выгодно, чтобы покупатели переводили деньги в порядке убывания ai.
Аналогично можно доказать, что если есть два продавца, с которыми можно рассчитаться, то выгоднее их ставить в порядке возрастания bj.
Единственный тонкий момент — это наличие продавцов, с которыми не получается расплатиться. Очевидно, что если Григорий не может расплатиться с x продавцов, то выгоднее, чтобы они были наиболее дорогими.
Основываясь на вышесказанном, получим решение задачи. Сортируем последовательности ai и bj, после чего моделируем процесс, поддерживая текущий баланс Григория.
Условие
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт
Величайший писатель всех времён Хенк Морбукс уже придумал, о чём он будет писать следующий бестселлер, но ещё не определился с именами k своих персонажей. Как и для предыдущих книг, имена он будет получать разделением специально придуманной строки на k различных и непустых частей. Помогите Хенку понять, можно ли разбить заданную строку на k различных имён.
Формат входных данных
Первая строка файла содержит количество тестов t (1 ≤ t ≤ 1000).
Каждый тест описывается двумя строками. В первой строке описания теста содержится строка длины не более 100, состоящая из строчных букв английского алфавита. Во второй строке содержится одно положительное число k (1 ≤ k ≤ 5) — на какое число различных строк нужно разделить заданную.
Формат выходных данных
Результат каждого теста должен быть выведен в описанном ниже формате.
Если разбить исходную строку можно описанным способом, то выходной файл должен содержать k + 1 строк. Первая строка должна содержать YES. (i + 1)-я строка должна содержать i-е имя. Исходная строка должна получаться конкатенацией строк в порядке вывода.
Если разбить исходную строку описанным способом нельзя, то выходной файл должен содержать одну строку NO.
Примеры
Входные данные
3
aaa
2
aaa
3
abc
3
Выходные данные
YES
a
aa
NO
YES
a
b
c
Решение
Первым делом отметим, что для любого k все строки длиной больше или равной k(k + 1)/2 можно разбить на k различных. Для этого мы возьмём подстроки длиной 1, 2, …, k — 1 и n — k(k — 1)/2. Так как k ≤ 5, то мы научились разбивать все строки длиной не менее 15. А для строк длины меньше 15 мы запускаем перебор по всем k — 1 позициям, в которых её разбиваем, и проверяем, правда ли, что в полученном разбиении все строки разные.
Условие
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт
Илья, Ваня и Влад давно участвуют в командных соревнованиях по программированию. В этом году прошло n командных соревнований, в каждом из которых ребята получили по футболке. Будем считать, что типы футболок нумеруются от 1 до n, в соответствии с соревнованиями, на которых их вручали.
У каждого мальчика есть самая любимая футболка, чуть менее любимая и так далее. А именно у каждого мальчика есть перестановка чисел от 1 до n — номера футболок, первая из которых самая любимая, а последняя — самая нелюбимая.
Сейчас ребята на соревновании. Они хотят на каждый контест надевать одинаковые футболки. Но предпочтения футболок у них могут отличаться, поэтому перед контестом они выписали на листок числа от 1 до n и по очереди вычеркивают по одному числу. Футболку, номер которой останется последним, ребята и надевают в этот раз.
Ребята всегда вычеркивают оптимально, то есть каждый старается сделать так, чтобы в итоге осталась футболка, которая ему нравится больше всего. Поэтому ребята решили попросить вас, чтобы вы написали программу, которая будет находить номер футболки, который останется в итоге.
Формат входных данных
Входные данные содержат несколько тестовых примеров. Первая строка содержит одно число t (1 ≤ t ≤ 50) — количество тестов. Далее следуют описания тестов.
Каждый тест задаётся следующим образом: первая строка содержит одно натуральное число n (1 ≤ n ≤ 13) — количество соревнований, в которых участвовали ребята.
В следующей строке находится перестановка от 1 до n — предпочтения футболок Ильи.
В следующей строке находится перестановка от 1 до n — предпочтения футболок Вани.
В следующей строке находится перестановка от 1 до n — предпочтения футболок Влада.
Ребята ходят в следующем порядке: Илья, Ваня, Влад.
Формат выходных данных
Для каждого тестового примера выведите единственное число — номер футболки, который останется в итоге.
Примеры
Входные данные
3
4
1 3 2 4
4 1 2 3
1 2 3 4
5
1 3 2 4 5
5 3 2 1 4
1 3 2 4 5
3
1 2 3
1 2 3
1 2 3
Выходные данные
1
3
1
Решение
Для решения этой задачи используем динамическое программирование по подмножествам. Обозначим как dp[i][mask] оптимальный номер футболки, которого может добиться i-й участник, если он делает ход и ему доступны футболки, соответствующие установленным битам в числе mask. Для пересчёта переберём, какую футболку он вычеркнет, и выясним, какую футболку он получит, используя значение dp[(i + 1)%3][mask1], где mask1 получается из mask обнулением соответствующего бита.
Условие
Ограничение по времени 4 секунды
Ограничение по памяти 256 мегабайт
Небольшое государство, расположенное на островах, развивает свою транспортную систему. Некоторые из островов соединены мостами таким образом, что между любыми двумя островами есть единственный путь по мостам, иначе говоря, система мостов образует дерево. Мосты могут иметь разную длину.
Перед открытием этих мостов для всех необходимо проверить их надёжность. Для этого в течение q дней двое рабочих проедут с фиксированной скоростью 1 по некоторому пути из одного острова в другой. Каждый из них проедет по своему пути, возможно начиная в разные моменты времени. Мост считается протестированным в i-й день, если в тот день оба рабочих ехали по нему одновременно в течение некоторого ненулевого промежутка времени. Для каждого из q дней тестирования определите, был ли в тот день протестирован хотя бы один мост.
Формат входных данных
Первая строка содержит два числа n и q (1 ≤ n, q ≤ 105, n ≥ 2) — число островов и дней тестирования соответственно. Следующие n — 1 строк описывают мосты в формате ui vi li (1 ≤ ui, vi ≤ n, 1 ≤ li ≤ 109) — концы моста и его длина. Каждая из следующих q строк содержит описания двух путей рабочих. Каждый путь задаётся тремя числами bi, ei, si (1 ≤ bi, ei ≤ n, 1 ≤ si ≤ 109, bi ≠ ei) — начальная и конечная вершина пути, а также время, в которое рабочий начнёт движение.
Формат выходных данных
Выведите q строк с ответами на запросы. В i-й строке выведите YES, если в i-й день был протестирован хотя бы один мост, и NO иначе.
Примеры
Входные данные
8 6
1 2 3
1 3 1
1 4 2
2 5 5
2 6 1
5 7 2
5 8 4
5 3 2 7 4 2
8 6 1 1 7 6
4 5 1 4 5 10
7 8 3 3 4 5
6 7 6 5 1 2
2 1 10 8 3 3
Выходные данные
YES
YES
NO
NO
NO
YES
Решение
Будем решать все запросы независимо друг от друга, онлайн. Для начала найдём пересечение двух путей и от каждого из путей оставим только это пересечение.
Как найти пересечение двух путей? Для этого «спроецируем» каждый из концов второго пути на первый путь. Проекцией вершины u на путь s → t назовём вершину, лежащую на пути s → t, которая является ближайшей к u по расстоянию в дереве. Этой вершиной может быть одна из следующих вершин:
- s или t;
- LCA (s, t);
- LCA (s, u), если она лежит на пути s → t;
- LCA (t, u), если она лежит на пути s → t.
Путь между проекциями каждой из вершин второго пути на первый и будет искомым пересечением, обозначим его за s' → t'.
После этого следует рассмотреть два случая:
- Пути идут по этому пересечению в разных направлениях. В этом случае можно найти момент времени, когда оба рабочих окажутся в одной точке (не стоит забывать, что он может быть полуцелым). После этого осталось проверить, что этот момент времени соответствует ребру, а не вершине.
- Пути идут в одном направлении. В таком случае можно показать, что если оба рабочих в какой-то момент времени находились на одном ребре, то это верно и для ребра с максимальной длиной на пути s' → t'. Если максимальная длина ребра на s' → t' равна M, то ответ YES тогда и только тогда, когда |t1 — t2| < M, где t1 и t2 — время начала движения.
В решении, описанном выше, использовались поиск LCA, поиск максимального ребра на пути и расстояния между двумя вершинами. Всё это можно реализовать, например, с помощью техники двоичных подъёмов за O((n + q)logn) времени и O(nlogn) памяти.
***
Чемпионат 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-тематику.
