Автор andrewzta, 10 лет назад, По-русски

Благодарности

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

Члены жюри, авторы и разработчики задач:

  • Виталий Аксенов Aksenov239
  • Артем Васильев VArtem
  • Николай Ведерников Niko
  • Виталий Демьянюк chavit
  • Андрей Комаров komarov
  • Георгий Корнеев
  • Павел Кротков pashkal
  • Демид Кучеренко BLIZZARD
  • Анна Малова
  • Борис Минаев qwerty787788
  • Андрей Станкевич andrewzta

Координатор разборов Виталий Аксенов Aksenov239

Прорешивали раунды:

  • Геннадий Короткевич tourist
  • Павел Маврин pashka
  • Нияз Нигматуллин niyaznigmatul
  • Владимир Смыкалов enot110
  • Дмитрий Филиппов DimaPhil
  • Сергей Цаплин Sert

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

Задача A. Разбор задач.

Идея: Анна Малова.
Реализация: Андрей Комаров.
Разбор: Андрей Комаров.

В задаче требуется составить план разбора задач так, чтобы суммарная продолжительность разбора была минимальной. Задачи должны разбираться в порядке с первой до m-й. Время разбора одной задачи состовляет t секунд. Замена разбирающего задачу члена жюри — c секунд. Если один и тот же член жюри разбирает несколько задач подряд, то замена не требуется. Про каждого члена жюри известно, какие задачи он хочет разбирать, а какие — нет.

Эта задача решается жадным алгоритмом. Выберем члена жюри, который умеет решать максимальное число задач, начиная с первой. Пусть он умеет решать k задач. Затем, выберем того, кто умеет решать максимальное число задач начиная с k-й. Будем продолжать так, пока не будут разобраны все задачи. Тогда ответом на задачу будет m · t + q · c, где q — число произведённых замен.

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

Данное решение работает за O(n·m).

Также можно было написать простое решение с помощью динамического программирования. dp[i][j] равно минимальному времени, которое тратится, если разобрали i задач и i-ую разбирал j-ый член жюри. Данный массив можно легко посчитать за O(n2m).

Задача B. На далекой Амазонке.

Идея: Виталий Аксенов.
Реализация: Демид Кучеренко.
Разбор: Демид Кучеренко.

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

  • В графе не должно быть циклов
  • В каждую вершину ведёт максимум одно ребро
  • В графе должно быть ровно a вершин, из которых существовуют исходящие ребра
  • В графе должно быть ровно b вершин, в которые существуют входящие ребра

Для начала разберем случаи, когда ответ «IMPOSSIBLE». Это случаи, когда выполняется хотя бы одно из условий:

  • Матерей больше, чем дочерей
  • Матерей больше, чем n-1 (все матерьми быть не могут)
  • Дочерей больше, чем n-1

Если такой граф возможно построить, то сначала построим цепочку из a ребер (Таким образом у нас будет задействованы a+1 женщина, и будет a матерей и a дочерей). После чего, дополним дочерьми любых матерей, чтобы дочерей стало ровно b. Может получиться так, что некоторые женщины не будут ни матерьми, ни дочерьми, но это не противоречит условию задачи.

Задача C. Лабораторная по физике.

Идея: Виталик Аксенов.
Реализация: Артем Васильев.
Разбор: Артем Васильев.

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

Запишем формулу температуры воды, если мы смешиваем холодную воду из сосуда объёмом ci и горячую воду из сосуда объёмом hj: T = p / q = (C·ci + H·hj) / (ci + hj) Преобразовав эту формулу, получим, что (H·qp) / (pC·q) = ci / hj Таким образом, мы свели задачу к следующей: задана несократимая дробь и множество числителей и знаменателей, можно ли выбрать числитель и знаменатель так, чтобы получилась заданная дробь?

Введем обозначения Ax — множество всех ci / x, где ci делится на x. Аналогично, By — множество всех hi / y, где hi делится на y. Тогда несократимую дробь p / q можно представить тогда и только тогда, когда Ap и Bq пересекаются. Стоит отметить, что суммарный размер всех множеств Ax и By равен O(M log M), где M — ограничение на объем сосудов (в данной задаче M равно 105).

При представлении Ax и By в виде отсортированных списков один запрос можно выполнить за O(M / max(x, y)). Если представлять Ax и By как битовые множества, то получается решение за O(M / 64) на запрос.

Самое быстрое решение получается, если не считать ответы для одной и той же дроби несколько раз. В этом случае можно доказать более точную оценку на время работы решения. Докажем оценку O((M + k) sqrt(M)), где k — количество запросов. Если максимум из p и q больше, чем sqrt(M), то запрос можно выполнить за O(sqrt(M)), просмотрев все элементы меньшего из множеств.

Оценим сумму времен выполнения всех остальных запросов. Запросов, выполняющихся за O(M / x) не больше, чем 2x. Cуммируя по всем x, и учитывая, что x не больше, чем sqrt(M), получаем оценку O((M + k) sqrt(M)) Суммарное время работы решения: O((M + k) sqrt(M)).

