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

Поздравляю всех этих заслуженных в нашем сообществе людей с днем рожденья!

Будучи недавно в офисе КРОК (да-да, есть планы по продолжению сотрудничества:)), я услышал о другом интересном конкурсе. Он называется "Летающие роботы". Сам я далек от робототехники, но тема эта интересная и популярная. С удовольствием публикую небольшой анонс.

О конкурсе

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

Для участия нужно представить на конкурс беспилотное автономно летающее устройство-робот (он же коптер, он же дрон, он же беспилотник). Можно действовать двумя способами:

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

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

Подробнее о задании

Схема полигона

Описание полигона

Возводится под открытым небом, представляет собой открытую «коробку» по типу дворовой хоккейной площадки.

• Размер коробки — 50 на 25 метров, высота стенок и перегородок внутри периметра -приблизительно 3 метра, перегородки радиопрозрачные.
• Полигон сверху затянут сеткой, препятствующей вылету роботов за его пределы. Разбит на две части перегородкой с проходом шириной не менее 3 метров.
• Точка старта и посадки помечены крестами, имеют инвертированную окраску (белый крест на черном фоне и черный крест на белом), нанесены краской на круг из пластика/фанеры, диаметр круга 3 метра.
• Положение точки посадки изменяется перед каждым полетом, перемещается в случайное место в пределах выделенной для этого зоны (на схеме показана пунктирной линией).
• Отдельно выделена зона препятствия, в пределах которой в случайное место перед каждым полетом устанавливается перегородка, блокирующая две трети ширины «коридора».

Важный факт — возможна стабилизация по GPS.

Задание

• Взлететь из точки старта и долететь до точки посадки, успешно миновав препятствие.
• Снова взлететь, вернувшись в точку старта, опять миновав препятствие.

Сесть в точке посадки можно в любое место обозначенного круга (диаметр — 3 метра). На схеме пунктирной линией обозначен примерный маршрут автономного полета.

Приз!

Главный приз конкурса — денежное вознаграждение в размере 1000000 рублей.

Подробные условия конкурса читайте в на сайте КРОК.

Всем привет!

До Codeforces Round #135 (Div. 2) осталось всего несколько часов. Вся подготовка раунда сосредоточена в городе Петрозаводске, где проходят традиционные сборы по подготовке к ACM-ICPC. Сегодня здесь выходной, многие поехали на экскурсию в Кижи, а я с Gerald-ом готовим для вас контест. Виталик Aksenov239 Аксенов не остался равнодушен и предложил свою помощь, за что ему большое спасибо. Спасибо Маше Delinur Беловой за перевод условий.

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

Всем удачи и удовольствия от раунда!

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

• Задачи на online-алгоритмы, т.е. такие алгоритмы, которые не читают все входные данные сразу, а могут читать их только по мере своей работы. Простой пример: задано множество из n чисел. Надо обработать n запростов. Каждый запрос содержит элемент множества, до обработки запроса надо вывести минимум чисел в множестве, а потом удалить этот элемент. Естественно, после последнего запроса множества станет пустым. Если решать эту задачу как офлайн-задачу, то можно решать ее <<с конца>>, обрабатывая запросы от последнего к первому (т.е. фактически добавляя в множество элементы). В таком случае решение совсем тривиально. Онлайн-формулировка не позволяет решению прочитать очередной запрос до обработки предыдущего, что вынуждает писать решение, обрабатывающее запросы в прямом порядке. В таком случае необходима структура данных типа std::set в С++ для поддержания минимума в динамическом множестве.
• Задачи на игры. В таком случае участнику надо написать программу, которая делает какие-то ходы, а ответы на эти ходы зависят от того, как именно сходила программа. Здесь в качестве игр могут выступать не только типичные игры, но и «угадайки». Например: было загадано число от 1 до n. Программа участника пытается его угадать, а интерактивный модуль отвечает больше или меньше загаданное число очередной попытки участника. Требуется отгадать число, сделав не более попыток. В качестве решения здесь участник может использовать бинарный поиск.

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

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

Пакет задачи состоит из:

