Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

By andrewzta, 5 years ago, In Russian,

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

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

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

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

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

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

  • Геннадий Короткевич tourist
  • Павел Маврин pashka
  • Нияз Нигматуллин niyaznigmatul
  • Владимир Смыкалов enot.1.10
  • Дмитрий Филиппов 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).

Read more »

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

By andrewzta, 5 years ago, In Russian,

Всем привет!

Итак, четыре квалификации позади и приближается основное событие отборочного цикла Russian Code Cup 2014 — отборочный раунд. 802 участника сразятся за право войти в 50 лучших, которые будут приглашены в Москву в начале октября для участия в финальном раунде RCC-2014.

Отборочный раунд начнется в 14-00 по московскому времени в воскресенье, 8 июня, и продлится 3 часа.

Раунд завершен, поздравляем финалистов!

Read more »

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

By andrewzta, 5 years ago, In Russian,

Задача А. Соцопрос.

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

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

Так как по условию задачи задачу решат только те, кому она не противна и умеют решать, то максимум, кто попытается решить задачу будет nb. То есть если среди всех кто попытается решить задачу, будут те кто умеет, то это будет максимум кто решит, а это min(a, nb).

Минимум же достигается, если все кому противна задача, будут уметь решать задачу, тогда ответ max(0, ab)

Задача B. Сто.

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

Решением задачи является программа, аккуратно рассматривающая несколько несложных случаев. Самым простым случаем является ситуация, когда количество цифр в числе x равно k+1. В этом случае необходимо вывести −1, если число не содержит ни одного нуля, и ноль — если хотя бы один ноль в числе присутствует.

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

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

Задача C. Поход в гости.

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

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

Задача D. СНМ.

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

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

Хоть массив rank и не задавался во входных данных, легко понять, что без сжатия путей, ranki это высота поддерева с вершиной i в корне. Также отметим, алгоритм устроен так, что ranki каждый раз увеличивается не более, чем на единицу, а после того, как вершина подвешивается к другой, ее parent и rank не изменяются, поэтому можно строить от листьев к корню.

Рассмотрим поддерево с корнем в вершине u. Если ranku = r, то у вершины u должны существовать дети с рангом 0, 1, ..., r-1. Легко показать, что это условие является также достаточным: если провести операции union в порядке увеличения ранга сына, все операции пройдут корректно.

Отсюда следует решение для одного дерева:

  • Рекурсивно построим решение для всех детей корня дерева.
  • Проверим, что для всех h от 0 до rankroot — 1 существует сын с рангом h.
  • Проделаем операции union(root, childi) в порядке увеличения ранга childi.
Также возможно реализовать СНМ и непосредственно проделать все операции, проверив, что получившийся массив parent совпал с нужным.

Время работы решения — O(n log (n)).

Задача E. Нанороботы.

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

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

Будем решать эту задачу при помощи динамического программирования. Обозначим за dp[w][x][y] минимальное число шагов, за которое можно довести робота массой w из клетки (x, y) до финальной клетки (n, m). Начальные значения dp[w][n][m] = 0 говорят о том, что из целевой клетки идти никуда не надо. После того, как dp будет посчитано, ответ будет содержаться в ячейке dp[w][1][1].

Научимся считать dp. Чтобы посчитать dp[w][i][j], сделаем одно из двух:

  • Дойдём до финиша, не разбивая робота на части. Для этого, с помощью обхода в глубину, найдём кратчайший путь до финиша по выдерживающим клеткам.
  • Либо, дойдём до какой-то клетки, разобъёмся на две части и дойдём ими оттуда.
Чтобы не было проблем с пониманием того, в каком порядке считать значения динамики, можно считать её лениво. Итоговая сложность алгоритма: O(w2n2m2).

Read more »

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

By andrewzta, 5 years ago, In Russian,

Всем привет!

Все помнят, что исходно в RCC-2014 планировалось только 3 квалификационных раунда, но из-за ряда технических трудностей при проведении первой квалификации было решено провести четвертый раунд.

Поэтому в ближайшее воскресенье, 1 июня 2014 года, в 13-00 по московскому времени, состоится четвертый квалификационный раунд Russian Code Cup 2014.

Зарегистрироваться и участвовать можно на сайте http://russiancodecup.ru

Участвовать могут все, кроме тех участников, которые уже квалифицировались в первом, втором или третьем раундах.

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

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

Раунд завершен. Поздравляю всех квалифицировавшихся!

Read more »

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

By andrewzta, 5 years ago, In Russian,

