150 000 рублей за первое место готовимся к Russian Code Cup, разбирая решения задач


Оглавление (нажмите, чтобы открыть):

150 000 рублей за первое место: готовимся к Russian Code Cup, разбирая решения задач предварительного тура

Группа: Главные администраторы
Сообщений: 14349
Регистрация: 12.10.2007
Из: Twilight Zone
Пользователь №: 1

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

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

В сегодняшнем разборе участвуют:

  • Олимпиада в Гномляндии
  • Один день Антона Сергеевича и его студентов
  • Проблемы хранения млурана в ядерной лаборатории Флатландии
  • Актуальный вопрос защиты планеты от метеоритов
  • Телепорты и то, какие препятствия они создают для кладоискателей

Начнем с итогов. В квалификации приняли участие 765 человек (заметим, что это число участников, приславших свои варианты решения; зарегистрировавшихся было заметно больше).

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

Географическое распределение участников получилось действительно глобальным, хотя, конечно, число российских участников было максимальным. Итак, в порядке убывания:

В отборочный тур вышел 201 человек. Ниже — список 10 участников, первыми прошедших в отборочный тур:

1. Владислав Епифанов

2. Сергей Рогуленко

3. Иван Попелышев (3 место)

3. Пётр Митричев (еще одно 3-е место)

6. Владислав Исенбаев winger

8. Геннадий Короткевич

8. Роман Ризванов

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

А теперь перейдем к разбору задач. Участники смогут сверить свои решения, а те, кто еще не проходил квалификацию — потренироваться и проверить свои версии (кстати, следующие квалификационные туры — 11 мая и 2 июня).

Задача A. Олимпиада

Идея: Виталий Аксёнов

Реализация: Виталий Аксёнов

Разбор: Виталий Аксёнов

Подробная постановка задачи

Ограничение по памяти — 256 мегабайт

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

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

Помогите гномам найти минимальную площадь, которую могут занимать три поля после постройки.

Одно из возможных оптимальных расположений полей в первом примере приведено на рисунке.

Формат входных данных

Входные данные содержат не более 1000 строк, каждая из которых содержит в себе описание трёх полей — шесть натуральных чисел, каждое из которых не превосходит 10000.

Первое и второе число обозначают размеры первого поля, третье и четвёртое — размеры второго поля, пятое и шестое — размеры третьего поля.

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

Формат выходных данных

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

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

Выполним перебор того, как положить каждое поле — вертикально или горизонтально. После того, как мы зафиксировали положение полей, достаточно просто посчитать площадь объединения прямоугольников. Ее можно посчитать следующим образом: S = S1 + S3 + S3 — S12 — S23 — S13 + S123, где Si — площадь i-го прямоугольника, Sij — площадь пересечения двух прямоугольников с номерами i и j, а S123 — площадь пересечения всех трех прямоугольников.

Задача B. Трапецоидная карта и трапеции

Идея: Виталий Демьянюк


Реализация: Виталий Демьянюк

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

Подробная постановка задачи

Ограничение по памяти — 256 мегабайт

Однажды Антон Сергеевич рассказывал студентам алгоритм построения трапецоидных карт. В качестве разминки он дал им задачу о трапециях. Он нарисовал на доске n отрезков. Длина i-го отрезка равна ai. Студентам требуется найти количество различных наборов из четырех отрезков, из которых можно составить равнобедренную трапецию ненулевой площади.

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

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

Помогите студентам найти количество таких наборов.

Формат входных данных

В первой строке задано число t — столько раз Антон давал своим студентам эту задачу. В следующих 2t cтроках содержится описания всех задач.

Описание каждой задачи состоит из двух строк. В первой строке описания дано число n — количество отрезков, нарисованных на доске. Во второй строке описания задачи дано n целых чисел ai — их длины (4 ≤ n ≤ 5000, 1 ≤ ai ≤ 108 для всех i от 1 до n).

Суммарное число всех отрезков во всех задачах не превышает 5000.

Формат выходных данных

Для каждой задачи в отдельной строке выведите одно число — искомое количество наборов.

Обозначим длины меньшей и большей параллельных сторон трапеции за a и b соответственно, а за c — длину боковых сторон. Тогда трапецию можно составить только в том случае, когда a + 2c > b. Перебрав a, b и с, получаем решение за O(n 3 ).

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

Также нужно не забыть обработать случаи, в которых a = b, a = c, b = c, и аккуратно следить за тем, чтобы в каждой четверке номера отрезков были попарно различными. Итоговая сложность равна O(n 2 ).

Задача C. Хранение млурана

Идея: Виталий Аксенов

Реализация: Павел Кротков

Разбор: Павел Кротков

Подробная постановка задачи

Ограничение по памяти — 256 мегабайт

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

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

В ядерной лаборатории Флатландии образцы млурана хранятся на двух специальных складах. Ученым удалось получить n различных изотопов млурана, массы которых являются числами от 1 до n. Теперь необходимо распределить изотопы по складам для хранения. Безопасными называются такие способы хранения, при которых каждый изотоп хранится ровно на одном складе, а любые два различных изотопа, сумма масс которых равна одному из «критических чисел», хранятся на разных складах.

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

Формат входных данных

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

Первая строка описания содержит два целых числа n и k (1 ≤ n ≤ 1018, 1 ≤ k ≤ 61) — количество изотопов, которые необходимо хранить, и количество «критических чисел». Следующая строка содержит k различных натуральных чисел, каждое из которых является степенью двойки и не превышает 2n — критические числа. Критические числа отделены друг от друга пробелами.

Количество наборов данных в каждом тесте не превышает 10000. Последняя строка теста содержит два нуля.

Формат выходных данных

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

Реализуем сначала решение, работающее за линейное время. Будем рассматривать массы изотопов в порядке возрастания, начав с 1. Пусть k — текущее число, а 2 t — минимальная степень двойки, большая k. В таком случае:

  • если k является степенью двойки или 2 t не лежит в множестве «критических чисел», изотоп массы k можно хранить на любом складе
  • в противном случае изотоп массы k можно хранить только на том складе, на котором нет изотопа массы 2 t — k

Заметим, что ответ равен 2 x + d , где d — количество степеней двойки, не меньших 1 и не больших n, а x — количество таких чисел, не являющихся степенями двойки, что минимальная большая их степень двойки не лежит в множестве «критических чисел». Значит, можно разбить все числа от 1 до n на log2n отрезков, границы которых — соседние степени двойки, после чего выбрать нужные отрезки и просуммировать их длины.

Задача D. Защита планеты

Идея: Виталий Аксёнов

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


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

Подробная постановка задачи

Ограничение по памяти — 256 мегабайт

После недавнего падения метеорита на Урале правительства многих стран задумались о защите Земли от астероидов. Для этого было создано Международное Антиметеоритное Агентство (МАМА), в которое были приглашены лучшие учёные в области астрофизики.

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

Для удобства введём прямоугольную декартову систему координат. Пусть Земля имеет координаты (0, 0, 0). Все астероиды и Земля считаются материальными точками в пространстве.

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

