company_banner

Russian Code Cup: итоги финального раунда

    18 сентября состоялся финальный раунд всероссийского кубка по программированию Russian Code Cup. В этом году в финал олимпиады вышли 50 программистов — 27 из России, 11 из Украины, 7 из Беларуси, двое из США и по одному из Армении, Грузии и Швейцарии.



    Победителем стал Петр Митричев из Москвы. Он получил приз в 10 тыс. долл. США. Второе место занял Евгений Капун из Санкт-Петербурга, он получил 5 тыс. долл. США. На третьем месте — Михаил Дворкин из Санкт-Петербурга с призом в 3 тыс. долл. США. Поздравляем ребят и желаем им дальнейших успехов!

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

    C полным описание задач можно ознакомиться здесь.

    Задача А. Перевод часов

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

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

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

    Посмотрим, насколько изменилось неудобство в стране в результате изменения времени в некотором городе. Пусть город имел сдвиг i часов относительно столицы. Пусть суммарный сдвиг городов, которые имеют меньший сдвиг времени, равен S, а их количество — L. Тогда добавка к неудобству с этими городами для текущего равна Li-S. Аналогично можно вычислить добавку к неудобству относительно городов, имеющих больший сдвиг времени. Эту величину следует вычесть из суммарного неудобства, выяснить новый сдвиг времени для города и добавить к суммарному неудобству соответствующую величину.

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

    Задача B. Обратная задача о черепашке

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

    Заметим следующее. Пусть у нас есть два лабиринта, в которых количество способов добраться от верхней левой до правой нижней клетки равно a и b, соответственно.
    Тогда, разместив их параллельно, как показано на рисунке, мы можем получить лабиринт, в котором a + b способов добраться из верхней левой до нижней правой клетки, а разместив их последовательно — получить лабиринт, в котором ab путей.



    Заметим, что в пустом лабиринте размера 2×2 существует два пути, а в лабиринте размера 1×1 — один путь. Следовательно, разложив число k в двоичную систему счисления и используя описанный метод, можно получить лабиринт с k путями из верхней левой в правую нижнюю клетку.

    Пример такого лабиринта для k = 19 приведен на рисунке.



    Заметим, что на каждый разряд числа k требуется 5 клеток по горизонтали, а 260 > 1018, поэтому приведенная схема позволяет создать лабиринт размером не более 300×300, как и требуется в условии задачи.

    Задача C. Разбиения таблицы

    В этой задаче требовалось подсчитать количество разбиений таблицы из нулей и единиц на 9 частей, чтобы количество единиц в заданных пяти из этих частей была четна.



    Возможно несколько подходов к решению этой задачи, рассмотрим один из них. Зафиксируем c1, c2, r1 и r2. Заметим, что при увеличении r2 на один четность количества единиц в частях A5, A7 и A9 не меняется, если строка r2 содержала четное число единиц и меняется в противном случае. Поэтому при фиксированных c1, с2 и r1 легко понять, какие r2 подходят — в зависимости от четности количества единиц в искомых частях при r2 = n — 1 подходят либо такие r2, что количество единиц в строках начиная с r2 + 1 до n четно, либо нечетно. Получаем решение за O(n3), что пока недостаточно, чтобы уложиться в отведенное ограничение по времени. Однако теперь аналогичное рассуждение можно применить к c1 и c2. При фиксированных r1, r2 и c1 увеличение c2 на один изменяет четность как раз на четность числа единиц в столбце c2. Поэтому зафиксировав r1, положив r2 = n — 1 и зафиксировав c1, легко найти количество значений c2, при которых подходят r2 с четной суммой в больших строках или с нечетной суммой.

    Асимптотика этого решения уже O(n2), что достаточно при заданных ограничениях.

    Задача D. Архиватор

    К этой задаче возможно как минимум два различных подхода: динамическое программирование или жадный алгоритм.

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

    Решение с помощью динамического программирования устроено следующим образом: в каждой вершине u будем хранить минимальный суммарный штраф p[u][x] для поддерева, если в этой вершине записать число x. Заметим, что в вершине осмысленно записывать только число, которое встречается в одном из листьев в поддереве, поэтому суммарное количество вариантов, которое следует рассмотреть есть O(n log n).

    Пересчет осуществляется следующим образом: рассмотрим вершину u с детьми v и w. Пусть мы планируем записать значение x. Если оба значения p[v][x] и p[w][x] определены, то один из вариантов поставить x в u — это поставить x в обоих детей, цена этого варианта p[v][x] + p[w][x]. Также есть вариант поставить x лишь в одного ребенка. Пусть мы планируем поставить x в v, тогда стоимость этого варианта p[v][x] + minp[w] + 1, где minp[w] — минимальное значение p[w][y] по всем y.

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

    Доказательство корректности приведенного алгоритма оставим в качестве упражнения.

    Задача E. Блэкджон

    В данной задаче необходимо выбрать подмножество дробей (карт) так, чтобы их сумма была равна единице. Таким образом, данная задача является частным случаем задачи о рюкзаке. Одним из возможных подходов к решению задачи является приведение всех дробей к общему знаменателю. Однако наименьшее общее кратное (НОК) всех возможных знаменателей составляет 232 792 560, что является слишком большим числом для дальнейшего решения получившейся «классической» задачи о рюкзаке.

    Для решения поставленную задачу необходимо разбить на независимые подзадачи. Для этого надо разбить дроби на пять групп в зависимости от знаменателя: дроби со знаменателями 11, 13, 17, 19, а также все остальные дроби. Заметим, что если выбранные из любой из этих групп дроби в сумме дают не целое число, то они не могут быть дополнены дробями из других групп до целого числа. Этот факт связан с тем, что в отдельные группы выделены большие простые знаменатели такие, что не может быть других знаменателей кратных им кроме их самих.

    В каждой из групп сумма выбранных дробей обязана быть целым числом даже, возможно, нулем. Решая задачу о рюкзаке для каждой из групп, узнаем можно ли в группе выбрать дроби так, чтобы получить некое целое число. Представляют интерес только целые числа от −100 до 100, так как сумма не более чем 100 дробей, каждая из которых по модулю не превышает единицу, по модулю не превысит 100. Также заметим, что НОК всех возможных знаменателей последней группы составляет лишь 5040, то есть число возможных вариантов числителя в сумме не превышает 1 008 001. Этот факт позволяет решить задачу о рюкзаке в каждой группе за отведенное время.

    Зная, какие целые числа можно получить в каждой из групп, необходимо проверить можно ли, выбрав по одному целому числу в каждой из групп, получить сумму равную единице. Эта задача может быть решена с помощью метода динамического программирования. Введем величину ai, j — можно ли, используя первые i групп дробей, получить сумму ровно j. Базой будет являться значение a0,0 = true и a0, j = false для j от −100 до 100 кроме нуля. Переход осуществляется следующим образом: ai, j=true, если хотя бы для одно k верно (ai-1, j-k and bi,k), и false иначе, где bi,k — значение, показывающее, можно ли в группе i выбрать дроби с суммой k. Ответом на задачу будет являться значение a5,1.

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

    Задача F. Разрезание торта

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

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

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

    Можно непосредственно проверить все прямые, являющиеся кандидатами на ответ. Самое трудное в этом — построить касательную к выпуклой оболочке из данной точки. Для этого можно перебрать все вершины выпуклой оболочки. Суммарная асимптотика такого решения составит O(mn), и программа, реализующая этот подход, не укладывается в ограничения по времени.

    Можно придумать более эффективный метод нахождения касательной. Мы предлагаем воспользоваться другим наблюдением. Предположим, что интересный угол касательной из данной точки к выпуклой фигуре составляет β. Пусть β ≤ α ≤ π/2. Тогда одна из касательных к этой фигуре с интересным углом α, разделяет эту фигуру и точку.



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



    Если хотя бы одна розочка не находится в затемненной области, то ответ не больше α. Обратное также верно.

    После этого искомый угол можно найти двоичным поиском.

    В итоге получаем решение с асимптотикой O(N (log N + I)), где N = n + m, а I — число итераций двоичного поиска.

    До встречи на Russian Code Cup 2012!

    Команда Russian Code Cup.
    Mail.Ru Group 790,89
    Строим Интернет
    Поделиться публикацией
    Комментарии 6
    • +6
      Монстры
      • +3
        Эээ, привык считать себя человеком, а не монстром! :) Хотя чтобы попасть в призовую тройку, нечеловеческое везение мне определённо понадобилось :)
        • –7
          Ботаны
        • +6
          Решением, за которое Михаил Колупаев макбукпро получил, поделитесь? :)
          • +4
            Смотришь на эти задания, и вроде не дурак, языки знаешь, алгоритмы, математику, но… Не всегда даже понятно с чего начать решать задачу.
            Что тут скажешь Respect таким талантам!

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

            Молодцы ребята!
            • +1
              Очень увлекательная статья)

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

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