Задача А. Треугольники.

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

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

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

Рассмотрим отрезки a, b, c в порядке возрастания длины, тогда если выполнено равенство c2 = a2 + b2, то треугольник является прямоугольным, если c2 < a2 + b2 остроугольным, и если c2 > a2 + b2— тупоугольным

Задача B. Оригами.

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

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

Для этого переберём все такие x — делители числа S, и проверим, что xa и Sxb. Если существует хотя бы одна такая пара x и Sx, удолетворяющим ограничениям, то решение существует.

Время работы на один тестовый случай O(sqrt(S)).

Задача C. Митя и граф.

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

Первое наблюдение заключается в следующем: граф должен быть рёберным кактусом. Если он не получился таковым, то обязательно найдётся чётный цикл. Раз это кактус, то количество циклов равно m — (n — 1). А так как каждый цикл содержит в себе минимум 3 вершины, то 3·(m-(n — 1)) ≤ m. Отсюда получаем, что максимальное число рёбер равно 3·(n — 1) / 2.

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

Задача D. Призы.

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

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

  • В начале, в первой группе дети получают n конфет, во второй — n-1 конфет, ..., в последней — 1 конфету.
  • Далее мы можем прибавлять по одной конфете всем детям на префиксе групп. Это значит, что мы можем выбрать число p и увеличить ai на единицу для любого i ≤ p.

Так как мы выбрали изначальное распределение, то из общего числа конфет можно сразу вычесть n·a1+...+1·an. Несложно заметить, что операция распределения вычитает bp = a1+...+ap. Итого, нам надо проверить, можем ли мы представить d в виде какой-то суммы b1, ..., bn, а это стандартная задача о рюкзаке.

Время работы O(nd).

Задача Е. Криптостойкие ключи

Идея: Виталий Демьянюк.
Реализация: Виталий Демьянюк.
Разбор: Виталий Демьянюк.

Дано множество чисел a1, a2, ..., an. Его замкнули относительно операций НОД и НОК. Требуется выяснить, принадлежит ли заданное число v замкнутому множеству S.

Представим v в виде p1q1p2q2... pkqk, q i > 0 , где p1, p2, ..., pk — простые числа. Чтобы v принадлежало S необходимо чтобы для каждого i, 1 ≤  i ≤  k существовало j, 1 ≤  j ≤  n, такое что piqiaj и piqi+1aj . Этот факт следует из того, что мы можем любое число представить в виде НОК(НОД(...), НОД(...), ..., НОД(...)), так как min(a, max(b, c)) = max(min(a, b), min(a, c)) и max(a, min(b, c)) = min(max(a, b), max(a, c)). Положим ci равным наибольшему общему делителю чисел aj, таких что piqiaj . Если все ci делят v, то v принадлежит S. Оно может быть получено как наименьшее общее кратное всех ci. В противном случае v не принадлежит S(это следует из свойств операций НОД и НОК).

Время работы O(nk + sqrt(v) ), где k — количество простых делителей числа v.

Read more »

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

By andrewzta, 5 years ago, In Russian,

Всем привет!

В ближайшую субботу, 24 мая 2014 года, в 19-00 по московскому времени, состоится третий квалификационный раунд Russian Code Cup 2014.

Зарегистрироваться и участвовать можно на сайте http://russiancodecup.ru

Участвовать могут все, кроме 401 участника, которые уже квалифицировались в первом и втором раундах.

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

И немного приятных новостей: мы обновили версии компиляторов почти всех языков, добавили возможность отправлять на C++11 под GNU C++ (а Visual C++ 2013 и так поддерживает C++11) и добавили Java 8 (Java 7 тоже пока остается). Актуальные версии компиляторов и строки компиляции на странице с правилами чемпионата http://www.russiancodecup.ru/rules

Всем удачи!

[UPD] Всем спасибо за участие, раунд завершен. У нас снова 201 прошедший, поздравляем! Разбор будет опубликован в ближайшее время.

Read more »

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

By Aksenov239, 5 years ago, In Russian,

Задача A. Командная олимпиада.

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

Самое логичное в задаче сразу перебрать количество задач первого типа, которые решил Вася. Пусть он решил vn задач первого типа, тогда очевидно, что максимальное количество задач второго типа vm, которое мог решить Вася за олимпиаду, равно (n-vn·p)/q. Итого, у нас осталось n-vn задач первого типа и m — vm задач второго. Нужно не забыть сравнить эти количество с нулём.

