By RussianCodeCup, 4 years ago, In Russian,

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

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

Руководитель подготовки задач Андрей Станкевич andrewzta

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

  • Виталий Аксенов Aksenov239
  • Артем Васильев VArtem
  • Николай Ведерников Niko
  • Илья Збань izban
  • Георгий Корнеев
  • Анна Малова
  • Борис Минаев qwerty787788
  • Дмитрий Филиппов DimaPhil
  • Григорий Шовкопляс GShark

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

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

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

Перейдем теперь к разбору задач.

Задача A. Игра со строками

Идея: Григорий Шовкопляс.
Реализация: Григорий Шовкопляс.
Разбор: Григорий Шовкопляс.

В задаче дана строка, с которой можно делать следующие операции:

  • удалить три подряд идущих единицы;
  • удалить два подряд идущих нуля;
  • заменить подстроку «01» на подстроку «10»;
  • заменить подстроку «10» на подстроку «01».
Нужно посчитать, сколько существует способов получить строку определенной длины из данной, применяя эти операции.

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


Теперь с помощью этих операций получим из исходной строку, где все нули стоят в начале, а единицы в конце. Из получившейся строки мы можем получить строку новой длины, ничего не переставляя, так как все единицы и нули уже сгруппированы. Строку длины k, можно получить из строки длины n, удалив 3x единиц и 2y нулей, где k = n — (3x + 2y). Значения x и y можно перебрать.


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

Задача B. Разбиение на команды

Идея: Григорий Шовкопляс.
Реализация: Дмитрий Филиппов.
Разбор: Дмитрий Филиппов.

В задаче дан граф, на каждом ребре которого написаны числа 0 или 1, означающие, что концы ребра одного цвета или разного соответственно. Также некоторые вершины графа покрашены в белый или черный цвет. Спрашивается, можно ли как-нибудь покрасить в черный и белый цвета остальные вершины, чтобы информация, написаная на ребрах, была верна, и количество вершин черного и белого цвета было одинаковым?

Разобьем наш граф на компоненты связности. Заметим, что, зная цвет одной вершины в компоненте, мы можем восстановить цвет всех остальных. Из этого следует, что если в компоненте хотя бы одна вершина уже покрашена, раскраска всей компоненты единственна (кроме случая, когда в полученной раскраске нарушится какое-то из требуемых условий, тогда ответ на задачу — «NO»). Если же ни одна вершина еще не покрашена, вариантов раскраски два — можно покрасить любую вершину компоненты в белый цвет, восстановить цвета остальных вершин, а после этого, если их инвертировать — получим вторую раскраску.


Несложно заметить, что мы свели нашу исходную задачу к задаче о рюкзаке — из каждой компоненты мы можем взять некоторое количество белых вершин, и всего их надо набрать n ⁄ 2 (если n нечетное, ответ на задачу — «NO»). А это уже можно решить с помощью динамического программирования за O(n2).

Задача C. Карта.

Идея: Георгий Корнеев, Виталий Аксёнов.
Реализация: Виталий Аксёнов.
Разбор: Виталий Аксёнов.

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

Рассмотрим сначала самую простую версию задачи. Дан прямоугольник, и нужно его сложить, получив минимальную площадь. Очевидно, что его нужно складывать по линии сетки, ближайшей к середине. (Если таких две, то можно сложить по любой.) Рассмотрим функцию площади от позиции сгиба. Для прямоугольника с углами (x1, y1) и (x2, y2) эта функция имеет следующий вид:

  • На отрезках (-∞; x1] и [x2; +∞) функция равна площади прямоугольника;
  • На отрезке [x1; (x1 + x2) / 2] функция линейно убывает с коэффициентом y2y1;
  • На отрезке [(x1 + x2) / 2; x2] функция линейно возрастает с коэффициентом y2y1.
Итого: функция меняет своё состояние только в трёх точках. Между двумя подряд идущими точками функция является линейной.

Заметим, что так как наша задача дискретная, в случае, когда (x1 + x2) не делится на два, лучше бить функцию на пять участков между точками x1, ⌊(x1 + x2) / 2⌋, ⌈(x1 + x2) / 2⌉ и x2.

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

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

Задача D. Декартовы деревья.

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