Формат входных данных

Первая строка содержит два целых числа n и R (1 ≤ n ≤ 100000, 1 ≤ R ≤ 106) — количество астероидов и радиус зоны опасности.

В каждой из следующих n строк содержится по шесть целых чисел xi, yi, zi, vxi, vyi и vzi (в€’106 ≤ xi, yi, zi ≤ 106, в€’100 ≤ vxi, vyi, vzi ≤ 100) — координаты, задающие начальное положение и вектор скорости i-го астероида. Гарантируется, что вектор скорости не равен 0.

В следующей строке содержится одно целое m (1 ≤ m ≤ 100000) — количество моментов времени, которые интересуют учёных.

В каждой из следующих m строк содержится по одному целому числу ti (0 ≤ ti ≤ 107) — момент времени, интересующий ученых.

Формат выходных данных

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

Рассмотрим каждый метеорит и найдём времена входа и выхода в зону опасности. Для этого в уравнение сферы x 2 +y 2 +z 2 = R 2 подставим уравнение прямой, задающей траекторию движение метеорита, то есть x = x+dx•t, y = y+dy•t, z = z+dz•t. У нас получится квадратное уравнение относительно времени. Корни и будут являться интересующими нас временами. В этой задаче могли возникнуть проблемы с точностью чисел с плавающей точкой, поэтому, если корень уравнения был достаточно близок к целому числу, его необходимо было округлить.

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

Время работы O((n + m)•log(n + m))

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

Идея: Анна Малова

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

Разбор: Борис Минаев

Подробная постановка задачи

Ограничение по памяти — 256 мегабайт

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

Составление плана осложняется одним фактом. Некоторые пары городов соединены телепортами. Например, если город A и город B соединены телепортом, то, приехав по некоторой дороге в город A, вы сразу же телепортируетесь в город B и можете продолжить движение только по дорогам, которые соединены с городом B. Аналогично, если вы приехали по дороге в город B, то сразу же телепортируетесь в город А и продолжаете движение по дорогам, которые соединены с городом A.

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

Формат входных данных

Входные данные содержат описание нескольких тестов. Каждый тест имеет следующую структуру. В первой строке содержатся три целых числа n, m, k (1 ≤ n ≤ 105, 1 ≤ m ≤ 105, 0 ≤ k ≤ 105) — количество городов, количество дорог и количество телепортов. В следующих m строках содержатся по два различных числа — номера городов, которые соединяет очередная дорога. Далее в k строках содержатся по два различных числа, описывающие пары городов, которые соединены телепортами.

Между двумя городами может быть несколько дорог. Никакой город не соединен дорогой сам с собой. Никакой город не соединен телепортом сам с собой. Любой город соединен телепортом не более чем с одним другим городом.

Гарантируется, что суммарное количество городов во всех тестах не превышает 105. Аналогично, суммарное количество дорог и суммарное количество телепортов также не превышает 105. Последняя строка входных данных содержит три нуля. Их обрабатывать не нужно.

Формат выходных данных

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

Для удобства обозначим количество дорог, которые ведут в город i, как сi. Для начала нам необходимо определить, существует ли вообще эффективный план путешествия. Во-первых, если есть два города i и j такие, что сi в‰ 0 и сj в‰ 0 и не существует пути между i и j, то план мы построить не можем. Следует заметить, что путь может содержать не только дороги, но и телепорты.

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

Рассмотрим, что же происходит с городами, которые лежат на концах пути. Во-первых, если город i соединен телепортом с j и лежит на конце пути, то сi= сj + 1 (кроме случая, когда j также является концом пути). При этом если путь начинается и заканчивается в городе i, то сi = сj + 2. Если же город не соединен телепортом с другим и находится на одном из концов пути, то его сi может быть нечетным.

В итоге, чтобы проверить существование пути, необходимо сделать следующее. Посчитаем для каждого города некоторую величину ai. Если город i соединен с j телепортом, то ai = max(0, ci — cj). В противном случае, ai = сi mod 2. Если сумма всех ai равна двум или нулю, то путь существует, иначе нет.

Построение плана посещения страны аналогично построению Эйлерового пути в обычном графе. Начинать поиск необходимо с вершины, у которой ai в‰ 0; если же такой нет, то с любой, у которой сi в‰ 0. При переходе к очередной вершине, если она соединена с другой вершиной телепортом, необходимо просто перейти к ней и продолжить поиск пути дальше. Доказательство того, что путь действительно найдется полностью, аналогично доказательству существования Эйлерового пути в обычном графе.

Итоговая сложность равна O(n + m + k).

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


Новая победа Геннадия Короткевича: первый на Russian Code Cup

Накануне, 18 сентября, подвели итоги чемпионата по программированию Russian Code Cup. Магистрант Университета ИТМО, двукратный чемпион ACM ICPC Геннадий Короткевич стал лидером соревнований.

Геннадий Короткевич победил в чемпионате, решив три задачи из шести. С таким же результатом завершили контест обладатели второго и третьего мест — аспирант Нижегородского государственного университета Владислав Епифанов и студент НГУ Николай Калинин. Однако они набрали больше штрафных очков, чем победитель RCC. Штрафные баллы здесь начисляются по правилам ACM ICPC: за каждую решенную задачу приписывают штраф, который составляет время в минутах с начала соревнования до момента решения задачи. Кроме того, каждая неудачная попытка решить задание «награждается» 20 штрафными минутами.

По правилам соревнования участником может стать любой желающий старше 18 лет. Поэтому среди финалистов можно встретить как выпускников, так и первокурсников вузов. Чемпионат состоит из пяти раундов, и к финалу выживают только 50 сильнейших программистов, среди которых, помимо Геннадия Короткевича, есть и другие представители Университета ИТМО. Так, студент четвертого курса вуза Иван Белоногов занял 12 место, первокурсник Михаил Путилин — 23 место, магистрант Владимир Смыкалов — 32, а выпускник вуза Евгений Капун — 27 место.

Тройка лидеров Russian Code Cup

Приз за первое место составил 150 000 рублей, участник, занявший второе место, получил 100 000 рублей, а третье — 65 000 рублей. Участники, занявшие в финальном раунде 4−10 места, выиграли по 30 000 рублей, с 11 по 25 — получили поощрительный приз в размере 15 000 рублей.

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

С полным перечнем победителей можно ознакомиться по ссылке.

Редакция новостного портала Университета ИТМО

150 000 рублей за первое место: готовимся к Russian Code Cup, разбирая решения задач предварительного тура

В этом году RCC начнется с «разогревающего» раунда, который стартует 15 марта в 13:00. Результаты этого этапа не учитываются в следующих турах. Он проводится для того, чтобы участники могли размяться и оценить свои силы перед основными раундами чемпионата.

Мастер Йода рекомендует:  Искусственный интеллект помогает производить нейлон

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