Посчитаем, какое максимальное число задач первого типа и второго типа можно решить за олимпиаду. Первого типа получается maxn=t/p, а второго типа — maxm=t/q. Благодаря подсчитанным значениям, несложно уже посчитать ответ: 1 + (n — vn + maxn — 1) / maxn + (m — vm + maxm — 1) / maxm.

Задача B. Три ладьи.

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

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

Либо можно рассмотреть все различные варианты взаимных расстановок 3 ладей:

  • (1, 1), (2, 2), (3, 3). Бьют 3 · n + 3 · m — 12 клеток.
  • (1, 1), (1, 2), (2, 3). Бьют 2 · m + 3 · n — 9 клеток.
  • (1, 1), (2, 1), (3, 2). Бьют 3 · m + 2 · n — 9 клеток.
  • (1, 1), (1, 2), (2, 1). Бьют 2 · n + 2 · m — 7 клеток.
  • (1, 1), (1, 2), (1, 3). Бьют m + 3 · n — 6 клеток.
  • (1, 1), (2, 1), (3, 1). Бьют n + 3 · m- 6 клеток.
Во всех других случаях нужно выводить «IMPOSSIBLE».

Задача C. Король и королева.

Идея: Виталий Демьянюк.
Реализация: Павел Кротков.
Разбор: Павел Кротков.

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

Пусть королева стоит в клетке с координатами (x, y), строки и столбцы нумеруются с нуля, и мы хотим научиться находить размер региона, расположенного левее вертикали, на которой расположен ферзь, и выше диагонального луча, выпущенного налево вверх из клетки, в которой стоит королева. Заметим, что в случае, если этот луч упирается в верхний край доски (xy) , то ответом будет являться сумма всех чисел от одного до x — 1. В противном же случае из этой величины необходимо вычесть количество клеток, которые были бы биты королевой, если бы не край доски. Количество таких клеток равно сумме всех чисел от одного до x-y-1.

Задача D. Дерево.

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

Дано дерево, которое нужно получить из одной вершины двумя операциями: отрезать ребро и добавить 2 вершины к листу. Чтобы решить данную задачу первым делом проверим, есть ли вершина степени не менее 4. Если она есть, то дерево получить нельзя.

В любом другом случае дерево построить можно. Для этого посчитаем количество вершин v2 степени 2 и v3 степени 3. Если есть вершина степени 2, то при выборе её начальной мы построим дерево за (v2 — 1)·2+(v3 + 1), иначе число действий равно (v2 + 1)·2+v3. Это верно потому что для получения внутренней вершину степени 3, нужно применить одну операцию второго типа, а для получения внутренней вершины степени 2 нужно применить 2 операции.

Задача E. Налог на проезд.

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

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

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

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

Теперь нам необходимо решить некоторую модификацию задачи о рюкзаке. Она решается методом динамического программирования. Будем рассматривать все дороги по очереди. Также будем поддерживать количество способов собрать некоторую сумму денег, используя только некоторый префикс дорог. Рассмотрим более подробно, как обрабатывать очередную дорогу. Пусть увеличение налога на проезд по этой дороге добавляет c денежных единиц в общую прибыль, а цена за проезд по дороге может находится в пределах от 0 до max. Как узнать, сколько существует способов получить суммарный доход ровно m? На самом деле это количество совпадает с количеством способов получить суммарную прибыль mc за исключением двух слагаемых. Эти слагаемые соответствует тому, что мы можем назначить стоимость проезда равную 0, но не можем max + 1. То есть каждое значение динамического программирования можно посчитать с помощью трех уже посчитанных значений. Таким образом, очередную дорогу можно обработать за O(MAX), где MAX — прибыль, которую хочет получить президент.

Read more »

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

By andrewzta, 5 years ago, In Russian,

Всем привет!

В ближайшее воскресенье, 18 мая 2014 года, в 14-00 по московскому времени, состоится второй квалификационный раунд Russian Code Cup 2014.

Зарегистрироваться и участвовать можно на сайте http://russiancodecup.ru

Участвовать могут все, кроме 200 лучших (на самом деле 201, поскольку 200-е место было поделено) в первом квалификационном раунде.

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

Всем удачи!

Read more »

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

By Aksenov239, 5 years ago, In Russian,

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

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

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

Решением задачи является проверка всех клеток игрового поля и пар соседних клеток игрового поля, удолетворяют ли они указанным выше условиям. Итоговая сложность: O(n2).

Задача B. Таймер.

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