1. Одного или нескольких тестов, возможно с ответами (на картинке это файл file.in и file.a). В качестве ответов обычно используются выводы интерактора при тестировании модельных авторских решений.
2. Интерактивного модуля (сокращенно, интерактора) — специальной программы, которая <<общается>> с решением.
3. Тестирующей программы (чекера).
4. Крайне желательно наличие авторского решения.
5. Крайне желательно наличие специальной программы — валидатора. Валидатор получает на вход текст теста (file.in) и возвращается с кодом возврата 0 тогда и только тогда, когда тест корректен. Здесь есть хитрость, так как по-идее еще надо валидировать непосредственно данные, отосланные решению (стрелочка от интерактора к решению stdout-stdin). В настоящий момент такую валидацию лучше встраивать в интерактор.

Как происходит запуск решения и его оценка в интерактивной задаче.

1. Сначала запускается в <<связке>> одновременно решение и интерактор. На решение как обычно наложены традиционные ограничения на время и память. На интерактор похожие ограничения тоже должны быть наложены, но довольно лояльные (например, 15 секунд/256MB). Интерактор запускается с теми же параметрами командной строки, что и обычный чекер — именем файла для чтения описания теста (в схеме file.in), именем файла для вывода информации о результатах взаимодействия (в схеме file.out), именем файла с ответом (в схеме file.a). Возможны дополнительные классические параметры testlib, если интерактор написан на нем.
2. Ждем события, что один из процессов завершился (сам собой или был прерван).
3. Первый случай, первым завершилось решение:
   • Если завершилось по причине превышения каких-то ограничений, то сразу возвращаем вердикт Time Limit Exceeded, Memory Limit Exceeded или Idleness Limit Exceeded (последний, если программа продолжительное время вообще не расходовала процессорное время).
   • Если завершилось с кодом возврата неравным 0, то возвращаем Runtime Error.
   • Если завершилось благополучно и с кодом 0, то продолжаем ждать пока завершится интерактор.
4. Второй случай, первым завершился интерактор:
   • Если завершился по причине превышения каких-то ограничений, то сразу возвращаем вердикт Judgement Failed.
   • Если завершился с кодом возврата неравным 0, то обрабатываем его как обычный чекер:
     • код 1: возвращаем вердикт Wrong Answer,
     • код 2: возвращаем вердикт Wrong Answer (или Presentation Error, если такой вердикт поддерживается),
     • код 3 или любой другой: возвращаем Judgement Failed.
   • В случае любого из ненулевых кодов возврата, вывод интерактора на стандартный поток ошибок (stderr) следует считать комментарием тестирующей системы о тестировании на этом тесте.
   • Если интерактор вернулся с кодом 0, то ждем завершения решения. Применяем к нему пункты о превышении ограничений или ненулевом коде возврата из предыдущего пункта. Таким образом, считаем, что оно благополучно завершилось с кодом 0.
5. Ждем завершения второго процесса, считаем, что он благополучно завершился с кодом 0, иначе вердикт очевиден.
6. Запускаем чекер, передавая ему в качестве аргументов file.in (описание теста), file.out (вывод интерактора) и, если есть, file.a (файл ответа). Таким образом, командная строка запуска имеет вид: check file.in file.out или check file.in file.out file.a. Чекер запускаем с лояльными ограничениями (например, 15 секунд/256 MB). Ждем завершения процесса. Если ограничения были превышены, то возвращаем Judgement Failed. В противном случае смотрим на код возврата:
   • код 0: возвращаем вердикт OK,
   • код 1: возвращаем вердикт Wrong Answer,
   • код 2: возвращаем вердикт Wrong Answer (или Presentation Error, если такой вердикт поддерживается),
   • код 3 или любой другой: возвращаем Judgement Failed.
7. В случае любого из ненулевых кодов возврата, объединенный вывод чекера на стандартный поток вывода (stdout) и ошибок (stderr) следует считать комментарием тестирующей системы о тестировании на этом тесте.

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

1. PCMS2 считает, что чекер всегда должнен возвращаться с кодом 0, а его вердикт считывается из специального XML-файлика.
2. EJUDGE имеет свою собственную систему кодов возврата, несовместимую с общеприятой.

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

Вот пример простого интерактора под testlib.h, который делает задачу A+B интерактивной:

#include "testlib.h"
#include <iostream>

using namespace std;