В задаче дано n чисел yi, нужно было посчитать, сколько декартовых деревьев можно построить на множестве (i, yi).

Для начала заметим, что если все n чисел yi равны одному и тому же числу, то ответ — Cn, n -е число Каталана. Понять это можно, например, исходя из рекуррентной формулы: если в левое поддерево определить k вершин, то в правом окажется n-k-1 вершин, то есть Cnk=0n Ck·Cn-k-1.

Рассмотрим все вхождения максимального числа в массиве. Любая вершина с таким приоритетом может быть либо корнем, либо быть ребенком другой вершины с таким же приоритетом. Пусть вхождения максимума имеют индексы a1, a2, ..., ak. Тогда мы должны построить какое-то декартово дерево на вершинах a1, a2, ..., ak, и подвесить к нему какие-то декартовы деревья, построенные на вершинах (1, ..., a1-1), (a1+1, ..., a2-1), ..., (ak+1, ..., n). Заметим, что для соседних ai и ai+1 в любом декартовом дереве, построенном лишь на максимальных вершинах, одна из этих вершин будем предком другой, поэтому поддерево, построенное на вершинах (ai+1, ..., ai+1-1), мы сможем однозначно подвесить за одну из этих двух вершин.

Таким образом, число способов построить декартово дерево на вершинах с l по r равно cnt(l, r)=C k · cnt(l, a1-1) · ... · cnt(ak+1, r). Ответом будет являться cnt(1, n).

Задача E. Аллея.

Идея: Борис Минаев.
Реализация: Борис Минаев.
Разбор: Борис Минаев.

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

Рассмотрим, сколько необходимо сделать разбиений, чтобы ответ получился не более Ans. Для каждого отрезка длины Len необходимо сделать (Len — 1)/Ans разбиений (результат деления округляется вниз). Построим функцию количества необходимых разбиений от ответа для каждого отрезка. Сложим эти функции для всех отрезков. Для того чтобы найти минимальное значение Ans, которое можно достичь, сделав не более чем K разбиений, воспользуемся двоичным поиском.

Будем хранить функции в сжатом виде, а именно, сохраним значение функции для Ans только, если f(Ans) ≠ f(Ans-1). Можно доказать, что для отрезка длины Len потребуется O(sqrt(Len)) памяти, чтобы сохранить его функцию. Позиции, в которых меняется значение функции, можно определить за время пропорциональное их количеству. Максимальное суммарное число позиций изменения будет достигаться на тесте, в котором все отрезки имеют одинаковую длину. В случае ограничений, которые даны в условии задачи, их количество не может превышать 106·sqrt(103)=107.5.

Чтобы объединить несколько функций, которые сохранены в сжатом формате, необходимо отсортировать все моменты изменения функций. Для этого разобьем все позиции, в которых функции изменяются, на два класса. В первый класс отнесем все позиции, которые меньше 106. Их можно отсортировать подсчетом за время пропорциональное их количеству. Остальных же позиций будет немного, и для их сортировки можно использовать встроенные функции языка. Чтобы убедиться, что количество позиций, которые больше 106 невелико, сделаем следующее. Для того, чтобы отрезок максимальной длины не превосходил 106, достаточно сделать не более Len/106 разбиений отрезков. Поскольку, в условии задачи суммарная длина отрезков не превосходит 109, то количество изменений функции, позиции которых превосходят 106, будет меньше 1000.

Задача F. Освещение сцены.

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

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

  1. Сумма мощностей должна быть не меньше Z;
  2. Множества выходов выбранных прожекторов попарно не пересекаются.
Подмассив с такими свойствами будем называть хорошим.

Для начала решим задачу для одной фиксированной левой границы. Такую задачу можно решить при помощи динамического программирования по двоичным маскам: dpmask — это максимальная стоимость прожекторов, для которых объединение множеств выходов является подмножеством mask. Формула пересчета для добавления одного элемента (p, m) выглядит так: dp'mask = max(dpmask, dpmask — m + p), если m является подмаской mask, и dpmask, иначе. Добавление одного элемента можно реализовать за O(2k). Когда dp2k — 1 становится больше или равно Z, надо выдать ответ.

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

  1. Добавить элемент в конец;
  2. Удалить элемент из начала;
  3. Ответить на запрос: "Является ли текущее множество прожекторов хорошим?".

