andrewzta's blog

By andrewzta, history, 3 months ago, In Russian,

Всем привет!

В этом году российская делегация ведёт блог в форме телеграм-канала https://t.me/russiaioi2019. Заходите в канал завтра, чтобы посмотреть обсуждение задач и текущих результатов.

Удачи всем участникам!

Read more »

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

By andrewzta, history, 19 months ago, In Russian,

Всем привет!

UPD Мы продлили регистрацию до 20 марта, так что сегодня последний шанс зарегистрироваться!

В этом году финал личной номинации "Олимпиады школьников по информатике и программированию", известный также как ИОИП, пройдет 25 марта.

Олимпиада в перечень олимпиад Российского совета олимпиад школьников под номером 62 и имеет 1 уровень. Таким образом, диплом этой олимпиады может давать льготы при поступлении в вуз.

На заключительный этап без дополнительного отбора приглашаются все участники заключительного этапа ВКОШП-2017, вне зависимости от города выступления. Также на заключительный этап без дополнительного отбора приглашаются все участники муниципального этапа ВсОШ в Санкт-Петербурге, обучающиеся в 11 классе, которые набрали на муниципальном этапе хотя бы 250 баллов. Наконец, на заключительный этап приглашаются участники, успешно выступившие хотя бы в одном из двух отборочных туров.

Подробная информация про ИОИП, список допущенных до финала, контактная информация точек проведения и возможность подать заявку на участие в финале ИОИП для тех, кто к нему допущен — на сайте олимпиады http://neerc.ifmo.ru/school/ioip

Точки проведения организованы в Санкт-Петербурге, Мытищах, Екатеринбурге, Мозыре, Ижевске, Челябинске, Самаре, Ханты-Мансийске, Ставрополе, Новосибирске, Витебске, Иннополисе, Могилеве, Бишкеке, Кременчуге, Москве, Хабаровске.

Удачи всем и до встречи в финале!

Read more »

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

By andrewzta, 21 month(s) ago, In Russian,

Всем привет!

В марте центре Сириус пройдет смена по олимпиадной информатике. Информация о смене выложена на сайте центра: https://sochisirius.ru/obuchenie/nauka/smena145/620

Эта смена будет ориентирована на начинающих школьников, впервые попавших на Всерос или не становившихся ранее призерами. Точные критерии опубликованы на сайте: от тех регионов, которые в прошлом году были представлены 10 или более школьниками, приглашаются участники, которые не были в прошлом году на заключительном этапе, а от остальных регионов — те, кто в прошлом году не был призером или победителем. Школьники из 11 класса не могут принять участие в смене.

Отбор среди тех, кто может принять участие в смене, производится по баллам на региональном этапе. Если у вас на региональном этапе хотя бы 500 баллов, и вы подходите под критерии, мы рекомендуем подать заявку в смену прямо сейчас (можно подать заявку и с меньшим числом баллов, но шансов на зачисление меньше). Кроме того, от регионов, где никто не проходит на Всерос (ориентировочно 550-600 баллов, в зависимости от класса), приглашается по одному участнику не старше 9 класса, при условии что именно этот участник будет представлять регион на заключительном этапе.

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

Удачи всем и до встречи в Сириусе!

Read more »

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

By andrewzta, history, 2 years ago, translation, In English,

Hi all!

During Elimination Round of Russian Code Cup 2017 we had a technical issue that caused almost all problem A solutions sent for evaluation from 5-th to 10-th minute of the contest be accepted.

We found that issue when it was already too late, so it wouldn't be fair to rejudge the solutions. However, we understand that this issue created unfair circumstances for other contestants, that could lose to those lucky ones that submitted in the described time frame.

We have rejudged all solutions after the round, and tried to simulate how could the contest proceed should they have been judged correctly. Of course, any simulation of this kind cannot be accurate, and there is no completely fair resolution. We have decided to do the following:

1) Increase the number of Final Round participants to 55. It gives partial compensation to those participants who could have qualified but failed to do so because of someone's incorrectly small penalty.

2) Increase number of t-shirts to 205. So all participants who have at least 3 accepted problems get our branded t-shirt.

Judges and the technical group of Russian Code Cup are sorry about the issue. We will do our best to avoid anything like that in future.

Good luck to all finalists in the Final Round that will take place in September 2017!

Read more »

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

By andrewzta, 3 years ago, In Russian,

Всем привет!

Открыта регистрация на заключительный этап ИОИП.

Если вы

  • учитесь в выпускном классе и участвовали в заключительном ВКОШП-2016

ИЛИ

  • учитесь в выпускном классе и успешно выступили в одном из отборочных интернет-туров http://neerc.ifmo.ru/school/io

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

Заполните анкету http://neerc.ifmo.ru/school/ioip

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

Read more »

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

By andrewzta, history, 3 years ago, translation, In English,

In 2016 teams form Middle Asia are invited to Almaty to take part in NEERC. The contest will take place in Kazakh-British Technical University. See contact information at http://neerc.ifmo.ru/information/contacts.html#almaty.

Read more »

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

By andrewzta, history, 3 years ago, translation, In English,

Information about Uzbekistan Subregional Contest 2016 is posted at http://neerc.ifmo.ru/subregions/uzbekistan.html

Uzbekistan Subregional Contest in 2016 will take place on November 13, 2016 and will be online. The start of the contest will be at 13-00 Uzbekistan Time (UTC+5).

Teams from Uzbekistan universities must take part in it at their universities, under observation of their coaches. To take part, coach must completely register teams at Baylor registration system and send the list of teams to neerc@mail.ifmo.ru before November 10, 2016.

UPD Correct local time now posted.

Read more »

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

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

Всем привет!