int main(int argc, char* argv[])
{
    setName("Interactor A+B");
    registerInteraction(argc, argv);
    
    // reads number of queries from test file
    int n = inf.readInt();
    for (int i = 0; i < n; i++)
    {
        // reads query from test file
        int a = inf.readInt();
        int b = inf.readInt();

        // writes query to the solution, endl makes flush
        cout << a << " " << b << endl;

        // writes output file to be verified by checker later
        tout << ouf.readInt() << endl;
    }

    // just message
    quitf(_ok, "%d queries processed", n);
}

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

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

Закончились сборы Саратовского государственного университета "Сазанка 2012". Спасибо всем участникам! Поздравляем победителей:

• 1 место: Московский авиационный институт (Белоусов, Журавлев, Сафронов);
• 2 место: Уральский федеральный университет (Красносельских, Меркурьев, Назаров);
• 3 место: Санкт-Петербургский государственный университет (Новиков, Малиновский).

Мне кажется получилось полезно и интересно :) Пишите в комментария впечатления и отзывы. Удачной дороги всем гостям Саратова!

Вот фотографии (кликабельны):

Есть чем похвалиться. Если посчитать количество активных участников как это делает TopCoder (хотя бы одно участие в rated-event за полгода), то на Codeforces таких 9389. Кстати, на TopCoder аналогичный показатель чуть меньше — 9380. Как говорится — мелочь, а приятно :)

Год назад нас было 5160. На данный момент распределение по цветам такое:

Всем привет!

Фотографии с прошедшего финала VK Cup 2012 можно найти в группе http://vk.com/vkcup

Решил собрать здесь несколько ссылок:

• статья на ленте
• мой пост на Хабре
• колонка от Владислава Цыплухина
• Посты Alex_KPR: 0, 1, 2 и 3
• недописанный обзор от YuukaKazami

Сегодня состоится финал VK Cup 2012, Финал! Мы желаем удачи всем участникам, а болельщикам — насладится интересным соревнованием. На открытии финала кубка в своей приветственной речи генеральный директор "В Контакте" Павел Дуров анонсировал апгрейд призового фонда. Я начинаю по-настоящему жалеть, что я не участник! Финалисты поборются за:

• 1 место — $30000
• 2 место — $20000
• 3 место — $10000
• 4-5 места — $2000
• 6-10 места — $1000

Удачи! Желаем только положительных эмоций. На старт! Внимание! ...

UPD: Соревнования завершено! О его ходе и церемонии закрытия, я полагаю, совсем скоро напишет Alex_KPR. Всем спасибо за участие и интерес! Вот полные результаты.

Поздравляем победителей. Тройка лидеров:

• sevenkplus (Yuzhou Gu) Китай
• s-quark (Qinshi Wang) Китай
• tourist (Геннадий Короткевич) Беларусь

UPD: Как вы уже успели заметить, 16-го июля в 19:00 стартует неофициальная онлайн-версия финала VK Cup 2012. Любой желающий может принять участие и почувствовать себя на месте финалиста. Раунд будет нерейтинговым. Если вы решали или в какой-то степени знакомы с задачами, пожалуйста, воздержитесь от участия. Все задачи появятся в архиве и будут доступны всем желающим.

Всем привет!

Сегодня, 14-го июля, состоится пробный тур финального раунда чемпионата VK Cup 2012. Функциональность Codeforces сильно ограничена как для внешних посетителей, так и для участников финала. Пожалуйста, сохраняйте спокойствие :-)

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

MikeMirzayanov и жюри VK Cup 2012

Всем привет!

Совсем скоро состоится финал чемпионата по программированию VK Cup 2012. Оргкомитет и жюри работают не покладая рук, чтобы мероприятие понравилось участникам.

Напоминаю, что финал пройдет с 13-го по 16-е июля, а примут участие в нем лучшие 50 участников по результатам VK Cup 2012 Раунд 3. Как только мы окончательно поймем, у кого получается приехать, список финалистов будет опубликован.

Вот некоторая информация из штаба организационного комитета, которой нельзя не поделиться. Участники финала будут размещены в прекрасном отеле Кемпински, в самом центре Санкт-Петербурга на берегу Мойки. Отель находится в пешей доступности от офиса ВКонтакте, так что никаких изнурительных автобусов и знакомства с пробками Питера! Будете смотреть фотографии отеля – обратите внимание на ресторан на крыше с видом на Дворцовую площадь.