Решение данной задачи использует реализацию очереди на двух стеках с идеями из метода реализации очереди с минимумом. Аналогично очереди с минимумом, будем хранить в стеках не просто элементы, а пары (элемент; массив dpi, в котором содержатся значения ДП для элементов с текущего и ниже). Добавление одного элемента в такой стек можно выполнить за O(2k), удаление за O(1). Окончательно, используя такую модификацию стека в очереди, можно отвечать на запрос типа 3 за O(2k): ответ на него положителен тогда и только тогда, когда maxi = 0..2k-1 dp1i+dp22k-1-i ≥ Z, где dp1, dp2 — массивы значений ДП на вершине первого и второго стека, соответственно.

В заключение, вспоминая, что каждый элемент в результаты работы очереди, реализованной на двух стеках, перемещается O(1) раз, получаем, что решение работает за O(n2k) времени и использует O(n2k) памяти.

Read more »

 
 
 
 
  • Vote: I like it  
  • +78
  • Vote: I do not like it  

By RussianCodeCup, history, 4 years ago, In Russian,

Всем привет!

Чемпионат Russian Code Cup 2015 приближается к финишной прямой. В ближайшее воскресенье 14 июня в 13:00 состоится отборочный тур RCC-2015. В отборочном туре примут участие 604 лучших по итогам трех квалификационных раундов — борьба была такой напряженной, что в первой и третьей квалификациях 200-е место оказалось поделено, и в отборочный раунд прошло по 202 участника.

Обратите внимание, что отборочный тур длиннее квалификационных и продлится 3 часа.

По итогам отборочного раунда 200 лучших раунда получат фирменную футболку наших соревнований, а топ 50 участников пройдут в финальный раунд и получат возможность сразится за ценные призы. Финал состоится 19 сентября и, как и в прошлом году, пройдет онлайн. В соответствии с правилами соревнований в финал могут пройти только те, кому на момент проведения финала исполнится 18 лет.

Приглашаем квалифицировавшихся принять участие в отборочном раунде, а всех остальных поболеть за своих друзей на сайте http://russiancodecup.ru!

Read more »

 
 
 
 
  • Vote: I like it  
  • +33
  • Vote: I do not like it  

By RussianCodeCup, 4 years ago, In Russian,

Задача A. Покупка велосипеда.

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

По условию задачи нужно сказать, можно ли по данным числам a, b, c найти такие числа a1, b1, что a1  ≤  a, b1  ≤  b и a1 + 2 · b1 = c.

Решение у этой задачи простое: почти всегда достаточно проверить, что суммарный номинал наших монет не меньше c: a + 2 · b  ≥  c. Исключение — когда c нечётное. Тогда ещё нужно проверить, что a  ≥  1.

Задача B. Цифровые корни.

Идея: Григорий Шовкопляс.
Реализация: Григорий Шовкопляс.
Разбор: Григорий Шовкопляс.

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

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

Задача C. Две улитки.

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

В этой задаче две улитки днём поднимаются на ai, а ночью опускаются на bi. Требуется определить, сколько по времени первая улитка обгоняла вторую.

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

Задача D. Игровые автоматы.

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

Нам даны кнопки, которые умеют выключать какой-то набор из лампочек, и кнопки, которые умеют включать какой-то набор лампочек. Задача: с помощью кнопок перевести лампочки из выключенного состояния в заданнное, или сообщить, что такое сделать нельзя.

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

Мы могли нажимать кнопку, если:

  • кнопка выключает лампочки, то состояния изменённых лампочек должны быть или выключены, или неизвестны;
  • кнопка включает лампочки, то состояния изменённых лампочек должны быть или включены, или неизвестны.

Смотрим на последнее состояние, и нажимаем кнопки, каждую по одному разу, если это возможно. Пусть ни одну кнопку нажать нельзя, то нужно проверить, правда ли лампочки или выключены, или неизвестны, что соответствует стартовому состоянию. Если правда, мы можем последовательностью нажатий перейти в заданное состояние, иначе — нельзя.

Задача E. Интернетопровод.

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

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

Любая прямая задается тройкой коэффициентов a, b и c таких, что ax+by+c=0. Две прямые (a1, b1, c1) и (a2, b2, c2) параллельны, если коллинеарны векторы (a1, b1) и (a2, b2).