В ходе первых двух этапов участники соревнуются онлайн на сайте Russian Code Cup. Три квалификационных раунда стартуют 28 марта, 25 апреля и 31 мая, причем программисты, которым не повезло в первом квалификационном туре, могут попытать удачу в следующих. В отборочный тур, назначенный на 14 июня, пройдут по 200 лучших участников из каждого квалификационного раунда. А 50 программистов, показавшие при отборе наилучшие результаты, померятся силами в финале. С каждым этапом сложность задач будет возрастать, и в финале будут предложены наиболее трудные из них. Итоговый раунд состоится 19 сентября.

Победитель, продемонстрировавший в течение чемпионата самые высокие результаты по скорости и качеству решения задач, получит денежный приз в размере 300 000 рублей; обладатели второго и третьего места — 150 000 и 90 000 рублей соответственно. Программистам, занявшим с четвертого по десятое места, достанется по 30 000 рублей. Кроме того, все 50 финалистов получат футболки с символикой чемпионата, а 600 участников, прошедших в отборочный тур, — онлайн-сертификаты, подтверждающие их квалификацию.

Началась регистрация на пятый ежегодный чемпионат по спортивному программированию Russian Code Cup

Определены даты проведения главного российского чемпионата по спортивному программированию — Russian Code Cup. В этом году участники вновь сразятся за звание лучшего и призовой фонд в размере 750 000 рублей.

Определены даты проведения главного российского чемпионата по спортивному программированию — Russian Code Cup. В этом году участники вновь сразятся за звание лучшего и призовой фонд в размере 750 000 рублей.

Russian Code Cup (RCC) ежегодно собирает несколько тысяч русскоговорящих участников со всего мира. Они сражаются за звание не только самого талантливого, но и самого быстрого программиста, поскольку решение оригинальных и сложных задач чемпионата оценивается сразу по двум критериям: качество и скорость. Russian Code Cup даёт молодым программистам прекрасную возможность продемонстрировать свое мастерство, получить признание профессионального сообщества и обратить на себя внимание крупных IT-компаний.

В этом году RCC начнётся с «разогревающего» раунда, который стартует 15 марта в 13:00. Результаты этого этапа не учитываются в следующих турах; он проводится для того, чтобы участники могли размяться и оценить свои силы перед основными раундами чемпионата.

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

В ходе первых двух этапов участники соревнуются онлайн на сайте Russian Code Cup. Три квалификационных раунда стартуют 28 марта, 25 апреля и 31 мая, причём программисты, которым не повезло в первом квалификационном туре, могут попытать удачу в следующих. В отборочный тур, назначенный на 14 июня, пройдут по 200 лучших участников из каждого квалификационного раунда. А 50 программистов, показавшие при отборе наилучшие результаты, померяются силами в финале. С каждым этапом сложность задач будет возрастать, и в финале будут предложены наиболее трудные из них. Итоговый раунд состоится 19 сентября.

Победитель, продемонстрировавший в течение чемпионата самые высокие результаты по скорости и качеству решения задач, получит денежный приз в размере 300 тыс. рублей; обладатели второго и третьего места — 150 тыс. и 90 тыс. рублей соответственно. Программистам, занявшим с четвертого по десятое места, достанется по 30 тыс. рублей. Кроме того, все 50 финалистов получат футболки с символикой чемпионата, а 600 участников, прошедших в отборочный тур, — онлайн-сертификаты, подтверждающие их квалификацию.

Зарегистрироваться на RCC можно на сайте cups.mail.ru. Этот ресурс объединяет все IT-соревнования, ежегодно проводимые Mail.Ru Group – Russian Code Cup, чемпионат по программированию искусственного интеллекта Russian AI Cup, соревнование для разработчиков приложений, игр и интернет-сервисов Russian Developers Cup.

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

В прошлом году победителем Russian Code Cup 2014 стал Геннадий Короткевич из НИУ ИТМО (в позапрошлом году он занял в чемпионате второе место). Серебряным призёром был признан Пётр Митричев (также являющийся победителем Russian Code Cup 2013). Третье место досталось Егору Куликову.

«За время, которое обычный программист тратит на понимание задачи, спортивный ее уже решает»

В сентябре российские школьники привезли две золотые и две серебряные медали с Международной олимпиады по информатике IOI 2020 (International Olympiad in Informatics). Результат неплохой, и это неудивительно: нашим командам это не впервой. Россия держится в пятерке самых успешных команд по числу и достоинству медалей. IOI – вершина олимпиадной цепочки, которая начинается со школьного этапа Всероссийской олимпиады. Как она устроена, кто и как пробивается к вершинам и как России удалось занять вторую строчку в общем количестве золотых медалей после Китая, читайте в материале Indicator.Ru.

Что такое спортивное программирование

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

«За время, которое обычный программист тратит на понимание задачи, спортивный программист ее уже решает», — комментирует технический координатор сборов перед IOI 2020 года, главный судья сборов по программированию Moscow Workshops ICPC Олег Христенко.

Технический координатор сборов перед IOI 2020 года Олег Христенко

Александр Ломакин/Центр развития ИТ-образования МФТИ

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

Как устроен мир спортивного программирования

Путь школьника в спортивное программирование начинается с этапов Всероссийской олимпиады школьников: школьного, муниципального, областного и заключительного. По результатам Всероса и с учетом других заслуг Центральная предметно-методическая комиссия Министерства просвещения отбирает около 20 человек в национальную сборную для поездки на Международную олимпиаду — IOI. Кроме того, школьники участвуют во Всероссийской командной олимпиаде по программированию (ВКОШП) и в ряде перечневых олимпиад таких, как олимпиада «Ломоносов», Открытая олимпиада школьников по программированию, «Когнитивные технологии», «Технокубок» и другие. Перечневые олимпиады бывают трех уровней. Из них только первый обеспечивает поступление в определенные вузы без экзаменов или 100 баллов по информатике за ЕГЭ. Олимпиады второго уровня дают 100 баллов по ЕГЭ, но только в определенных вузах. Льготы по результатам олимпиад третьего уровня каждый вуз определяет сам.

Многие продолжают занятия спортивным программированием и в студенчестве. В самом масштабном соревновании по олимпиадному программированию для студентов — чемпионате мира International Collegiate Programming Contest (ICPC) — за год на отборочных этапах участвует 50 тысяч студентов со всего мира. В отличие от Всероссийской олимпиады и IOI, здесь ребята соревнуются не индивидуально, а в составе команд из трех человек. По правилам ICPC проходят и локальные соревнования при университетах всего мира.

Помимо вузовских олимпиад, существуют популярные онлайн-сообщества с регулярными соревнованиями, в которых участники в личном зачете борются за место в рейтинге. Например, TopCoder или российская платформа Cofeforces.

Свои чемпионаты устраивают и крупные IT-компании. Чаще всего в них предлагается решить «приближенные» задачи. Как правило, у них нет конкретного решения. Участники этих соревнований должны разработать некий продукт, который ближе всего подошел бы к идеальному решению этой проблемы. Обычно такие соревнования проходят в несколько отборочных туров в режиме онлайн, а в финале лучших собирают на очной площадке.