Опубликована первая информация о проведении заключительного этапа ИОИП. Заключительный этап ИОИП состоится 27 марта 2016 года.

В этом году для участия в заключительном этапе необходимо подать заявку. Подать заявку имеют право ученики выпускного класса — участники ВКОШП-2015 (все площадки, вне зависимости от результата), а также набравшие хотя бы 300 баллов в первом отборочном онлайн туре или хотя бы 200 баллов во втором отборочном онлайн туре.

Площадки уже согласованы в Санкт-Петербурге, Москве (для участников из Москвы и МО), Ижевске, Самаре, Екатеринбурге, Казани, Мозыре. Ведется согласование дополнительных площадок.

Если вы попадаете под критерии, подайте заявку на участие в заключительном этапе ИОИП сейчас, в целом срок подачи заявок до 20 марта.

Обратите внимание! Принять участие в финале ИОИП смогут только школьники, которые в этом году учатся в выпускном классе, остальные школьники смогут принять участие в интернет-олимпиаде вечером в тот же день.

UPD В список точек проведения добавлен Ханты-Мансийск.

UPD2 В список точек проведения добавлен Челябинск.

UPD3 В список точек проведения добавлены Новосибирск и Бобруйск.

UPD4 Оргкомитеты ИОИП и Московской олимпиады школьников по информатике приняли решение НЕ формировать расписание проведения в Москве таким образом, чтобы обеспечить возможность участия в обеих олимпиадах. Мы рекомендуем участникам принять участие в той из олимпиад, тип задач которой кажется вам ближе. В Москве в ИОИП смогут принять участие только жители Москвы и Московской области. Участникам из других регионов, которые которые указали Москву как желаемое место участия, необходимо выбрать другую удобную точку проведения и написать письмо на iojury@gmail.com, повторно регистрироваться не нужно!

UPD5 В список точек проведения добавлен Липецк.

UPD6 До конца подачи заявок осталась неделя! И хотя нам очень нравится круглое число в 256 заявок, мы надеемся, что в финале примет участие большее число школьников. Учитесь в выпускном классе и принимали участие в ВКОШП? Участвовали в отборах? Регистрируйтесь на заключительный этап ИОИП и агитируйте друзей, которые имеют право принять участие. Выбирайте удобную вам точку проведения и подавайте заявку.

UPD7 Мы решили продлить прием заявок на участие в заключительном этапе до 23 марта, так что у вас есть еще 3 дня, чтобы подать заявку, если вы подходите под критерии: выпускной класс И (участник ВКОШП ИЛИ прошел отборочный тур).

Read more »

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

By andrewzta, 5 years ago, In Russian,

Завершился финал Russian Code Cup 2014. Окончательные результаты на сайте http://russiancodecup.ru.

Поздравляем победителей!

Read more »

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

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 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 andrewzta, 6 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, 6 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 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

By andrewzta, 6 years ago, In Russian,

Начинается регистрация на ИОИП, сайт олимпиады http://neerc.ifmo.ru/school/ioip

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

Все учащиеся выпускных классов, которые принимали участие во ВКОШП приглашаются на заключительный этап ИОИП без отбора. А тем, кто на ВКОШП не попал, можно поучаствовать в отборах, которые пройдут 18 и 26 января 2014 года.

Заключительный этап пройдет в воскресенье, 16 марта 2014 года.

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

Всем удачи!

Read more »

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

By andrewzta, 6 years ago, In Russian,

Уже в эти выходные, 30 ноября — 1 декабря состоится NEERC.

Если вы хотите попасть на NEERC в Санкт-Петербурге, но не зарегистрированы как Attendee ни у одной из команд, пожалуйста заполните форму. Вы сможете получить бейдж на стойке регистрации в субботу перед открытием или в воскресенье перед началом контеста.

Read more »

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

By andrewzta, 6 years ago, In Russian,

В понедельник, 23 сентября состоится финал Russian Code Cup. Если вы не сможете придти на соревнование вживую, приглашаем вас посмотреть видеотрансляцию на сайте russiancodecup.ru. Ведущий — Михаил Мирзаянов. Начало трансляции в 10-40.

Приходите, будет интересно!

Read more »

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

By andrewzta, 6 years ago, In Russian,

Всем привет!

В понедельник, 23 сентября, в Москве пройдет финал Russian Code Cup 2013! Приглашаем вас посетить мероприятие, посвященное финалу чемпионата.

В этом году финал Russian Code Cup 2013 пройдет с участием мировых звезд программирования.

23 сентября перед зрителями и участниками выступят:

  • Эдвард Йордон, пионер в разработке методологии программирования и автор метода Йордона, член Компьютерного зала славы и автор бестселлеров по практике программирования, в числе которых культовый «Путь камикадзе»
  • Кен Голдберг, изобретатель первого в мире робота с web-интерфейсом, профессор Школы информатики Калифорнийского университета в Беркли
  • Дмитрий Скляров, разработчик алгоритма программы Advanced eBook Processor

и другие яркие личности мировой IT-индустрии.

Для посещения мероприятия необходимо зарегистрироваться на сайте RCC — http://russiancodecup.ru/signup_guest/

Read more »

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

By andrewzta, 7 years ago, In Russian,

В субботу, 13 апреля, состоялся первый квал. Его итоги подводятся в статье на Хабре http://habrahabr.ru/company/mailru/blog/177171. 200 лучших прошли в отборочный раунд.

А уже скоро, 11 мая, в 12-00 состоится второй квалификационный раунд. Ждем всех, кто не прошел квалификацию с первого раза или не смог по тем или иным причинам принять участие в первой квалификации. Напоминаем заранее, чтобы участникам было удобнее составлять свои планы на длинные праздники.

Read more »

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