company_banner

Разбор задач первого квалификационного раунда RCC 2016


    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-го вагона — ai метров. Расстоянием между вагонами можно пренебречь.

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

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

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

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

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

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

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

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

    Примеры:

    Входные данные
    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 мегабайт

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

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

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

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

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

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

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

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

    Примеры:

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

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

    Решение:

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

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

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

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


    Условие:

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

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

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

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

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

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

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

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

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

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

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

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

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

    Примеры:

    Входные данные
    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

    Решение:

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

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

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

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


    Условие:

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

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

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

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

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

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

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

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

    В следующих m - 1 строках даны пары чисел ui, vi (1 ≤ ui, vi ≤ 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

    Решение:

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

    Посчитаем для пары ориентированных ребер (u1, v1) в первом дереве и (u2, v2) во втором дереве значение dp[u1][v1][u2][v2], равное размеру наибольшей пары изоморфных поддеревьев, если вершина u1 перейдет в вершину u2, а вершины v1 и v2 обязательно не войдут в выбранные поддеревья. Кроме того, разрешим vi быть равной какой-нибудь фиктивной вершине -1, это будет значить, что удаленного поддерева vi нет, и можно использовать для общего поддерева все вершины. Если мы посчитаем такую величину, ответом будет максимум по всем парам вершин u1, u2 величины dp[u1][-1][u2][-1].

    Чтобы посчитать dp[u1][v1][u2][v2], нужно каким-то образом сопоставить поддеревья u1 и u2 друг другу. Заметим, что если e1 — сын вершины u1, отличный от v1, то поддерево e1 содержит меньше вершин, чем поддерево u1, при подвешивании дерева за v1. Для сыновей e1 вершины u1 и e2 вершины u2 мы по предположению индукции уже посчитали dp[e1][u1][e2][u2], так что мы знаем, сколько вершин можно добавить в искомое поддерево, если вершине e1 в нем будет соответствовать e2. Если у вершины u1k сыновей, у u2m сыновей, то мы получаем матрицу ai, j размера k•m, в которой нужно выбрать несколько ячеек с максимальной суммой, при условии, что в каждом столбце и в каждой строке выбрано не больше одной ячейки. Это стандартная задача о назначении, которая решается Венгерским алгоритмом.

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

    * * *

    Если вы не подали заявку на участие в чемпионате, у вас ещё есть время! Регистрируйтесь на сайте 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-тематику.
    Mail.ru Group
    Строим Интернет

    Комментарии 9

      –3
      Странное это ваше спортивное программирование, которое по сути чисто математические задачи, в принципе можно решать просто на бумаге с ручкой, а от программирования, смакования программирования, тут мало чего.
        0
        А что есть «смакование программирования»? Любая программа — математика, которая решается с помощью ручки. Пощупать результат? Но так в спортивном программировании нужно реализовать свою мысль. Половить баги? В спортивном программировании этого добра выше головы. Тут вопрос терминологии и определений.
          0
          Конечно, получить данные на входе, допустим из парсера или с хардварной карты, обработать их, интерполировать, агрегировать и красиво вывести в виде графика тоже математика. Но согласитесь, совершенно не та математика, требующая специальных знаний, как на соревнованиях по спортивному программированию. Да и вряд ли такие задачи когда-либо будут этих соревнованиях. Можно ли оперировать с такими данными с помощью ручки и бумажки? Да, можно, но на это у вас уйдёт слишком много времени и бумажек. И вам не нужно строить графы, поиск выхода из лабиринта или искать где сходится множество.
        –4
        Это для математиков задачи, а не для программистов! Такие знания математики нужны пожалуй только для написания своего 3D движка. Программлю успешно последние 12 лет своей жизни и честно сказать почти ничего не понял о чем тут говорится. Математику знаю (и помню) до 5 класса школы)
          0
          «Это для математиков задачи, а не для программистов!» Простите, а те же создатели 3D движка не программисты? А создатели алгоритмов или структур данных (которые все используют, возможно и вы, пусть и неявно)? Программирование бывает разным (как и много других специальностей): вот у меня знакомый 7 лет делает сайты визитки на вордпресе и знать ничего не знает про все эти энгуляры и другие новомодные течения (и я никого не упрекаю и не критикую, сайты визитки также нужно делать и это нелегкая работа ). Я, например, также ничего не понял из этого поста, но это не потому что он не для программистов, а просто потому, что я в это ни в зуб ногой (если бы я зашел на топик про haskell также ничего не понял бы ). Извините за, возможно, кривые примеры, но позволю себе привести еще один: представьте себе, после разбора конкурса для хирургов один врач заявляет, мол, эти задачи для анатомов, а не для врачей, я вон 20 лет проработал окулистом и знания анатомии мне так и не пригодились. (Опять же, я не уменьшаю важности окулистов, просто пытаюсь донести, что специалист по глазам, может ничего не понимать в хирургии и наоборот)
            0
            Используя ваш пример с врачами, можно сказать о том, что здесь даны задачи для нейрохирургов, которые назвали просто задачами для врачей. Это узкоспециализированные знания, которые касаются ну может быть максимум 10% программистов. И не способность решить их отнюдь не означает что остальные 90% – не программисты.
          +2
          Разбор задачи С:
          «Асимптотика решения — O(sqrt(a[1]) + d(a[1])•n), где d(a[1]) ≤ 1344.»

          Объясните, пожалуйста, почему именно такая асимптотика? Ведь gcd множества M_2 находится за O(log(max(M_2))), таким образом асимптотика должна быть O(sqrt(a[1]) + d(a[1])•n•log(max(a[i]))).
            0
            Давайте рассмотрим множество M_2, будем считать его gcd по-очереди добавляя в gcd числа из M_2. Пусть g — текущее значение gcd, и мы берем gcd(g, a_i). Где a_i — очередной элемент M_2. Будем рассматривать рекурсивную реализацию gcd.
            int gcd(int a, int b) {
            return b == 0? a: gcd(b, a % b);
            }

            Тогда на глубине рекурсии, равной 2, значения a и b не превосходят значения g. А так, как при каждом новом уходе в рекурсию итоговое значение gcd уменьшается в 2 раза, после вычисления gcd, g уменьшится в 2^(h — 1) раз, где h — глубина рекурсии. Так как, g мы поддерживаем по ходу, оно может уменьшится в 2 раза не более логарифма раз. В итоге, вычисление gcd множества M_2 будет работать за O(|M_2| + log(max(a_i)))
            Вроде, как-то так :)
            0
            Что мне не нравится в разборах, так это бездоказательные утверждения. «Очевидно», «заметим» и т. д. Вот не очевидно совсем.

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

            Самое читаемое