Проведем прямые через все пары точек, и приведем их к нормальному виду: GCD(a, b)=1, и a>0 или a=0 и b>0. Такое представление единственно для любой прямой. Перебрав все прямые, проходящие через пару точек, мы получим все углы, под которыми есть смысл проводить прямую-ответ (в случае, когда ответ больше двух, какие-то две точки из ответа будут лежать на одной прямой). Зная угол, под которым проходит прямая-ответ, несложно указать оптимальное d: для фиксированных a, b, задающих угол наклона прямой, нужно выбрать два самых часто встречаемых с этими значениями a, b значения c, и мы получим две прямые, параллельные искомой, находящиеся от нее на расстоянии d. В случае, если такое значение c всего одно, то, если не все точки лежат на одной прямой, можно добавить к ответу еще одну точку.

Read more »

 
 
 
 
  • Vote: I like it  
  • +21
  • Vote: I do not like it  

By RussianCodeCup, 4 years ago, In Russian,

Всем привет!

В это воскресенье 31 мая в 13:00 по Москве состоится третий квалификационный раунд Russian Code Cup. Раунд продлится 2 часа. По итогам раунда 200 лучших выйдут в отборочный раунд, где сразятся за выход в финал.

Третий раунд — последний шанс для тех, кто еще не успел пройти квалификацию, так что не пропустите! Отборочный раунд состоится в 13:00 14 июня, в него проходят 200 лучших участников из каждого квалификационного раунда.

Для того чтобы принять участие в Russian Code Cup, нужно зарегистрироваться на сайте http://russiancodecup.ru/ (регистрация будет открыта до начала третьего квалификационного раунда).

Подробнее о чемпионате, правилах и призах и читайте на сайте http://russiancodecup.ru, по всем вопросам обращайтесь на russiancodecup@corp.mail.ru

Приглашаем всех принять участие в квалификационном раунде Russian Code Cup и желаем всем удачи!

Read more »

 
 
 
 
  • Vote: I like it  
  • +65
  • Vote: I do not like it  

By RussianCodeCup, 4 years ago, In Russian,

Analysis QR2 RCC 2015

Задача A. Турникеты в метро.

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

По условию задачи нужно найти момент времени, когда числа, отображаемые на турникете у двух мальчиков, будут отличаться в k раз. В первую очередь разберём случай k=1, в этом случае ответ — YES, если на обоих турникетах показывается 99 или если a = b. Иначе, несложно заметить, что правильный момент времени наступит не раньше, чем у какого-то мальчика количество поездок станет меньше 99. Перейдём сразу к первому такого моменту. У нас осталось всего не более 99 вариантов подходящих дней. Переберём и проверим каждый из них на то, что он удовлетворяет условию задачи.

Задача В. Игра.

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

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

В dp[i][j] будет хранить математическое ожидание длины пути, если мы начнем на i-м этаже в j-ой комнате и пойдём до последнего уровня. Тогда ответ на нашу задачу будет хранится в dp[1][1].

Будет решать задачу с последнего уровня до первого. Понятно, что dp[n + 1][x] = 0, где x от 1 до n + 1. Теперь зная ответ для (k + 1)-го уровня, посчитаем значение динамики для k.

  • Если a[k][j][0] < a[k][j][1], тогда dp[k][j] = dp[k &plus; 1][j] + a[k][j][0]. Где a[k][j][0] —  длина коридора с k-го уровня j-ой комнаты в j-ую комната на (k &plus; 1)-ом уровне. А a[k][j][1] —  длина коридора с k-го уровня j-ой комнаты в (j &plus; 1)-ую комната на (k &plus; 1)-ом уровне.
  • Если a[k][j][0] > a[k][j][1], тогда dp[k][j] = dp[k &plus; 1][j &plus; 1] + a[k][j][1].
  • Если a[k][j][0] = a[k][j][1], тогда dp[k][j] = (dp[k &plus; 1][j] + dp[k &plus; 1][j &plus; 1]) / 2 + a[k][j][0]. Так как мы могли равно вероятно пойти как по первому коридору, так и по второму с равной вероятностью.


После подсчёта ответ на задачу будет храниться в dp[1][1].