Задача D. Конструктор пил.

Идея: Николай Ведерников.
Реализация: Николай Ведерников.
Разбор: Николай Ведерников.

В задаче требуется посчитать количество перестановок, таких что:

  • ai-1ai
  • aiai + 1
Для всех i от 1 до n ⁄ 2. Назовём такую перестановку возрастающей пилообразной.

Заметим, что количество таких перестановок равно количеству перестановок, у которых на нечётных позиция стоят числа, больше своих соседей. Биективное соответствие: bi = nai. Назовём такую перестановку убывающей пилообразной. Это нам пригодится дальше для решения задачи.

Очевидно, что если длина перестановки равна 0 или 1, то ответ — 1.

Пусть мы знаем ответ для всех длин от 0 до n, найдём ответ для n+1. Будем считать общее количество пилообразных последовательностей. Для того чтобы получить количество возрастающих, нужно общее число последовательностей разделить на 2, так как количество возрастающих равно количеству убывающих.

Пусть n+1 поставили на позицию 2·k, тогда сначала у нас идёт возрастающая пилообразная длиной 2·k−1, а после возрастающая длиной n−2·k+1. На первые 2·k−1 позиций мы можем выбрать любые из n чисел. Итого, получаем, что количество перестановок длины n+1, у которых число n+1 на позиции 2·k: ansk−1 · ansn−2·k+1 · Binom(n, 2·k−1).

Пусть n+1 поставили на позицию 2·k+1, тогда сначала у нас идёт убывающая пилообразная длиной 2·k, а после возрастающая длиной n−2·k. На первые 2·k позиций мы можем выбрать любые из n чисел. Итого получам, что количество перестановок длины n+1, у которых число n+1 на позиции 2·k+1: ansk · ansn−2·k · Binom(n, 2·k).

Итого, общее число пилообразных последовательностей длины n+1: ansn+1 = ∑nk = 0 ansk · ansnk · Binom(n, k).

Задача E. Зарплата.

Идея: Анна Малова.
Реализация: Павел Кротков.
Разбор: Павел Кротков.

В данной задаче дан ориентированный граф. Все ребра можно было классифицировать на три части.

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

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

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

Задача F. Робот.

Идея: Борис Минаев.
Реализация: Борис Минаев, Артем Васильев
Разбор: Борис Минаев, Артем Васильев

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

Для начала найдем количество способов добраться из одной клетки в другую без условия, что нельзя посещать конечную клетку раньше последнего хода. Такую задачу можно решать независимо по координатам, а потом перебрать, сколько ходов было совершено по одной координате, а сколько по другой. Как решать задачу в одномерном случае? Пусть изначально робот имеет координату x1, а в конце должен иметь координату x2. Пусть a=|x2-x1|, а всего было совершено t ходов. Тогда количество различных способов будет равно количеству сочетаний из t по (t-a)/2 (при этом t-a должно быть неотрицательным и четным). Однако нужно учесть, что робот может иметь только положительную координату в процессе путешествия. Для этого необходимо просто вычесть из полученного результата количество способов добраться из клетки -x1 в x2. Это справедливо, так как между путями из x1, которые нарушают требование положительности координаты, а также всеми путями из -x1 можно показать взаимно однозначное соответствие. Соответствующие друг другу пути будут иметь зеркальные первые части (до момента входа в клетку 0) и общие вторые части.

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

Теперь рассмотрим, как учесть то, что робот не может заходить в конечную клетку до последнего хода. Будем считать ответ с помощью динамического программирования. Пусть уже посчитано количество способов дойти до клетки за меньше чем t ходов. Чтобы посчитать это значения для t ходов, рассмотрим общее количество способов сделать это за t ходов и вычтем из него все способы, которые заходят в конечную клетку до хода t. Для этого переберем номер первого хода, в который робот посетит конечную клетку и умножим соответствующее ему количество способов на количество способов выйти из клетки (x2, y2) и вернуться в нее за оставшиеся время. При этом, робот может сколько угодно раз посещать конечную клетку (во второй части).

Заметим, что изложенное решение работает пока за t2. Для более быстрого решения следует рассуждать в терминах производящих функций. Обозначим f(x) = f0 x0 + f1 x1 + ... + ft xt + ..., где fi — ответ не задачу. Аналогично определим count(x) — производящая функция для количества путей, без учета условия первого захода в конечную клетку на последнем ходу, cycle(x) — производящая функция для количества путей из конечной клетки в саму себя. Из рекуррентных соотношения для fi, можно вывести соотношение на производящие функции: f(x) = count(x) — f(x) cycle(x), откуда f(x) = count(x) / (cycle(x) + 1) = count(x) (cycle(x) + 1)-1. Для вычисления f необходимо посчитать первые t + 1 членов дроби в правой части. Это можно сделать, вычислив обратный к cycle(x) + 1 многочлен по модулю xt+1, и перемножив count(x) с результатом. Взятие обратного многочлена по модулю xt+1 можно выполнить за время O(t log t) с использованием быстрого преобразования Фурье. Итоговое время работы: O(t log t).

  • Проголосовать: нравится
  • +38
  • Проголосовать: не нравится

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