Экскурс в историю

Первые соревнования по спортивному программированию проходили среди студентов. Чемпионат ICPC в первый раз был органиован в 1977 году в Атланте (США). Он начинался как соревнование между четырьмя американскими университетами при поддержке ассоциации вычислительной техники ACM и только в 1990 году вышел на международный уровень.


Участники 13-го чемпионата по спортивному программированию ACM

Идею организовать соревнование среди школьников на двадцать четвертой Генеральной конференции ЮНЕСКО предложил болгарский профессор Благовест Сендов. В болгарском городе Правец, и состоялась первая олимпиада. В ней приняли участие 46 участников из 13 стран. Лучший результат и в индивидуальном, и в командном зачете показала принимающая страна.

С 1989 года Международная олимпиада по информатике IOI проходит ежегодно. В 1991 году соревнования состоялись в СССР, в Минске, и после этого Россия принимала IOI единственный раз – в 2020 году. Делегатов со всего мира встречали в Татарстане, в Казанском федеральном университете. Тогда России, как принимающей стороне, разрешалось выставить на соревнования не одну, а сразу две команды – одна соревновалась «в зачет», вторая – «не в зачет». Наши школьники выиграли три золотые, четыре серебряные и одну бронзовую медали и в итоге заняли второе место после Китая.

Шансов на то, что Россия снова примет IOI немного, но такие случаи были — дважды проводилась олимпиада в Болгарии и Греции. Всего принимали у себя олимпиаду 28 стран.

Как устроена IOI

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

Олимпиада проходит на английском языке, но по заявке участников им могут положить в конверт с английским заданием еще и версию на их родном языке. Решать задачи олимпиады можно на любом из трех языков программирования: C++, Pascal или Java. Каждую задачу можно «сабмитить», то есть посылать ее решение в систему, максимум 50 раз. В системе ребята сразу видят статус своего сабмита — прошло решение или нет. Программа выдает им короткий автоматический ответ о наличии ошибок, и участники могут их исправить. На количество полученных баллов влияет способ решения задачи и количество потраченного на это времени. Из нововведений этого года – новые рекомендации по подаче уточняющих вопросов к задачам. Во время соревнования участник может попросить пояснения задачи от организаторов и получить ответ в формате «да», «нет», «без комментариев», «ответ есть в условии задачи» или «invalid question». Это значит, что вопрос надо переформулировать.

Сборы будущих участников олимпиады в МФТИ

Центр развития ИТ-образования МФТИ

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

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

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

Руководитель национальной сборной на IOI 2020, проректор МФТИ Алексей Малеев поясняет, что соотношение медалей помогает оценить распределение сил между странами год от года. А сравнение количества баллов картину не проясняет: «По баллам результаты сравнивать сложно, каждый раз новые задачи. Если дать легкие задачи, значит будет в среднем больше набрано баллов, если сложные – меньше».

О задачах олимпиады

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

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

В каждой задаче на IOI выделены подзадачи, за решение которых можно набрать баллы, даже если школьник не справился с задачей целиком. Об этом рассказывает Олег Христенко: «На IOI решение задачи оценивается в баллах от 0 до 100. Баллы выставляются системой по результатам запуска программы участника на тестах. В обычных задачах оценка за каждый тест — «верно» или «неверно». Полный балл выставляется за прохождение всех тестов. За прохождение определенных групп тестов, обычно соответствующих более простым подзадачам, выставляются частичные баллы».

Один из участников российской команды — Егорь Лифарь — на сборах

Центр развития ИТ-образования МФТИ

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

Христенко отметил, что на школьной международной олимпиаде по информатике задачи более разнообразные, чем на студенческой: «Бывают интересные задачи с открытыми тестами, задачи на encoder-decoder, когда одна и та же программа участника должна работать в двух режимах».

Как это было в 2020 году

Нынешняя олимпиада в Японии стала тридцатой. Она проходила в Цукубе, научном городке вблизи Токио, с 1 по 8 сентября 2020. В ней приняли участие 335 участников из 87 стран. Абсолютный победитель IOI этого года, член сборной США Бенджамин Ци был единственным среди участников олимпиады, кто носит титул «Легендарный гроссмейстер» в одном из самых популярных сообществ олимпиадных программистов Codeforces. Это означает, что он входит в число 19 программистов, которые набрали на Codeforces более 3000 баллов в регулярных соревнованиях. Сейчас Бенджамин Ци — восьмой в этом рейтинге.

В российскую сборную вошли выпускник Общеобразовательной школы-интерната «Лицей имени Н.И. Лобачевского» КФУ Рамазан Рахматуллин, 11-классник московской школы-интерната имени А.Н. Колмогорова МГУ имени М.В. Ломоносова Владимир Романов, выпускник питерского «Президентского физико-математического лицея № 239» Михаил Анопренко, а также самый юный участник команды – девятиклассник из московской Школы «Интеллектуал» Егор Лифарь.

«Для решения задачи требуется изобрести верный алгоритм, а также правильно и аккуратно реализовать его в программе. Оба этапа важны: не зная алгоритм, нельзя написать программу, но без навыков программирования даже гениальная идея сама по себе не принесет баллов. В некоторых задачах придумать решение сложнее, чем потом написать программу, а в некоторых наоборот: идея решения на поверхности, но кода нужно очень много. В задачах олимпиады прошлого года гораздо сложнее было изобрести правильную идею, чем писать код. В этом году баланс чуть сместился в сторону реализации, написания больших программ, но и дойти до идеи решения тоже было непросто. С отборочными мы хорошо угадали. На отборах было несколько задач, похожих на те, что были в итоге на Межнаре», – рассказал один из тренеров команды, финалист престижных индивидуальных соревнований по спортивному программированию Topcoder Open и Russian Code Cup, тренер Moscow Workshops ICPC и команд-чемпионов ICPC Михаил Тихомиров. Кроме него команду готовил и медалист ICPC, тренер шестикратных чемпионов ICPC, судья Всероссийской олимпиады по информатике Андрей Станкевич. Ранее в течение многих лет команду тренировал Владимир Кирюхин, он совсем недавно передал ее новому поколению.

Как ребята готовились

До того, как попасть на сборы перед IOI, школьники проходят четыре этапа Всероссийской олимпиады школьников: школьный, муниципальный, два тура областного и два тура заключительного. Кроме того, они участвуют в двух профильных сменах образовательного центра «Сириус»: в марте там готовили призеров регионального этапа Всероса к заключительному этапу, в июне —призеров и победителей заключительного этапа к Международной олимпиаде. Дальше 20 участников, отобранных ЦПМК, приезжают на сборы, которые в этом году впервые организовал Физтех.

«Я много участвовал в отборах в сборную, где-то четыре раза, это больше, чем у остальных, – рассказал Рамазан Рахматуллин. – Я очень хотел победить, но, в первую очередь, хотел пройти в сборную, победить уже потом».