Задача С. Палочки и Шарниры.

Идея: Георгий Корнеев.
Реализация: Григорий Шовкопляс.
Разбор: Григорий Шовкопляс.

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

Рассмотрим решение с помощью двоичного поиска по ответу. Очевидно, что если цепочка помещается в окружность, то она поместится и в окружность большего радиуса.

Теперь надо научиться проверять, что окружность может вместить в себя цепочку. Идея проста: наберем максимальное количество палочек, такое что их суммарная длина меньше либо равна радиусу окружности. Если больше палочек нет, то задача решена. Иначе, смотрим, можем ли поместить следующую: если ее длина минус сумма предыдущих больше радиуса (развернули ее в шарнире на 180 градусов, и она вышла за пределы окружности), значит, уместить цепочку в эту окружность нельзя, иначе — на окружности найдется точка, на которую можно положить следующий шарнир, а значит, эта палочка поместится. Теперь проверяем, что длина оставшихся палочек меньше диаметра окружности, что равносильно тому, что мы можем разложить все оставшиеся шарниры на окружность, и цепочка поместится в окружность.

Задача D. Числа Фибоначчи.

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

По условию задачи нужно найти сумму k-ых степеней первых n чисел Фибоначчи по модулю 109+23. Самое первое действие заключалось в разложении модуля на множители: 109+23 = 3·112·61·45161. Давайте посчитаем нужную сумму по каждому из этих модулей и восстановим по Китайской Теореме об Остатках ответ на задачу.

Для каждого модуля по отдельности задача решается следующим образом. Найдём период чисел Фибоначчи. Для наших модулей они получаются небольшими, и предпериод всегда равен 0. Посчитаем сумму k-ых степеней чисел Фибоначчи на данном периоде и ещё небольшом кусочке. Тогда ответ на задачу при фиксированном n будет равен сумме нескольких периодов и сумма на маленьком кусочке.

Получив ответ для каждой из меньших задач, восстанавливаем ответ для начальной задачи.

К сожалению, на данном этапе задача не заканчивалась. Нужно придумать любую оптимизацию для того, чтобы программа прошла по времени. Можно было применить следующие: избавиться от двойного взятия по модулю при быстром возведении в степень, предварительно предподсчитав числа в степенях степени двойки, либо возводить не в степень k, а воспользоваться теоремой Эйлера и возводить в степень по модулю φ.

Задача E. Телепорты.

Идея: Илья Збань.
Реализация: Илья Збань.
Разбор: Илья Збань.

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

Заметим, что два отражения подряд относительно точек i, j прибавят к координате текущей точки вектор f(i, j) = (2(xjxi), 2(yjyi)). Если мы знаем, что в ответе четное число отражений, то задачу можно свести к следующей: можно ли представить вектор (xfxs, yfys) суммой векторов f(i, j). Случай с нечетным числом векторов в ответе сводится к задаче с четным числом, если первым действием отразить стартовую точку относительно любого телепорта (может показаться, что нужно перебрать все n вариантов первого хода, но на самом деле это не обязательно) и попытаться решить задачу с четным числом векторов в ответе.

Заметим, что не нужно использовать все n2 векторов f(i, j): f(i, j) = f(1, j) — f(1, i). Итак, у нас в рассмотрении остался всего n-1 вектор. Утверждается, что целочисленную линейную оболочку целочисленных векторов можно представить как целочисленную линейную оболочку всего двух некоторых векторов, т.е. эта оболочка — некоторая сетка на плоскости.

Будем добавлять в рассмотренное множество векторы по одному и поддерживать два вектора, задающие линейную комбинацию всех уже добавленных. Один вектор будет иметь вид v1 = (x1, 0), где x1 — минимально возможное положительное, а второй — v2 = (x2, y2), где y2 — минимально возможное положительное, и 0 ≤ x2 < x1.

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

Чтобы найти новый вектор v1, надо посмотреть на GCD двух векторов: старого v1, и вектора с минимальным x вида (x, 0), представимого линейной комбинацией векторов v2 и v3. Для этого нужно найти минимальное решение уравнения k2 · y2 + k3 · y3 = 0.