Точное расписание еще не определено, кое-что зависит от времени приезда участников и сложности задач (да-да, финальный раунд, возможно, будет иметь неклассическую продолжительность), но общий план такой:

• 13 июля: Заезд, ужин, знакомства и развлечения.
• 14 июля: День в основном будет посвящен неофициальному развлекательному мероприятию Code Game Challenge (special for VK Cup 2012). Также в этот день планируется непродолжительный пробный тур. Вечером, в дополнение к отличному ужину, состоится Code Game Challenge Show — просмотр турнира стратегий на большом экране.
• 15 июля: Основной день соревнования (удачи!). Вечером награждение победителей и чествование всех финалистов (уверен, все останутся довольны :));
• 16 июля: Отъезд домой.

ВКонтакте и Codeforces очень рады большому интересу школьников и студентов к чемпионату VK Cup 2012. Несмотря на то, что на соревнование приглашались только молодые программисты (возраст участников – не более 23 лет), зарегистрировались на чемпионат без малого 6000 участников из 91 страны! Мы очень рады, что почти все прошедшие в финал нашли возможность приехать в Санкт-Петербург. Победителей ждет достойная награда, тем более что мы рады сообщить: призовой фонд чемпионата увеличен. Есть за что побороться и приложить максимум усилий для победы!

• 1 место — $20000
• 2 меcто — $10000
• 3 место — $5000
• 4-5 место — $2000
• 6-10 место — $1000

Легкой дороги финалистам,
Оргкомитет и жюри VK Cup 2012

Вопросы и ответы

• По каким правилам будет проходить финальное соревнование? Финал будет раундом по оригинальным правилам Codeforces, продолжительность финала — 2.5 часа. Возможно, будет использована динамическая оценка стоимости задач.
• На каком компьютере мы будем писать контест? Каждому участнику будет предоставлен специально подготовленный ноутбук, подключенный к монитору, внешней мыши и клавиатуре. Пользоваться своими ноутбуками нельзя. Разрешается привезти с собой USB-клавиатуру, если она не содержит сложного функционала, который может дать преимущество на контесте.
• Какая ОС? Что будет стоять на рабочей станции? Мы планируем предоставить участникам возможность выбрать операционную систему — Windows или Ubuntu. На обеих системах будет установлен широкий спектр разнообразных программ, мы надеемся удовлетворить все основные требования.
• Можно ли использовать заготовки? Нет, но на основном соревновании вы можете использовать код, который вы напишите на пробном туре или CodeGame.

Немного фотографий

Общая информация

Саратовский государственный университет в первой половине августа проводит международную летнюю студенческую школу по программированию. Продолжительность школы — десять дней, школа пройдет с 1-го по 11-е августа.

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

Школа пройдет в живописном месте, на одной из саратовских баз отдыха на берегу Волги. Участники будут расселены в уютных номерах по 2-4 человека и обеспечены трехразовым питанием. На территории базы имеется собственный пляж и спортивные площадки.

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

Примерные темы лекций, на все темы будет обширная практика (возможны изменения):

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

Организационный сбор составляет 16000 рублей на одного участника. Кроме того, каждая команда или индивидуальный участник должны привезти с собой ноутбук (с поддержкой WI-FI). В стоимость оргвзноса включается проживание на базе отдыха, трехразовое питание, учебная программа.

Заинтересованным участникам и командам необходимо пройти предварительную регистрацию на сайте http://acm.sgu.ru/sazanka-2012/ до 15 июня 2012 года. Не откладывайте регистрацию, так как количество мест ограничено. Полностью и аккуратно заполните форму регистрации, введите информацию по каждому члену команды.

Дополнительную информацию можно получить по телефону 88452522711 или по электронной почте mirzayanovmr[символ с кодом 64]gmail.com.

О Саратовском государственном университете

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