В задаче нужно найти максимальное возможное число, которое может получиться на таймере после t секунд, если разрешено не более k раз заменить число на таймере на наименьшее число, не меньшее x и делящееся на y.

В заданных ограничениях всегда возможно получить число, которое делится на y. Рассмотрим первый момент, когда такое число появилось на таймере. Можно показать, что это число будет наименьшим среди чисел, не меньших x и делящихся на y. Обозначим его за z.

Существует не более двух различных оптимальных способов получить z на таймере. Первый из способов это использовать уязвимость до первого тика таймера. В таком случае мы тратим одно использование уязвимости и ноль секунд. Второй способ — не тратить использование уязвимости и подождать необходимое количество секунд. Этот способ возможен только тогда, когда z-xt и затрачивает z-x секунд и ноль использований уязвимости. Обозначим время после получения z за to, а оставшееся количество использований за ko.

После того, как на таймере появилось z, действия Пети становятся однозначными. Нам выгодно использовать как можно больше уязвимостей, потому что они прибавляют дополнительно y-1 секунд. Отсюда ответ равен z + min(to, ko) · (y-1) + to.

Осталось проверить оба способа получить число z, вычислить ответ для получившихся to и ko и выбрать максимальный из них. Время работы решения — O(1) на один тестовый пример.

Задача C. Обратная задача о наибольшей возрастающей подпоследовательности.

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

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

Данную задачу можно решить конструктивно. Например так d[i] = a[i] · ni + 1, где n — длина последовательности. Докажем, что это последовательность подходит.

i < j для которых d[i] < d[j] будет выполнено: (d[j] — d[i]) · nn, а (ji) < na[i] < a[j]. Аналогично в другую сторону.

i < j для которых d[i] = d[j] будет выполнено: a[i] > a[j].

Кроме того, существует решение, использующее алгоритм топологической сортировки.

Задача D. Трехцветные шахматы.

Идея: Виталий Демьянюк.
Реализация: Виталий Демьянюк.
Разбор: Виталий Демьянюк.

В задаче требовалось подсчитать количество способов покрасить каждую не покрашеную клетку доски n × m в три цвета так, чтобы никакие две соседние клетки не были покрашены в одинаковый цвет.

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

Занумеруем все цвета. Каждому состоянию соответствует четверка чисел (x, y, c, mask), где (x,y) – координаты клетки в которой начинается излом профиля. Рассмотрим все клетки профиля в порядке обхода сверху вниз. Тогда c – цвет первой клетки профиля. Рассмотрим i-тую клетку профиля и множество цветов в которые она не покрашена. Это множество состоит из двух цветов. Тогда i-тый бит mask равен 0, если цвет i+1 клетки профиля равен минимуму этого множества, 1 – если максимуму.

В каждом состоянии будем хранить количество способов покрасить соответствующую часть доски. Пересчет значений такой же как и в любой другой задаче динамического программирования по изломанному профилю. Для получения ответа переберем все c и mask и просуммируем значение в состояниях (n, m, c, mask).

Время работы — O(nm2n).

Задача Е. Как проложить сеть.

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

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

Для начала рассмотрим более легкую задачу. Пусть компьютеры и коммутаторы расположены на прямой. Назовем балансом разность между количеством компьютеров, которые мы рассмотрели, и количеством подсоединений к коммутаторам, которые использовали. Для каждого баланса от -n до n будем хранить наименьшую стоимость его достижения. Стоимость достижения баланса нужно определить таким образом, чтобы при балансе 0 его стоимость совпадала со стоимостью прокладки всей сети. Например, это можно сделать следующим образом: eсли после добавления очередного устройства модуль баланса увеличился, то из его стоимости вычитается расстояния до устройства, иначе добавляется. Теперь воспользуемся методом динамического программирования. Будем рассматривать устройства слева направо. Если текущее устройство — компьютер, то баланс нужно обязательно увеличить на один и соответствующим образом изменить его стоимость. Если же мы рассмотриваем коммутатор, то необходимо перебрать, сколько компьютеров будет к нему подключено, и аккуратно пересчитать стоимость баланса (возможно, первые несколько подключений будут его увеличивать, а следующие — уменьшать). Такое решение работает за O(n2·(n+m)).