Чтобы найти новый вектор v2, надо рассмотреть вектор вида k2 · v2 + k3 · v3. Нужно найти любое решение уравнения k2 · y2 + k3 · y3 = GCD(y2, y3), и прибавить несколько раз новый v1, чтобы гарантировать минимальность по х-координате.

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +22
  • Vote: I do not like it  

By RussianCodeCup, 4 years ago, In Russian,

Всем привет!

Уже в эту субботу состоится второй квалификационный раунд Russian Code Cup. На этот раз раунд будет в первой половине дня — он состоится 25 апреля в 12:00 по Москве. Раунд продлится 2 часа. По итогам раунда 200 лучших выйдут в отборочный раунд, где сразятся за выход в финал.

Те, кто после второго квалификационного раунда все еще не пройдут в отборочный раунд, смогут попробовать свои силы в третьем квалификационном раунде 31 мая в 13:00. В отборочный раунд, назначенный на 13:00 14 июня, пройдут 200 лучших участников из каждого квалификационного раунда.

Для того чтобы принять участие в Russian Code Cup, нужно зарегистрироваться на сайте http://russiancodecup.ru/ (регистрация будет открыта до начала третьего квалификационного раунда).

Подробнее о чемпионате, правилах и призах и читайте на сайте http://russiancodecup.ru, по всем вопросам обращайтесь на russiancodecup@corp.mail.ru

Приглашаем всех принять участие в квалификационном раунде Russian Code Cup и желаем всем удачи!

Read more »

 
 
 
 
  • Vote: I like it  
  • +30
  • Vote: I do not like it  

By RussianCodeCup, 4 years ago, In Russian,

Всем привет!

мы прислушались к мнению сообщества и решили, помимо онлайн-сертификатов для всех прошедших квалификацию, подарить футболки лучшим 200 участникам отборочного раунда.

Напоминаем, что зарегистрироваться и принять участие в Russian Code Cup вы можете на сайте russiancodecup.ru до начала третьего квалификационного раунда.

Второй квалификационный раунд состоится в субботу 25 апреля в 12:00. Раунд продлится 2 часа. По итогам раунда 200 лучших выйдут в отборочный раунд, где сразятся за выход в финал.

Подробнее о чемпионате, правилах и призах и читайте на сайте http://russiancodecup.ru, по всем вопросам обращайтесь на russiancodecup@corp.mail.ru

Read more »

 
 
 
 
  • Vote: I like it  
  • +386
  • Vote: I do not like it  

By RussianCodeCup, 4 years ago, In Russian,

Всем привет!

Мы рады представить вашему вниманию разбор задач первого квалификационного раунда Russian Code Cup и заодно напомнить, что тем, кто не смог пройти квалификацию с первого раза, стоит принять участие во втором квалификационном раунде, который состоится 25 апреля в 12-00 по московскому времени.

Задача A. Магические карточки.

Идея: Виталий Аксёнов.
Реализация: Григорий Шовкопляс.
Разбор: Григорий Шовкопляс.

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

Рассмотрим случай, когда у Гриши будут выбраны l минимальных карточек, а у Димы l максимальных. Очевидно, что если в этом случае Гриша выиграет, то он выиграет в любом другом, так как если заменить среди выбранных любую карточку на другую из набора данного игрока, то сумма у Димы не увеличится, а у Гриши не уменьшится.

Таким образом, чтобы решить задачу, нужно просто отсортировать карточки Гриши по возрастанию, а Димы по убыванию. После чего найти суммы первых l чисел в обоих наборах и сравнить их. Если сумма Гриши больше, то он выиграет любой раунд, иначе – нет.

Задача B. Домашнее задание.

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

В задаче дано три числа x, y, z, записанных в десятичной системе счисления, надо проверить, верно ли, что xk · yk = zk выполнено для бесконечного количества чисел k (через xk обозначено значение числа x, если считать, что оно записано в k-ичной системе счисления).

Предположим, что таких k существует бесконечно много. Тогда равенство должно быть выполнено для сколь угодно больших k. Возьмем такую систему счисления, в которой при перемножении чисел x и y не будет переноса ни в одном разряде. Если в каком-либо разряде получилось число, больше либо равное 10, то равенство не будет выполнено для данного k, а также для всех систем счисления с большим основанием, так как в них переноса тоже не будет. Значит, чтобы равенство было верно для бесконечного количества чисел k, как минимум, при перемножении без переноса не должно быть разрядов с числами больше 9. Если это выполнено, остается только проверить, что получившееся произведение совпадает с числом z, и если да, то ответ на задачу — «Infinity», иначе — «Finite».

