Приглашаю на чемпионат по программированию
Привет!
Мы с 2012 года проводим всероссийские чемпионаты по программированию вместе с Codeforces. Участвовать можно с 18 лет. Гражданство в целом не важно, у нас всегда были гости из Казахстана, Украины, РБ и других стран, но язык турнира — русский. Например, в 2013 году было 3500 человек, и первое место взял «терминатор» tourist, а пятое — вот этот парень rng_58 из Японии:
Правила — «олимпиадные» задачи, которые нужно решить, плюс «взломы» чужих решений за счёт подбора своих нестандартных наборов данных. Индивидуальный зачёт, в призах 100 тысяч рублей за первое место, 70 тысяч и 50 тысяч — за второе и третье. Как обычно, будет отдельный игровой раунд в финале — нужно будет написать AI для сражения с AI других участников (в прошлом году был хоккей, до этого — битва магов). Приз игрового раунда — ноутбук.
Сроки
Квалификация 16 марта, отборочный раунд 18 марта, финал на 50 участников — 15 апреля в нашем офисе в Москве. В прошлом году градация количества участников по мере отбора к финалу была такая: 3500, 2000, 400 и 50 на финал. Средний возраст финалиста — 24 года.
Для финалистов из РФ предусмотрены компенсация билетов в Москву (до 10 тысяч рублей).
Сложность
Сложность будет расти по мере приближения к финалу, но правила раундов остаются одинаковыми.
Ход турнира
Отборочные проходят на платформе Codeforces удалённо, как обычно все турниры там. Финал предполагает физическое участие: все игроки соберутся в одном зале. Там есть Wi-Fi, розетки и локальные машины с набором сред разработки, которые покрывают все языки, предусмотренные правилами. Практика показывает, что мы разворачиваем всего пару таких машин — обычно участники прибывают со своими ноутбуками.
Оттуда вы заходите на сайт под своим аккаунтом (как обычно), получаете задачи, решаете их. Закрыв задачу (после этого работать с ней уже нельзя), можно смотреть чужие исходники уже отправленных решений и «ломать» их, фактически, выявлением багов на автотесте, то есть подстановкой сложных наборов входных данных. За удачный взлом — бонус, за неудачный — штраф.
Пример задачи из 2013 года:
Вам заданы n участков памяти, для каждого участка известна его длина в байтах a[i]. Вам надо разместить в памяти как можно больше структур данных из возможных m, для каждой структуры известен ёё размер b[j] в байтах. То есть в оптимистичном случае получится разместить все m структур, а в пессимистичном — не одной. Известно, что все b[j] — это степени двойки. Каждая структура должна находиться в одном участке памяти, но участок может вмещать несколько структур. Конечно, каждый байт может принадлежать не более чем одной структуре.
Ваша программа должна быстро работать (уложиться в пару секунд) для любых n и m не превосходящих 10^6. Все a[i] и b[j] — целые числа от 1 до 10^9. Среди значений a[i] и b[j] могут быть одинаковые значения (хоть все).
Вот здесь есть больше задач.
Варианты решения:
Сначала рассмотрим частный случай, когда среди значений b[j] нет единиц. Значит все значения b[j] — четные (раз уж это степени двойки). В таком случае нечетные участки памяти не смогут быть израсходованы полностью (сумма четных — четна). Поэтому мы ничего не потеряем, если из каждого нечетного a[i] вычтем единицу. Таким образом, получаем ситуацию в которой все b[j] и a[i] четны. Но значит все эти значения можно одновременно поделить на 2 и это не изменит ответ! При таком делении могут появиться единичные структуры, и этот случай мы сейчас рассмотрим (а если они не появились, то можно делить всё на два опять).
Если же некоторые b[j] равны 1, то нет причин не попытаться их куда-то разместить. Конечно, в первую очередь их надо определить во все участки памяти нечетной длины (ведь их никак нельзя использовать полностью без единичных структур). Если и после этого остались единичные структуры, то заметим, что если мы одну единичную структуру определим в четный участок, то он станет нечетным. Поэтому туда обязательно будет выгодно определять и еще одну единичную структуру. Таким образом, можно из пар единичных структур насобирать структуры размера 2 и продолжать работать с ними, рассматривая их как единое целое. Если осталась одна без пары, то надо её определить в минимальный положительный a[i].
Так мы добились, что теперь у нас нет структур размера 1, а значит пришли к первому случаю. Единственное, надо помнить из скольки изначальных структур состоит текущая и размещать единичные структуры жадно по этому параметру.
Вопрос-ответ
— Сколько людей зарегистрировалось на момент публикации топика?
Можно посмотреть вот здесь: codeforces.com/croc2016/registrants
— Где точные правила и регистрация?
Вот — codeforces.com/blog/entry/43229
— Задача прошла 19 наборов данных из 20: я получу за неё хоть одно очко?
Нет, не получите. Надо пройти все.
— Я не гражданин России. Можно участвовать?
Да. Но стоит учитывать, что дорогу до Москвы мы оплачиваем только финалистам — гражданам РФ.
— Мне 45 лет, я бородат, студент и живу в Африке. Мне можно?
Участвовать и проходить в финал — да.
— Есть отчёты?
Фотоотчёт и отчёт участника.
И видео:
— Есть ли возможность поучаствовать хотя бы в квалификационных и отборочных раундах, если мне нет 18?
Да, вы сможете биться за рейтинг CF, но в финал вы не пройдёте. По крайней мере, если вам не исполнится 18 полных лет до 15 апреля 2016.
— Что писать в форме регистрации, если я не могу заполнить поле «ВУЗ»?
Пишите «null» или просто заполняйте по ситуации. Ограничений это не накладывает.
— Круто, но я не могу. Когда следующий чемпионат?
Попробуйте принять участие вне конкурса. Если не получится — Чемпионат проходит далеко не последний раз, плюс есть ещё масса конкурсов и контестов. Например, пару лет назад у нас был конкурс летающих роботов с призом в 1 миллион рублей. Также можно следить за нашим корпоративным блогом тут на Хабре — крупные мероприятия будут анонсироваться.