Рассмотрим способ, который позволяет уменьшить время работы алгоритма до O(n·(n+m)). Самое долгоработающее место алгоритма — обновление значений динамического программирования при обработке коммутатора. Будем находить стоимость получения балансов от меньших к большим. При этом будем поддержить очередь, в которой хранятся стоимости получения нужного баланса из различных предыдущих состояний балансов. При переходе к новому значению баланса нужно, возможно, удалить из очереди первый элемент (если к текущемему коммутатору нельзя поключить нужное количество компьютеров), добавить возможность получить текущий баланс не использовав коммутатор совсем, а также изменить все текущие стоимости, которые есть в очереди — для этого нужно прибавить (или отнять) расстояние до коммутатора. В очереди всегда должна хранится возрастающая последовательность стоимостей. Тогда ответ для текущего баланса всегда будет находится на первом месте очереди.

Теперь вернемся к задаче на круге. Разрежем круг и зафиксируем количество проводов, которые проходят через разрез. Можно легко показать, что если существует оптимальный ответ, в котором ровно столько проводов проходят через разрез, то существует оптимальный ответ, в котором эти провода подключены к первым устройствам соответствующего типа. Таким образом мы получили решение на круге за O(n2·(n+m)).

Read more »

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

By andrewzta, 5 years ago, In Russian,

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

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

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

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

2) В воскресенье, 1 июня 2014 года в 13-00 будет проведен еще один, четвертый квалификационный раунд. 200 лучших участников четвертого раунда также выйдут в отборочный раунд и получат футболку, таким образом в отборочном раунде примут участие 800 участников, а не 600, как было исходно заявлено.

Мы понимаем, что решение спорное и в нем есть свои минусы, но надеемся на ваше понимание. Со своей стороны мы предпримем все возможные усилия, чтобы дальшнейшие раунды прошли без накладок и 50 сильнейших вышли в финал и сразились за звание чемпиона Russian Code Cup 2014.

Read more »

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

By andrewzta, 5 years ago, In Russian,

Всем привет!

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

Зарегистрироваться и участвовать можно на сайте http://russiancodecup.ru

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

Всем удачи!

UPD: Принятое решение по итогам раунда

Тесты к прошедшему раунду: скачать тесты

Read more »

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

By Aksenov239, 5 years ago, translation, In English,

I want to say thanks to whom can help me to make this round: for testing pashka and cerealguy, for problems chavit and enot.1.10 and andrewzta for supervising.

417A - Elimination. Author and realization Aksenov239.

The first thing, that you need to mention, is that if k ≤ n·m, then the answer is equal to 0. After that you need to take at least n·m - k people. There's three possibilities to do that:

  • To consider only main rounds: .
  • To take additional rounds to the number, which is divisible by n: .
  • To take only rounds of the second type: d(n·m - k).

Also in this problem it is possible to write the solution, which check every possible combinations of the numbers of main and elimination rounds.

Solution: 6396283

417B - Crash. Author and realization Aksenov239.

Let us create array a with 105 elements, which is filled with  - 1. In the cell a[k] we will contain the maximal number of the submissions of the participant with identifier k. We will process submissions in the given order. Let us process submission x k. If a[k] < x - 1, then the answer is NO, else we will update array a: a[k] = max(a[k], x).

Solution: 6396297

418A - Football. Author and realization Aksenov239.

Let's consider this tournir as graph. Each vertex should have out-degree k. Then the graph should contain exactly nk edges. But the full-graph contains , because of that if n < 2k + 1 then the answer is  - 1, otherwise we will connect the i-th vertex with i + 1, ..., i + k, taking modulo n if needed.

Solution: 6396331

418B - Cunning Gena. Author and realization Aksenov239.

Let us sort the friends by the number of the monitors in the increasing order. Afterwards we will calculate the dp on the masks: the minimal amount of money Gena should spend to solve some subset of problems, if we take first n friends. Then the answer we should compare with the answer for first i friends plus the number of the monitors, which the i-th friend needs. Is is not hard to see, that if we consider the friends in this order consequently, then we can recalc dp like in the knapsack problem. The running time of this algorithm is O(nlog(n) + n2m).

Solution pashka: 6396347

418C - Square Table. Author and realization Aksenov239.

Let's build array of the length n for each n, that the sum of the squares of its elements is the square:

  • If n = 1, then take [1].
  • If n = 2, then take [3, 4].
  • If n is even, then take .
  • If n is odd, then take .

We are given two numbers n and m. Let array a corresponds to n, and array b corresponds to m. The we will build the answer array c as follows cij = ai·bj.

Solution: 6396358

418D - Big Problems for Organizers. Author chavit, realization Aksenov239.

This problem has two solutions.