Задача C. Конгресс юных любителей.

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

Данная задача является задачей динамического программирования. Давайте посчитаем следующий массив: d[сколько мест с начала рассадили][какое количество из них философы][количество пар философ-математик сидящие вместе][типы людей на двух последних обработанных местах] — количество способов рассадить математиков и философов, опираясь только на их типы и условия задачи. Данный массив пересчитывается последовательно при добавлении нового места. То есть добавляем нового человека, перебираем какое количество философов сидит до него, перебираем его тип, проверяем, что условия про окружение и тип места выполняются (для этого мы и храним типы людей на двух предыдущих местах), возможно у нас появляется пара философ-математик, сидящие на соседних местах.

Пока мы не использовали, что люди из разных стран. Заметим, что если мы зафиксировали назначение типов, нам для подсчёта по странам нужно только знать, что в позициях философ-математик сидят люди не из одной страны. Также нужно отметить, что количество назначений стран зависит только от количества таких пар в назначении типов. Несложно по массиву d получить массив c, который по количеству пар возвращает количество соответствующих назначений типов.

Пусть pn,k — количество перестановок из n элементов, таких что нет неподвижных точек среди первых k позиций. Тогда несложно убедиться, что ответ будет равен n! Σi = 1n pn,i · ci.

Осталось посчитать p. Воспользуемся идеей для подсчёта перестановок без неподвижных точек, например описанной на wikipedia, и получим реккурентное выражение pn,k = (n-1) pn-1,k-1 + (k-1) pn-2,k-2, а pn,0 = n! и pn,1 = n!(n — 1)!.

Задача D. Расшифровка.

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

Для начало научимся решать задачу без модификаций. Для этого воспользуемся идеей динамического программирования. В dp[i] будет храниться количество способов получить префикс длины i. Тогда переберем следующую исходную цифру x, если зашифрованная цифра соответствует строке с позиции i+1, тогда увеличиваем значение dp[i + len(x)] на dp[i], где len(x) — длина зашифрованной цифры x.

Теперь будем решать задачу с изменениями. Заметим, что при заданных ограничениях на коэффициенты трехчлена, одна цифра может превратиться в число, состоящее не более чем из трех цифр. Тогда для решения данной задачи воспользуемся деревом отрезков. В вершине, которая отвечает за отрезок от l до r, будем хранить 9 значений, количества способов получить подстроку c l + 0…2 позиции дo r − 0…2 позиции. Как построить такое дерево?

  • Если отрезок с l по r небольшой, то посчитаем значения с помощью динамического программирования.
  • Если отрезок большой, то разобьем его на два и посчитаем соответствующие значения для них рекурсивно. Теперь осталось научиться считать значение в узле, если мы знаем значения в детях. Во-первых, когда правый и левый подотрезок соприкасаются, то это значение на их объединении равно произведению значений на них. Если же между ними есть расстояние, то есть от правого подотрезка берется значение без одного или двух символов слева, а от левого подотрезка берем значение без одного или двух символов справа, то ответ будет равен количеству способов получить одно число между ними, умножить на значение на правом подотрезке, и на значение на левом подотрезке.
Ответ на всем отрезке будет лежать в корне дерева отрезков.

Тогда, когда мы модифицируем одну цифру, мы обновляем значение в листе, а затем обновляем значения поднимаясь вверх. Так как глубина дерева отрезков есть O(log (n)), где n — длина строки, то итоговое время работы O(m log (n)), где m — общее число запросов.

Задача E. Занимательная криптография.

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

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

Наивное решение использует идею динамического программирования dpi,j — количество строк длины i, имеющих хеш j. Переходы можно делать за Σ, и решение получается за n·m·Σ.

Это решение можно ускорить до m2 · log n, если использовать технику двоичных подъемов: dpi,j  – число строк длины 2i, имеющих хеш j. dpi,j = Σ(x=0..m-1) dpi-1,x·p2i-1 % m · dpi-1,j-x. Используя значения этой динамики, можно посмотреть разложение n по степеням двойки, и получить ответ на задачу.