• 2002 г. Титул чемпионов Европы, комплект серебряных медалей на чемпионате мира ACM-ICPC 2002.
• 2003 г. Комплект серебряных медалей на чемпионате мира ACM-ICPC 2003.
• 2006 г. Титул чемпионов мира, чемпионов Европы, комплект золотых медалей на чемпионате мира ACM-ICPC 2006.
• 2007 г. Комплект серебряных медалей на чемпионате мира ACM-ICPC 2007.
• 2008 г. Чемпионы России и NEERC.
• 2009 г. Комплект золотых медалей на чемпионате мира ACM-ICPC 2009.
• 2010 г. Комплект серебряных медалей на чемпионате мира ACM-ICPC 2010.
• 2011 г. Комплект серебряных медалей на чемпионате мира ACM-ICPC 2011.

Кроме того, студенты и тренеры СГУ неоднократно становились участниками финальных этапов соревнований TopCoder, Google Code Jam и Facebook Hacker Cup. Саратовский государственный университет входит в лучшие университеты мира по рейтингам TopCoder, Codeforces и рейтингам на основе результатов участия в международном студенческом командном чемпионате ACM-ICPC.

Руководитель Центра олимпиадной подготовки
Саратовского государственного университета, тренер команд. 

М.Р. Мирзаянов

Так как на сайте Russian Code Cup нет приличного дорешивания и тем более виртуальных контестов, только что прошедшая первая квалификация добавлена в тренировки. Итак, встречайте в тренировках 2012 Russian Code Cup, квалификация 1.

UPD: Добавили вторую квалификацию — 2012 Russian Code Cup, квалификация 2.

UPD: Добавили третью квалификацию — 2012 Russian Code Cup, квалификация 3.

Всем привет!

Пришла пора опубликовать фотографии с прошедшего чемпионата. Напоминаю, 27-го апреля в гостеприимном офиса КРОК прошел финал Чемпионата Москвы и МО. Так как Чемпионат был открытым, то присутствовали не только москвичи — были участники из других городов России и даже из ближнего зарубежья.

Ниже много мегабайт фотографий!