Для подготовки школьников к IOI в МФТИ также организовывают лагерь Moscow Workshops Juniors (Зимняя компьютерная школа), в котором школьники из разных стран могут учиться информатике и готовиться к олимпиаде. Трое из четырех участников российской сборной этого года, вся сборная Белоруссии и Казахстана, а также участник сборной Греции тренировались в этом лагере.

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

Сборы команды в МФТИ

Центр развития ИТ-образования МФТИ

Результаты олимпиады: мы и они

В этом году были награждены 167 участников из 335. 29 золотых медалей вручили тем, кто набрал 336 баллов и больше, 55 серебряных – тем, чей результат перевалил за 272 балла, и 83 бронзовые медали – тем, кто преодолел границу в 187 баллов.

Были среди участников и те, кто не решил ни одну задачу. А вот победитель IOI, Бенджамин Ци, решил четыре задачи из шести на максимальные 100 баллов и в сумме набрал 499 баллов из максимальных 600. В этом году впервые удалось завоевать два золота Грузии, пока это лучший результат страны за всю историю выступлений. В медальном зачете хорошо выступила Белоруссия, завоевав две золотые и две серебряные медали. Благодаря этому в общекомандном зачете они поделила с Россией 4-5 место. За Беларусь с 2006 по 2012 год выступал легендарный олимпиадник Геннадий Короткевич из Гомеля, что много лет выводило страну в лидеры IOI. Короткевич был абсолютным победителем IOI трижды — с 2009 по 2011 годы, еще три раза брал золото и один раз серебро.

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

В нашей сборной места и медали распределились таким образом:

Рамазан Рахматуллин — 11 место (золото),

Владимир Романов — 20-21 место (золото),


Михаил Анопренко — 33-36 место (серебро),

Егор Лифарь — 60-64 место (серебро).

Российская команда на награждении. Слева направо: Егор Лифарь, Владимир Романов, Рамазан Рахматуллин, Михаил Анопренко

«Ребята хорошо выступили. Но есть и что доработать, — отметил Михаил Тихомиров. — У кого-то было хорошо с придумыванием идей, но плохо с аккуратным написанием кода. А у кого-то наоборот. Надо, чтобы все было хорошо. У двоих из ребят есть еще несколько лет для участия в IOI, и мы теперь еще лучше понимаем, что с ними делать».

Мастер Йода рекомендует:  Как правильно установить шаблон на DLE

Бонусы

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

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

Итоги разных стран на IOI

Среди лидеров Международной олимпиаде из года в год остаются Китай, США, Республика Корея, Иран и Россия.

Таблица с результатами российских сборных за последние 5 лет и сравнение с другими странами

Год, место Участники от России Их баллы Призеры и Россия
2020, Цукуба, Япония Рамазан Рахматуллин 383 1. Китай
Владимир Романов 353 2. Республика Корея
Михаил Анопренко 326 3. США
Егор Лифарь 294 4-5. Россия и Белоруссия
2020, Тегеран, Иран Владимир Романов 373 1. Япония
Денис Шпаковский 350 2. Китай
Егор Лифарь 310 3. Россия
Александра Дроздова 275
2020 (Казань, РФ) Владислав Макеев 557 1. Китай
Михаил Путилин 531 2. Россия
Григорий Резников 432 3. Иран
Станислав Наумов 370
Денис Солонков 390
Александра Дроздова 363
Михаил Анопренко 335
Асхат Сахабиев 312
2015, Алма-Ата, Казахстан Михаил Ипатов 561 1-4. Южная Корея, Китай, Россия, США
Владислав Макеев 505
Михаил Путилин 498
Николай Будин 335
2014, Тайбэй, Тайвань Николай Калинин 556 1-2. Китай, США
Николай Сивухин 454 3-5. Австралия, Россия, Иран
Константин Семенов 388
Никита Уваров 365

По числу золотых медалей IOI Россия находится на втором месте после Китая, опережая США, Польшу и Республику Корея.

Страна Принимала IOI Золото Серебро Бронза Итого
Китай 2000 81 26 12 119
Россия 2020 58 38 12 108
США 2003 49 34 16 99
Польша 2005 40 39 30 109
Республика Корея 2002 39 38 26 103

На студенческих соревнованиях по спортивному программированию ICPC список стран-лидеров похожий, но Россия уже сильно опережает другие страны. С 2000 года российские студенты на ICPC завоевали 32 золотые медали. Для сравнения: студенты из Китая всего 13 раз удостаивались золота за этот период, европейские участники без учета России — 11, США — всего 6.

Казалось бы, странно: на студенческих олимпиадах наши ребята выступают намного лучше, в чем же дело на школьных соревнованиях? Алексей Малеев считает, что все дело в разнице системы подготовки и дефиците кадров в учительской среде. «Разрыв в уровне преподавания информатики в российских школах огромный. Москва выставляет иногда по 70 человек на заключительный этап Всероса, а есть регионы, от которых и одного человека не могут отправить. Но даже московские школьники порой не добираются до такого учителя, который мог бы вытащить их на абсолютное чемпионство в мире», — объясняет он.

Он также пояснил, что в России очень сильное университетское сообщество, и многие студенческие тренировки проводятся совместными усилиями. Есть международные сборы по спортивному программированию Moscow Workshops ICPC. Сильные тренеры из разных вузов, имена которых у всех на слуху, ездят по сборах в разные города и тренируют студентов. А у школьников такого практически нет. Они большую часть времени готовятся локально в своем городе, в своей школе. И тут уже все упирается в то, повезет или нет с учителем.

«Надо дать возможность школьникам из любого уголка России учиться у сильнейших педагогов. И параллельно готовить сильных тренеров, переманивать лучших специалистов из индустрии в преподавание. Это не только даст возможность стать абсолютными лидерами IOI, но и в перспективе поможет развитию IT-отрасли в нашей стране», — заключил Малеев.

Russian Code Cups

Интеллектуальные чемпионаты Mail.Ru Group
О проекте

октябрь 2020 —
декабрь 2020

ноябрь 2020 —
декабрь 2020

февраль 2020 —
октябрь 2020

март 2020 —
сентябрь 2020

Единый доступ ко всем чемпионатам

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

Присоединяйтесь к нашей группе ВКонтакте, где вы найдете полезную литературу, мастер-классы, обучающие видео, лучшие тематические конференции, а также первыми узнаете все важные новости о соревнованиях Mail.Ru Group и других российских и международных IT чемпионатах.

Russian Code Cup

19 марта — 10 сентября. Информация по этапам находится на портале чемпионата.

Регистрация участников: в любое время на сайте.

Для спортивных программистов

Самое масштабное в мире русскоязычное соревнование по спортивному программированию. Это «гоночная трасса» для самых быстрых умов, на которой можно проверить свои навыки в состязании с сильнейшими соперниками и заявить о себе на всю IT-среду. За несколько лет чемпионат привлек более 12 000 программистов со всего мира. Призовой фонд 2020 года составит 750 000 р.

Последние новости RCC