Последнее ускорение заключается в том, что в формуле перехода предыдущей динамики можно увидеть не что иное, как произведение двух многочленов. Если использовать для этого быстрое преобразование Фурье, получаем асимптотику m · log m · log n. Это и будет полным решением.

Read more »

 
 
 
 
  • Vote: I like it  
  • +46
  • Vote: I do not like it  

By RussianCodeCup, 4 years ago, In Russian,

Всем привет!

Уже в эту субботу, 28 марта в 18:00 состоится первый квалификационный раунд Russian Code Cup 2015. Раунд продлится 2 часа. По итогам раунда 200 лучших выйдут в отборочный раунд, где сразятся за выход в финал.

Те, кому удача в субботу не улыбнется, а также те, кто по тем или иным причинам не смогут принять участие в раунде, смогут попробовать свои силы во втором отборочном раунде 25 апреля в 12:00, а при необходимости и в третьем – 31 мая в 13:00. В отборочный тур, назначенный на 13:00 14 июня, пройдут 200 лучших участников из каждого квалификационного раунда.

Для того чтобы принять участие в Russian Code Cup, нужно зарегистрироваться на сайте http://russiancodecup.ru/ (регистрация будет открыта до начала третьего квалификационного раунда).

Подробнее о чемпионате, правилах и призах и читайте на сайте http://russiancodecup.ru, по всем вопросам обращайтесь на russiancodecup@corp.mail.ru

Приглашаем всех принять участие в квалификационном раунде Russian Code Cup и желаем всем удачи!

Read more »

 
 
 
 
  • Vote: I like it  
  • -42
  • Vote: I do not like it  

By RussianCodeCup, 4 years ago, In Russian,

Всем привет!

Идет регистрация на крупнейшую в России открытую ежегодную олимпиаду по спортивному программированию Russian Code Cup 2015. Первый квалификационный тур состоится уже в субботу, 28 марта, в 18-00 и продлится 2 часа.

Russian Code Cup – это возможность для русскоязычных программистов со всего мира проверить свои силы и продемонстрировать мастерство, решая оригинальные задачи различной сложности, а также заявить о себе экспертному IT-сообществу. Олимпиада проходит в три этапа: квалификационные раунды, отборочный тур и финал, на каждом из которых участникам олимпиады предлагается от четырех до восьми разноплановых задач. Задания и техническую часть соревнования обеспечивают специалисты Mail.Ru Group и эксперты Университета ИТМО – соорганизатора Russian Code Cup.

Квалификационные и отборочный раунды пройдут на сайте Russian Code Cup. Первый квалификационный раунд состоится 28 марта в 18:00, второй – 25 апреля в 12:00, третий – 31 мая в 13:00. Причем программисты, не прошедшие квалификацию с первого или второго раза, могут попробовать свои силы в следующих раундах. В отборочный тур, назначенный на 13:00 14 июня, пройдут 200 лучших участников из каждого квалификационного раунда. А 50 программистов, преодолевших «сито» отбора, померятся силами в финале, который состоится в 19 сентября 2015 года. Форма и время проведения финала будут объявлены после 1 июня. Победитель Russian Code Cup получит главный приз – 300 тысяч рублей; участник, занявший второе место, — 150 тысяч рублей; приз за третье место – 90 тысяч рублей, обладатели 4-10 места получат по 30 тысяч рублей. Кроме того, призы достанутся всем участникам, дошедшим до финала.

Для того чтобы принять участие в Russian Code Cup, нужно зарегистрироваться на сайте http://russiancodecup.ru/ (регистрация будет открыта до начала третьего квалификационного раунда).

Подробнее о чемпионате, правилах и призах и читайте на сайте http://russiancodecup.ru, по всем вопросам обращайтесь на russiancodecup@corp.mail.ru

Приглашаем всех русскоязычных участников сообщества Codeforces принять участие в Russian Code Cup 2015 и хотим со своей стороны поздравить Codeforces с 5-летием! Мы воспользовались возможностью поддержать Codeforces переводом в $1000. Нам приятно внести свой вклад в будущее платформы. Желаем Codeforces новых рекордов и достижений!

Read more »

 
 
 
 
  • Vote: I like it  
  • +51
  • Vote: I do not like it