Задачу D еще можно решать динамикой dp[length][lastNumber], пересчет сводится к суммированию нескольких подряд идущих значений для длины length-1, а это можно соптимизить префиксными суммами: 6838098 Ideone

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    А еще можно заметить, что заводить отдельные массивы для префиксных сумм не нужно=) Одно из авторский решений было именно таким.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится -13 Проголосовать: не нравится

      Да понятно, что не нужно и что только два слоя используются, но разве об этом стоит беспокоиться на контесте, если и так все заходит?

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      А ещё можно было найти последовательность в oeis.org, а там есть такое вот компактное решение =)

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Да, это решение круто тем что там нет умножений.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      В нем нет ни умножений, ни деления на два, и даже C-шки не надо предподсчитывать.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В разборе B потерян еще один случай на impossible: если матерей ноль, а дочерей больше нуля.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Согласен, поправил!

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Числа на входе были натуральные, а значит нуля быть не могло. А вообще, если дочерей ноль, а матерей больше ноля, то тоже impossible

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Ага, поторопился поправить, поправил обратно ;).

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    UPD. Не заметил коментарий BLIZZARD :)

»
10 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Еще, кстати, зачем в D усложнять? Можно совершенно также считать только возрастающие. Если мы интересуемся числом возрастающих, то n+1 может быть только на четной позиции, и разбивает последовательность на две возрастающих.

»
10 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

А в E, конечно, надо еще учесть, что могут быть ребра, которые ни при какой расстановке не дают решения.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В задаче D не хватает замечания, что делить каждый раз ответ на 2 (получить количество возрастающих пилообразных из общего количества) нужно по модулю 10^9+7. Если кто-то сходу не может этого сделать, то можно поступить так:

  • при нечётных n считаем сумму ans_k · ans_{n−k} · Binom(n, k) не от 0 до n, а от 0 до n/2 (из симметрии вторая половина суммы такая же).

  • при чётных n считаем ту же сумму от 0 до n/2-1 и прибавляем к ней ans_{n/2} * ans_{n/2} * (Binom(n, n/2) / 2). А Binom(n, n/2) / 2 = Binom(n-1, n/2) при чётных n.

То есть, если очень хочется, то можно обойтись и без деления.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Можно просто модуль на два домножить, а в конце поделить на два ответ.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Тогда складывать, видимо, придётся либо в long long'ах, либо в unsigned int'ах и очень аккуратно следить за поведением при переполнении.

»
10 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

В задаче F перебирать количество времени на каждую координату не нужно, этот же результат получается за O(1) формулой. Чтобы вывести формулу, повернём поле на 45°, теперь каждый ход двигает робота и по x, и по y, и можно просто перемножить количество путей. Учесть условие незахода в неположительные координаты в двумерном случае не намного сложнее, чем в одномерном: из всех путей в (x2, y2) вычтем пути в ( - x2, y2) и (x2,  - y2) и прибавим пути в ( - x2,  - y2) (вот такая формула включения-исключения). На последнем этапе, чтобы быстро обратить многочлен, нужно использовать метод Ньютона, а не просто FFT (если просто вычислить FFT, обратить поэлементно и вычислить обратное FFT, то это будет обращение по модулю x2k - 1, что не то, что нужно).

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А можно поподробнее про метод Ньютона? Не очень понятно, как его применять к производящим функциям.

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Здесь скорей не производящие функции, а формальные степенные ряды. К ним метод Ньютона для обращения применяется почти так же, как и к числам, причём можно доказать, что на каждом шаге количество правильно вычисленных элементов удваивается. Соответственно, если выполнять шаги с 2, 4, 8 и т. д. элементами, то всего будет O(n) элементов (поэтому сложность будет ).

      Про алгоритмы для степенных рядов можно почитать, например, у Кнута в главе 4.7 (задача 6 как раз посвящена вычислению обратного).

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    То есть метод Ньютона сойдется за итераций, а в нем каждая итерация — FFT за операций, т.е. всего за ?

    За такое время можно и по-другому: заметим, что коэффициент при x0 в cycle(x) равен 1, введем q(x) = cycle(x) - 1 и будем искать (2 + q(x)) - 1 = . Одна вторая просто вычисляется по модулю p как (p + 1) / 2, . Остается , т.к. r(0) = 0. Степенная сумма считается за умножений аналогично задачам про степенную сумму для матрицы, одно умножение выполняется за при помощи FFT — всего .

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Необязательно вычислять весь ряд на каждой итерации. Можно на первой итерации вычислить только первые два элемента, на второй — четыре, на третьей — восемь и т. д. Общая сумма будет .