Завершился отборочный раунд Russian Code Cup 2020. Результаты, условия и разбор задач, а также тесты к ним уже доступны на странице чемпионата.

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

16 апреля 2020 г.

Результаты, условия и разбор задач, а также тесты к ним уже доступны на странице портала. Последний квалификационный раунд будет проведён 29 апреля.

2 апреля 2020 г.

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

ML Boot Camp

21 апреля 2020 — 21 мая 2020


Регистрация участников: в любое время на сайте

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

Data Science и Machine Learning с начала 2010-х годов считаются одними из самых привлекательных, высокооплачиваемых и перспективных профессий. На нашей платформе у вас есть возможность научиться решать задачи по машинному обучению и анализу данных, участвовать в контестах и выигрывать ценные призы.

Последние новости ML

С 15 июня по 15 июля пройдет чемпионат ML Boot Camp V, имеющий название AgeHack. В этот раз соревнование организовано компанией Mail.Ru Group совместно с Insilico Medicine в сотрудничестве с Республиканским центром электронного здравоохранения при Министерстве здравоохранения Республики Казахстан. Чемпионат посвящен поиску решения для борьбы со старением.

Завершён чемпионат ML Boot Camp IV с задачей c секретом. Итоговые финальные результаты.

20 апреля 2020 г.

21 апреля стартует Machine Learning Boot Camp IV — уже четвёртое состязание по машинному обучению и анализу данных от Mail.Ru Group! Соревнование проходит онлайн в течение одного месяца, и необходимо решить всего лишь одну задачу. Приглашаем вас принять в нём участие! Лучшие участники будут приглашены в Mail.Ru Group для собеседования на позиции, связанные с анализом данных!

19 марта 2020 г.

Завершился этап «По мотивам онлайн-игр» ML Boot Camp III.

Russian AI Cup

Даты скоро будут анонсированы.

Регистрация участников: в любое время на сайте

Как для начинающих, так и для опытных программистов

Ежегодный чемпионат по программированию искусственного интеллекта на примере игровых стратегий. На текущий момент прошло уже 3 сезона игр: первая игра 2012 года — CodeTanks — участники программировали искусственный интеллект для танков, которые сражались в виртуальном пространстве. В 2013 году в игре CodeTroopers участники создавали интеллект для отряда бойцов, а в 2014 году — CodeHockey — для хоккейной команды. В чемпионате уже приняло участие более 5000 программистов из более чем 17 стран. Тематика игры 2020 года пока держится в секрете.

Последние новости RAIC

6 ноября 2020 г.

Мы рады приветствовать всех участников открытого бета-тестирования Russian AI Cup: CodeWizards 2020! Бета-тест продлится до 23:59 13 ноября. Обращаем ваше внимание на то, что в этот период нами могут вноситься существенные изменения в правила, систему оценки и любые другие аспекты чемпионата.

15 октября 2020 г.

Напишите искусственный интеллект для управления волшебником, соревнуйтесь с другими участниками в чемпионате! Подробное описание задачи можно найти в разделах Чемпионат «CodeWizards» и Правила.

Russian Design Cup

Даты скоро будут анонсированы.

Регистрация участников: в любое время на сайте

Дизайнеры и проектировщики интерфейсов

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

Последние новости RDC

24 октября 2020 г.

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

15 октября 2020 г.

Мы получили столько заявок, что не ожидали сами. Внимательно проверив список участников (сложа руки не сидим), мы поняли, что конкуренция будет невероятной. И одного главного приза мало. Лучшие должны быть достойно награждены. Поэтому дополнительные призы — в студию.

10 октября 2020 г.

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

26 сентября 2020 г.

Три этапа с заданиями от крупных российских и международных компаний. Десять увлекательных недель. Новый вызов. Знакомство в оффлайне. Моднейшая строчка в портфолио. Мак Про, наконец. Пора участвовать!

Началась регистрация на пятый ежегодный чемпионат по спортивному программированию Russian Code Cup

Russian Code Cup (RCC) ежегодно собирает несколько тысяч русскоговорящих участников со всего мира. Они сражаются за звание не только самого талантливого, но и самого быстрого программиста, поскольку решение оригинальных и сложных задач чемпионата оценивается сразу по двум критериям: качество и скорость. Russian Code Cup даёт молодым программистам прекрасную возможность продемонстрировать свое мастерство, получить признание профессионального сообщества и обратить на себя внимание крупных IT-компаний.

В этом году RCC начнётся с «разогревающего» раунда, который стартует 15 марта в 13:00. Результаты этого этапа не учитываются в следующих турах; он проводится для того, чтобы участники могли размяться и оценить свои силы перед основными раундами чемпионата.

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

В ходе первых двух этапов участники соревнуются онлайн на сайте Russian Code Cup. Три квалификационных раунда стартуют 28 марта, 25 апреля и 31 мая, причём программисты, которым не повезло в первом квалификационном туре, могут попытать удачу в следующих. В отборочный тур, назначенный на 14 июня, пройдут по 200 лучших участников из каждого квалификационного раунда. А 50 программистов, показавшие при отборе наилучшие результаты, померяются силами в финале. С каждым этапом сложность задач будет возрастать, и в финале будут предложены наиболее трудные из них. Итоговый раунд состоится 19 сентября.


Победитель, продемонстрировавший в течение чемпионата самые высокие результаты по скорости и качеству решения задач, получит денежный приз в размере 300 тыс. рублей; обладатели второго и третьего места — 150 тыс. и 90 тыс. рублей соответственно. Программистам, занявшим с четвертого по десятое места, достанется по 30 тыс. рублей. Кроме того, все 50 финалистов получат футболки с символикой чемпионата, а 600 участников, прошедших в отборочный тур, — онлайн-сертификаты, подтверждающие их квалификацию.

Зарегистрироваться на RCC можно на сайте cups.mail.ru. Этот ресурс объединяет все IT-соревнования, ежегодно проводимые Mail.Ru Group – Russian Code Cup, чемпионат по программированию искусственного интеллекта Russian AI Cup, соревнование для разработчиков приложений, игр и интернет-сервисов Russian Developers Cup.

В прошлом году победителем Russian Code Cup 2014 стал Геннадий Короткевич из НИУ ИТМО (в позапрошлом году он занял в чемпионате второе место). Серебряным призёром был признан Пётр Митричев (также являющийся победителем Russian Code Cup 2013). Третье место досталось Егору Куликову.

Russian Code Cup снова бросает вызов программистам

13 марта 2020

Крупнейший российский чемпионат по спортивному программированию Russian Code Cup 2020 стартует 19 марта. Талантливые программисты со всего мира вновь будут соревноваться в правильности и скорости решения задач и поборются за призовой фонд в размере 750 тысяч рублей.

Для участия в чемпионате необходимо зарегистрироваться на сайте Russian Code Cup. Соревнования пройдут онлайн. С 19 марта стартует предварительный раунд: участники смогут ознакомиться с платформой и оценить свои силы в решении одной типичной задачи. Участие в этом раунде необязательно, а его результаты не влияют на итоги следующих.