Теперь в пост можно совсем просто вставлять фотоальбомы из Picasa. Альбом должен быть публичным, доступным для просмотра по ссылке. Вставлять надо вот так [photoalbum:URL], например так [photoalbum:https://picasaweb.google.com/114907919772955385569/2012?authuser=0&feat=directlink].

Просьба публиковать фотоальбомы, посвященные соревнованиям по программированию и вокруг этого, интересные широкой публике.

Всем привет!

Сегодня вас ждет раунд по старым-добрым ACM-ICPC правилам. Да, это будет рейтинговый контест для второго дивизиона, а участники из первого дивизиона смогут принять участие вне конкурса.

Задачи для вас делали Nerevar, natalia, MikeMirzayanov и Edvard, а Delinur перевела задачи. Спасибо всем за помощь!

Желаю удачи!

UPD: Рейтинг будет обновлен позже.

Всем привет!

Напоминаю, что 3 апреля в 12:00 начнется квалификационный раунд Открытого чемпионата Москвы и МО по программированию (КРОК).

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

Раунд продлится 24 часа, но это не значит, что мы призываем вас все это время провести за решением задач. Мы надеемся, что большинство участников справятся с задачами (или с большинством задач) за более короткий срок. Такая длительность раунда выбрана для того, чтобы каждый нашел удобное время для участия.

До окончания раунда категорически запрещается публиковать где-либо условия задач/решения/какие-либо мысли и соображения о них. Запрещено общаться на тему задач, обсуждать условия и проч. Будьте честными и пусть в Раунд 1 пройдут сильнейшие. Когда квалификация будет завершена, можно будет обсуждать задачи и решения.

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

Желаем удачи и удовольствия от решения задач!

UPD: Соревнование закончено! Спасибо за участие. В скором времени будут удалены нарушители порядка и результаты станут официальными. Неофициально — проходной балл в Раунд 1 составляет 1950 баллов.

UPD 2: Из таблицы результатов были удалены явные читеры и люди, кому не исполнилось 18 лет на момент регистрации. Если ваши результаты были удалены по ошибке, свяжитесь со мной для прояснения ситуации. Теперь проходной балл составляет 1900 баллов.

Всем привет!

Добро пожаловать на VK Cup 2012 Уайлд-кард раунд 2!

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

В основном конкурсе этого раунда участвуют те, кто официально прошел в VK Cup 2012 Раунд 2, но не прошел в VK Cup 2012 Раунд 3. По результатам VK Cup 2012 Уайлд-кард раунд 2 лучшие 25 участников завоюют право участия в VK Cup 2012 Раунд 3. Все остальные члены сообщества могут принять участие вне-конкурса, just for fun.

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

Удачи! Пусть победит сильнейший!

P.S. Я не могу не оставить это здесь. Во время соревнования категорически запрещается публиковать/обсуждать алгоритмы решения задачи, подходы к решению, делиться какими-либо выводами о задаче. Нельзя делиться результатами (в том числе просто сообщать баллы) запуска своих решений на каких-либо тестах. Запрещено публиковать инструменты для упрощения или автоматизации процесса решения задачи.

И да, огромное спасибо Nickolas за великолепную задачу!

UPD: Контест закончен, тестирование завершено. Поздравляем первые 25 мест — результаты, вы вышли в VK Cup 2012 Раунд 3!

Добрый день.

VK Cup 2012 Round 2 будет проведен в двух редакциях:

• официальной VK Cup 2012 Раунд 2 — для прошедших в этот раунд участников VK Cup 2012 и участников из первого дивизиона (последние будут участвовать вне конкурса),
• спец. редакции для второго дивизиона VK Cup 2012 Раунд 2 (неофициальная редакция для Div. 2) — для участников из второго дивизиона, кто не является официальным участником VK Cup 2012 Раунда 2.

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

Всем привет.

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

Зачем вообще нужны разные стоимости задач? Как верно подметил RAD, они в самом деле необходимы для контестов, где решение может упасть на системном тестировании или около того. Например, Вася решил простую A, а Петя решил простую A и очень сложную B. У Пети A упала, а B он решил попозже (и может не с первой попытке). В таком случае, если задачи были равны по стоимости, то Петя займет место ниже Васи, что как-то несправедливо.

На Codeforces задачи оцениваются в кратное 500 количество баллов: 500, 1000, 1500 и т.д. Обычно мы стараемся подбирать 5-задачные наборы, разнообразные по сложности. В таком случае, каждый квалифицированный на контест найдет себе задачи по силам и такие, над которыми надо подумать. Традиционный комплект задач включает в себя задачи 500-1000-1500-2000-2500.

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

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

Идея такая:

• если задачу решили от половины участников до всех участников раунда, то она стоит 500 баллов,
• если задачу решили от четверти до половины участников участников раунда, то она стоит 1000 баллов,
• если задачу решили от одной восьмой до четверти, то она стоит 1500 баллов,
• и так далее.

Конечно, речь идет о максимальной стоимости задачи. Падение в минуту вычисляется по традиционной формуле X/250 (учитывается X на момент построения текущего положения участника). Более формально в таблице:

При подсчете числа участников учитываются те, кто сделал хотя бы одну попытку в этом раунде. Начальная стоимость (до какой-либо попытки по ней) любой задачи — 3000.

Вот и все! Как видите идея очень проста и не перегружена формулами и подробностями. Чтобы как-то с ней познакомиться сегодня по ссылкам "Результаты участников" для контестов по правилам Codeforces будут открываться результаты, посчитанные по таким правилам. Это временное изменение, вскоре мы вернем все назад.

Сегодняшний Codeforces Round 113 (Div. 2) будет использовать такие экспериментальные правила. Мы гарантируем, что задача A будет в нем именно та, которую мы считаем наиболее простой. Порядок остальных задач — случайный. Удачи!

Динамическая стоимость задач с шагом 250 баллов (поддержка реализована в марте 2015 г.)

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

Компания КРОК приглашает талантливых и прогрессивных специалистов (от 18 лет) принять участие в Открытом чемпионате Москвы и Московской области по программированию.Чемпионат проводится на базе проекта Codeforces. В работе жюри и технического комитета принимает участие Саратовский государственный университет.

Соревнование будет состоять из нескольких дистанционных отборочных этапов (3-4, 6 и 20 апреля) и финального тура, который пройдет 27 апреля в Москве в офисе компании КРОК. На финале чемпионата также состоится игровой раунд. Участники финала не обязательно должны быть жителями Москвы и Московской области, но дорога до места проведения финала организуется и оплачивается ими самостоятельно.

Победители чемпионата получат ценные призы: 100000 рублей за первое место и ноутбуки Apple MacBook Pro за второе и третье места. Участник, занявший первое место в игровом раунде, будет награжден Apple MacBook Air.

Для того чтобы принять участие в чемпионате необходимо пройти регистрацию на странице http://www.crocok.ru/championship/ до 4 апреля 2012 г.

Подробности о проекте можно также узнать на сайте http://crocok.ru в разделе "Чемпионат по программированию". Официальный язык чемпионата — русский. Задачи будут публиковаться на двух языках — русском и английском.

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

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

Если кто-то из участников засабмитит свои решения в дорешивание этого контеста, будет отлично — так проверим ограничения времени/памяти и отсутствие разных багов при импорте.

Еще один вопрос к участникам — как вы оцениваете сложность контеста по шкале 5 звезд? Описание можно посмотреть в тренировках (тултипы на звездах существующих тренировок).

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

Общие сведения о раунде

1. Для участия в раунде необходимо зарегистрироваться. Регистрация на раунд открывается за 6 часов до его начала и заканчивается за 5 минут до его начала, если в информации по раунду не оговорено другое.

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

3. Продолжительность раунда составляет 2 часа, если в информации по раунду не оговорена другая продолжительность.

4. Участникам для решения предоставляется 5 задач, если в информации по раунду не оговорено иное количество задач.

5. Условия задач доступны на двух языках: русском и английском.

6. Условия всех задач становятся доступными для прочтения в момент начала раунда.

7. Перед началом соревнования все зарегистрированные участники случайным образом делятся на комнаты. В каждую комнату попадают примерно 40 участников.

Вопросы по задачам

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

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

3. Жюри соревнований может ответить на заданный вопрос в произвольной текстовой форме.

4. Ответ "без комментариев" означает, что вопрос не соответствует пункту 2, жюри считает, что вопрос не относится к условию задачи или ответ на него содержится в условии задачи или в правилах соревнований.

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

Решение задач

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

   • С/С++
   • Delphi/Pascal
   • Java
   • С#
   • Python
   • Ruby
   • PHP
   • OCaml
   • Haskell
   • Perl
   • Scala
   • D
   • Go

2. Требования к программам:

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

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

4. Участник может видеть результаты проверки решений на соответствующей вкладке системы соревнования.

Компиляция решений

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

   • MinGW GNU C++ 4
   • MinGW GNU C 4
   • Microsoft Visual C++ 2010
   • Free Pascal 2
   • Delphi 7
   • C# Mono 2
   • Java 6, 7
   • Ruby 1
   • Python 2
   • PHP 5
   • Haskell GHC 6
   • Objective Caml 3
   • Scala 2
   • Perl 5
   • Go 1
   • MS C# .NET 4

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

3. Компиляция и запуск решений производятся под ОС Windows. Переводы строк задаются парой символов #13#10. После последней строки файла или входного потока (непосредственно перед его концом) находится перевод строки.

4. Если произошла ошибка компиляции, то участнику сообщается результат проверки <Ошибка компиляции>, а также лог компилятора.

5. Размер файла с исходным кодом не должен превышать 64 килобайт.

6. Тестирующая система использует компиляторы командной строки для компиляции решений. Строки компиляции для разных компиляторов приведены в таблице:

Проверка решений

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

2. Результат проверки решения на претестах сообщаются участнику сразу же после проверки.

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

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

5. Тестирование производится путем последовательного запуска программы на каждом из тестов.

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

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

2. Если результатом проверки решения является "Ошибка компиляции", "Отказ тестирования" или решение не прошло первый претест, то это решение никак не учитывается при подсчете результатов.

3. Решение по одной и той же задаче можно отправлять несколько раз.

4. Решение, прошедшее все претесты, называется подтвержденным решением данного участника по данной задаче.

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

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

   • каждую минуту стоимость задачи уменьшается: стоимость задачи падает на X/250 балла в минуту (где X первоначальная стоимость задачи), например, задача первоначальной стоимости 500 баллов дешевеет со скоростью 2 балла в минуту;
   • балл участника за задачу равен текущей стоимости задачи в баллах за вычетом штрафа;
   • штраф определяется как количество решений этого участника по этой задаче, сделанных ранее, умноженное на 50 баллов;
   • балл участника за задачу не может быть меньше, чем 30% от изначальной стоимости задачи.

Взломы

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

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

3. За успешный взлом участник получает 100 баллов. За неуспешный взлом участник получает штраф в 50 баллов.

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

   • задача больше не считается предварительно им решенной
   • его предварительный балл за эту задачу становится равным 0
   • тест из взлома добавляется в набор претестов по этой задаче для этого конкретного участника

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

Что можно делать, а что нельзя

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

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

3. Разрешается пользоваться любыми источниками информации в интернете (но копировать-вставлять чужой код нельзя).

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

5. Участникам запрещается общаться на темы, связанные с задачами, с кем бы то ни было, в том числе с другими участниками. Разрешается только задавать вопросы жюри через систему (см. раздел "Вопросы").

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

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

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

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

Таблица текущих результатов

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

2. Все промежуточные результаты являются неофициальными.

Финальное тестирование и окончательные результаты

1. После завершения соревнования публикуются результаты тестирования решений участников на основном наборе тестов.

2. На основном наборе тестов тестируются подтвержденные решения, то есть те, которые одновременно:

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

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

4. За решенную задачу участник получает балл, равный предварительному баллу его решения за эту задачу. Балл за нерешенную задачу равен 0.

5. Результатом участника считается сумма баллов за все решенные им задачи и баллов за взломы.

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

7. Тестирование осуществляется на компьютерах Core 2 Duo E6750, 2.66 Ghz, 3Gb памяти.

Интеллектуальная собственность

1. Нижеприведенные правила используются каждый раз, когда для раунда нет специальных правил. Участники сохраняют за собой владение всеми правами интеллектуальной и промышленной собственности (включая моральные права) после предоставления решения.

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

3. Участники предоставляют решение на условиях «как есть», без предоставления каких-либо гарантий или условий либо ни прямого, ни косвенного характера, включая, без ограничений, никаких гарантий или условий на названия, никаких гарантий относительно коммерческого использования или пригодности для тех или иных целей и ненарушения прав.

Просьба сообщить в комментариях, если мы забыли какие-то аспекты. Если после анализа комментария, текст будет обновлен, а соответствующий комментарий станет неактуальным, то такие комментарии мы будем через некоторое время скрывать (чтобы не захламливать ленту комментариев неактуальными вопросами/замечаниями).

В разделе тренировки опубликован контест, подготовленный Саратовским ГУ, для сборов в Зимних Петрозаводске (2011-2012). Этот же контест был этапом кубка главы Карелии и этапом открытого кубка.

Контест рекомендуется участникам уровня финала чемпионата мира или претендующих на подобные успехи.

А я не устаю призывать других авторов публиковать свои контесты в разделе тренировки!

Всем привет!

Напоминаю, что 9 марта в 12:00 начнется второй квалификационный раунд чемпионата VK Cup 2012.

Это последний шанс пройти в Раунд 1. В Раунд 1 проходят все участники, набравшие не меньше баллов, чем участник на 800-ом месте. Вас ждет несколько несложных задач, примерно расположенных по возрастанию сложности. Во время квалификации задачи тестируются системой только на претестах, а системное тестирование состоится после окончания квалификации (которая идет сутки). Претесты не покрывают все возможные случаи входных данных, так что тщательно тестируйте свои программы! Взломов, падения стоимости задач во время квалификации нет.

Раунд продлится 24 часа, но это не значит, что мы призываем вас все это время провести за решением задач. Мы надеемся, что большинство участников справятся с задачами (или с большинством задач) за более короткий срок. Такая длительность раунда выбрана для того, чтобы каждый нашел удобное время для участия.

До окончания раунда категорически запрещается публиковать где-либо условия задач/решения/какие-либо мысли и соображения о них. Запрещено общаться на тему задач, обсуждать условия и проч. Будьте честными и пусть в Раунд 1 пройдут сильнейшие. Когда квалификация будет завершена, можно будет обсуждать задачи и решения.

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

Желаем удачи и удовольствия от решения задач!

UPD: Тестирование завершено, проходной балл равен 3500 3450. Поздравляем всех, кто прошел в Раунд 1!

UPD 2: Мы удалили явных читеров и проходной балл уменьшился до 3450!