The first one. Let's hang the tree on some vertex. Afterwards, let us calculate for eah vertex it's height and 3 most distant vertices in its subtree. Also let's calculate arrays for the lowest common ancestors problem. For each vertex i and the power of two 2j we have p[i][j], up[i][j] and down[i][j]:

  • p[i][j] is the ancestor on the distance of 2j,
  • up[i][j] is equal to the longest path from i to the vertices, which are situated in subtrees of the vertices on the path between i and p[i][j].
  • down[i][j] is equal the same, but from the vertex p[i][j].

And the last part of this solution. Let us be given the query u v. Firstly, we find w = LCA(u, v). Afterwards, we need to find vertex hu, which is situated on the middle of the path between u and v. Really, we need to split the tree by this vertex, count the longest path from u in its tree and count the longest path from v in its tree. If we can imagine in the main tree, we can not delete this vertex, but with our precalculated arrays recalc this two values.

First solution: 6396376

The second solution. In a few words. Let's find the diameter of the tree. Precalc the answer for each vertices on the prefix. Then on the query we find two distant vertices on this diameter and the path. Obviously, diameter should contain the middle of the path, when we find it, using precalculated results on the prefixes and suffixes we can obtain the answer.

Second solution cerealguy: 6396390

418E - Tricky Password. Authors enot.1.10, Aksenov239, realization Aksenov239.

The key theoretical idea of this problem is that the $2$nd row is exactly the same as the $4$th row, $3$rd row is exactly the same as $5$th row and so on. Because of that we need only to answer queries on the first three rows.

Let's move on to the practical part. In the first place we will compress coordinates, that any value will not exceed 2·105. Afterwards, let's split the array into parts of the length LEN. On each part we will calculate the following values: cnt[k] — the number of occurences of the number k on this prefix, also f[k] — the total number of the values, which occur exactly k times on this prefix. Array f we will store in the Fenwick data structure.

It is not hard to see, that array cnt contains the answer for the queries to the 2nd row. To get the answer for the queries to the 3rd row we need to calculate f[cnt[k]... 105]. Also it's quite understandable how to recalc this dp.

In summary, we will get per query. And we take , then we will get per query. Solution: 6396412

Read more »

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

By andrewzta, 6 years ago, translation, In English,

Russian Code Cup is a competition organized by Mail.Ru Group for Russian-speaking programmers. This year the competition will run for the fourth time to gather top 50 to great finals in Moscow in October.

Though Russian Code Cup is open only for those who speak Russian, the team that is working on problems for Russian Code Cup has decided to make a present to all CodeForces users and set up an extra round for everyone.

The round will be held on April 17 at 19-30 Moscow time. The round will be open for everyone and will have both div-1 and div-2 tasks. It will use standard CodeForces rules. The writer of most problems is Aksenov239 — author of many Russian Code Cup problems.

We wish all participants good luck and see you on Thursday at http://codeforces.com

UPD: Score for problems: Div1: 500-1000-1500-2500-2500, Div2: 500-1000-1500-2000-2500. Good luck!

Read more »

Announcement of RCC 2014 Warmup (Div. 2)
Announcement of RCC 2014 Warmup (Div. 2)
Announcement of RCC 2014 Warmup (Div. 1)
Announcement of RCC 2014 Warmup (Div. 1)
 
 
 
 
  • Vote: I like it
  • +244
  • Vote: I do not like it

By andrewzta, 6 years ago, In Russian,

Определены даты проведения крупнейшей в России ежегодной олимпиады по спортивному программированию Russian Code Cup 2014. В этом году программисты сразятся за звание лучшего (и за главный приз – 10 тысяч долларов США) в четвертый раз. Регистрация на чемпионат уже идет, а первый тур состоится уже в эту субботу, 19 апреля!

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

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

На первых двух этапах программисты соревнуются онлайн на сайте Russian Code Cup. Первый квалификационный раунд состоится 19 апреля в 12:00, второй – 18 мая в 19:00, третий – 24 мая в 14:00. Причем программисты, не прошедшие квалификацию с первого раза, могут попробовать свои силы в следующих раундах.

В отборочный тур, назначенный на 14:00 8 июня, пройдут 200 лучших участников из каждого квалификационного раунда. А 50 программистов, преодолевших «сито» отбора, померятся силами в финале, который состоится в октябре 2014 года в офисе Mail.Ru Group.

Победитель Russian Code Cup получит главный приз – 10 тысяч долларов США; участник, занявший второе место, — 5 тысяч долларов США; приз за третье место – 3 тысячи долларов США. Кроме того, ценные призы достанутся всем участникам, дошедшим до финала.

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

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

Read more »

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