Основная программа Russian Code Cup традиционно состоит из трех этапов: три квалификационных раунда (2 апреля, 16 апреля и 29 апреля), отборочный раунд (14 мая) и финал (10 сентября). На каждом этапе участникам предстоит решить от четырех до восьми разноплановых задач. Те, кому не повезло в первом квалификационном раунде, могут попытать удачи в следующих. В отборочный тур пройдут по 200 лучших участников с каждой квалификации, а в финале сойдутся 50 лучших программистов.

Победителю чемпионата достанется главный денежный приз в размере 150 тыс. рублей. За второе и третье место конкурсанты получат 100 и 65 тыс. рублей соответственно.

Russian Code Cup 2012: подробный разбор задач с первой квалификации

27 мая завершился первый этап олимпиады Mail.Ru Group по программированию Russian Code Cup 2012. Всего в RCC’12 приняло участие более тысячи человек, из которых 200 лучших вышло в полуфинал соревнования, в отборочный раунд. Победителем первого квалификационного раунда стал студент мехмата ННГУ Владислав Епифанов из Нижнего Новгорода. Участниками было направлено 3391 решение, из которых 1066 были приняты системой как верные. 634 человека или 63% от общего числа участников, решили хотя бы одну задачу.

Russian Code Cup — индивидуальное соревнование по спортивному программированию, ежегодно проводимое Mail.Ru Group. Оно традиционно состоит из трех этапов: в начале лета проходят три квалификационных раунда, затем лучшие принимают участие в отборочном туре, первые пятьдесят победителей отборочного тура соревнуются в финале. Личного присутствия потребует только последний из них, остальные же проводятся онлайн. Все финалисты будут отмечены ценными подарками, а приз участнику, занявшему первое место, составит 10 000 долларов. За второе и третье место полагаются 5 000 и 3 000 долларов.

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

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

«Параллелепипед»

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

Тут следовало вспомнить, что параллелепипед — это фигура, основанием которой служит параллелограмм — четырехугольник, у которого стороны попарно параллельны. У параллелепипеда есть три размерности в 12 ребрах — длина, ширина и высота. Следовательно, необходимо ответить на вопрос, есть ли среди входных данных ровно три группы по четыре одинаковых числа.

Чтобы понять это, необходимо отсортировать все числа и убедиться, что получилось три группы по четыре одинаковых числа (одинаковых по крайней мере внутри каждой группы). Если это так, выводить yes, иначе — no.

Попыток сдать задачу «Параллелепипед» было 1479, из которых 639 – успешных (43%). Эта задача оказалась наиболее доступной – число попыток более чем в два раза больше, чем на других задачах, высокий процент успешности.
RussianCodeCup.Ru: постановка задачи
RussianCodeCup.Ru: разбор задач

«Перестройка»

Вторая задача была посложнее.

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

Эта задача предполагает некоторые знания из области теории графов. Вершинами у нашего графа являются города, ребрами — дороги. В теории графов есть понятие связности графа — наличия пути из любой вершины в любую. В данном случае изначально мы имеем граф неизвестной связности, а в итоге должны получить граф обязательно связный. Есть понятие компоненты связности графа — это максимальное по включению множество связанных между собой вершин. Соответственно число компонент связности — это количество несвязанных между собой групп вершин. Например, в случае, если ребер графа (=дорог) нет вообще, число компонент связности равна количеству вершин (=городов). Также введем понятие «моста» — ребра, удаление которого делает граф несвязным, то есть делит его на несвязанные части.

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

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

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

Следовательно, в этом простейшем случае ответ — ноль вариантов.

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

Сначала нужно найти, какие ребра являются «мостами» — ведь при удалении этих ребер мы приводим все к первому, рассмотренному выше варианту. Добавить их же назад мы не можем, так как по условиям задачи добавить можно только там, где ребер не было. Поскольку в итоге мы должны получить связный граф, добавленное ребро должно соединять вершины из разных компонент связности — делать из несвязного графа связный. Две группы из N и M вершин можно связать между собой NxM способами. Следовательно, число реформ у нас получится NxMxC, где C = число ребер без учета тех из них, что являются мостами.

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

Общее количество ребер можно посчитать по числу вершин: n * (n-1))/2 (где n = число вершин). Количество ребер, которые можно добавить, вычисляется вычитанием из общего количества числа имеющихся ребер. Так мы получаем первое слагаемое — число ребер, не являющихся мостами, помноженное на число ребер, которые можно добавить.

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

В итоге для решения этой задачи необходимо знание следующих алгоритмов из теории графов:

  • подсчет количества компонент связности;
  • нахождение мостов;
  • подсчет количества вершин с каждой стороны от моста.

Нахождение количества компонент связности

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

Алгоритм нахождения мостов основывается на поиске «циклов» — альтернативных путей между вершинами. Если такого пути не обнаруживается, то ребро является мостом.

Этот алгоритм можно модифицировать, чтобы находить число вершин с разных сторон от моста.

Попыток сдать задачу «Перестройка» было 621, из которых 137 – успешных (22%).

«Война»


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

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

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

Фактически задача сводится к разбиению массива чисел на монотонные отрезки так, чтобы произведение их длин было максимально. Понятно, что если большой отрезок можно разделить на несколько подотрезков, то произведение длин будет больше, чем длина большого отрезка. Это можно сделать при длине отрезка больше трех: если n ≥ 4, то 2(n — 2) = 2n — 2 ≥ n.

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

Для этого необходимо перебрать, какой длины отрезок нужно взять (1, 2 или 3), проверить, что на нем последовательность не возрастает или не убывает, и выбрать из подходящих вариантов максимум.

Для восстановления ответа нужно воспользоваться стандартной идеей: восстанавливать с конца, пользуясь информацией об оптимальной длине последнего отрезка для данного префикса.

Попыток сдать задачу «Война» было 879, из которых 184 – успешных (21%).

«Джавайское оружие»

«С древности у каждого джавая был набор из трех видов оружия: лазерный меч, лазерная сабля и лазерный ножик для намазывания масла на хлеб (вдруг джавай проголодается).

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

Длина ножика — d1, длина сабли — d2, длина меча — d3 должны быть простыми числами;

  • d1 ≤ d2 ≤ d3;
  • (d1 + d2) 2 − 1 делится на d3;
  • (d2 + d3) 2 − 1 делится на d1;
  • (d3 + d1) 2 − 1 делится на d2.

Компания «Dart Generics Industries» продает любой набор джавайского оружия по его номеру в лексикографическом порядке. А именно, упорядочим все джавайские наборы по неубыванию d1, при равном d1 по неубыванию d2, а при равных d1 и d2 по возрастанию d3 и пронумеруем их в этом порядке от 1 до бесконечности. Тогда по заданному k можно купить k-й набор в этом порядке.

Джавай Anykey хочет купить k-й набор. Подскажите ему размеры его оружия»

Покажем, что из условий, наложенных на длины оружия, следует, что d1 = d2. Пусть никакие три числа не равны, тогда d1 2 − 1 = (d1 + d2 + 1)(d1 + d2 — 1) делится на d3, так как d3 простое, один из множителей делится на d3.

Пусть, например, (d1 + d2 + 1) делится на d3. Из условия d1 2 -1 = (2d2 + d1 + 1) 2 -1 = 4d2 2 + 4d2 + 4d1d2 + d1 2 + 2d1. По условию это число делится на d1, значит 4d2 2 + 4d2 делится на d1. Значит либо d1 = 2, либо d1 = d2, либо d1 = d2+1.

Применяя аналогичные рассуждения к третьему условию, получаем, что либо d2 = 2, либо d1 = d2, либо d2 = d1+1. Из всех пар этих условий совместны только d1=d2 и d1=2, d2=3. Но в последнем случае подобрать подходящее d3 не удается. Значит d1=d2.

Аналогично рассматривается случай (d1 + d2 — 1) делится на d3.

Обозначим d1=d2 как p. Следовательно (p + p) 2 -1 = (2p — 1)(2p+1) делится на d3, а так как оно простое и наибольшее, оно может быть равно только (2p-1) или (2p+1). Следовательно, все тройки должны иметь вид (p,p,2p-1) или (p,p,2p+1). Поскольку по условиям задачи первое простое число находится в числе первых 60000 тысяч, оно не превышает 10 7 . Следовательно, при таких ограничениях можно применить решето Эратосфена — алгоритм поиска простых чисел.

Принцип алгоритма поиска простых чисел «по Эратосфену» заключается в следующем. К примеру нужно найти простые числа в промежутке от 1 до некоторого N 7 . Создаем массив на N элементов и заполняем его значением «true». Затем последовательно проходим по нему до корня из N, и везде, где встречаем true, вычеркиваем все кратные ему числа до N. На первом шаге вычеркиваются все четные числа (потому что первое простое — 2), на втором — все кратные тройке и т.д.

Попыток сдать задачу «Джавайское оружие» было 303, из которых 126 – успешных (42%).

«Этикетка»

Пожалуй, эта задача была самой сложной из всех, хотя объяснение у нее, вероятно, одно из самых простых.

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

Проблема заключалась в том, что эта цивилизация не пользовалась знаком переноса. Как только строка заканчивалась, чтение просто продолжалось со следующей строки. При расшифровке книг это не доставляло никаких неудобств, однако у этикетки есть существенное отличие от книги — этикетка наклеивалась на бутылку так, что получался цельный цилиндр, на котором по кругу был написан текст. При чтении текста следовало начать читать первую строку от места склейки, после достижения места склейки перейти на вторую строку, после этого на третью и так далее. Но ученым пока не удается определить место, где этикетка была склеена! Так что вместо текста пока имеется только набор строк одинаковой длины k, состоящих из букв и символов «.», которые использовались этой цивилизацией вместо пробелов.
К счастью, кроме самой этикетки имеется словарь, в котором перечислены все возможные слова, которые использовались этой цивилизацией. Теперь по этим данным вам необходимо определить, сколько существует вариантов местонахождения склейки. Более формально, вам необходимо определить, сколько существует неотрицательных значений t Напоминаем, что следующий тур состоится в это воскресенье, 2 июня, в 11:00. Необходима предварительная регистрация. Задачи каждого следующего тура, вероятно, будут попроще, но количество попыток попасть в отборочный становится все меньше. Торопитесь!

SavePearlHarbor

Ещё одна копия хабора

Отборочный раунд Russian Code Cup 2014: итоги и разбор задач

В прошедшее воскресенье состоялся отборочный раунд Russian Code Cup 2014. В нем участвовало 802 программиста, показавшие лучшие результаты в четырех квалификациях. В этом этапе участникам предстояло за 3 часа решить шесть задач, что на один час и на одну задачу больше, чем в квалификационных раундах. Да и задачи были существенно сложнее, чем предыдущие. За время соревнования из 802-х только 444 участника смогли решить хотя бы одну задачу. Всего было отправлено 3271 решения, из них правильных 1402.

Больше всего решений на GNU C++ — 1516.
Решений на Java 7 — 333.
Решений на Java 8 — 106.

Первым задачу A решил Геннадий Короткевич (tourist) за 2:52 минуты. Геннадий так же быстрее всех решил задачи В, С и D на 7:05, 24:29 и 13:05 минутах соответственно. Задачу E первым решил Дмитрий Егоров (Dmitry_Egorov) на 40:59 минуте. Задача F стала одной из самых сложных за всю историю Russian Code Cup — из всех участников ее решили правильно только три человека, и первым задачу F решил победитель RCC 2013 Петр Митричев (Petr) за 2:25:46.

Первым со всеми задачами справился Павел Кунявский (PavelKunyavskiy) за 2 часа 47 минут. Всего 6 задач решило 3 человека, 5 и больше задач решили 100 человек. Последним в заветные top 50 попал Роман Билый (RomaWhite), сдавший пятую задачу через 2 часа 30 минут после начала.

За волю к победе отметим Егора Куликова (Egor), который вошел в топ 50, сдав одну из задач с 7 попытки. А также Петра Митричева (Petr), который, не придумав как решить задачу C, отказался от попыток ее решить, первым решил самую сложную задачу F. А потом, вернувшись к задаче C, сдал ее за 4 минуты до конца и занял в итоге 3 место.

Территориальное распределение участников в этом раунде было следующим:

Россия 515
Украина 112
Беларусь 77
Казахстан 26
США 17
Армения 8
Узбекистан 8
Швейцария 6
Германия 4
Латвия 4
Австрия 2
Болгария 2
Великобритания 2
Грузия 2
Молдова 2
Польша 2
Республика Сингапур 2
Азербайджан 1
Аргентина 1
Ирландия 1
Канада 1
Кипр 1
Литва 1
Республика Корея 1
Словакия 1
Турция 1
Швеция 1
Япония 1

При этом впервые в Russian Code Cup были участники, не знающие русского языка из Австрии, Аргентины и Японии! Как признался один из них, условия задач раунда он переводил через сервисы онлайн перевода.

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

Запишем формулу температуры воды, если мы смешиваем холодную воду из сосуда объёмом ci и горячую воду из сосуда объёмом hj: T = p / q = (C·ci + H·hj) / (ci + hj) Преобразовав эту формулу, получим, что (H·q — p) / (p — C·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 равно 10 5 ).

При представлении 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)).

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

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

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

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

Очевидно, что если длина перестановки равна 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).

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

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

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

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

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

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

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

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

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

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

Заметим, что изложенное решение работает пока за t 2 . Для более быстрого решения следует рассуждать в терминах производящих функций. Обозначим f(x) = f x 0 + f1 x 1 +… + ft x t + …, где 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 многочлен по модулю x t+1 , и перемножив count(x) с результатом. Взятие обратного многочлена по модулю x t+1 можно выполнить за время O(t log t) с использованием быстрого преобразования Фурье. Итоговое время работы: O(t log t).

Добавить комментарий