Всем привет!

Как уже многие знают, 13 сентября в СГАУ состоялся отборочный контест на четвертьфинал мира по программированию. Разумеется, мы не только развесили плакаты о мероприятии в стенах родного университета, но и сделали множество репостов в контакте, а также пообщались лично с тренерами других вузов, так что популяризация ACM в Самаре вышла на новый уровень. Помимо этого, в отличие от некоторых других организаторов некоторых других отборочных соревнований, мы неизменно выкладываем наши контесты в публичный доступ на тренировки Codeforces, где абсолютно любой желающий мог бы их решать. Так что уже в эту субботу, 14 ноября, в 11.00 MSK все желающие смогут проникнуться неповторимой атмосферой нашего отбора.

Контест пройдет в тренировках Codeforces, будет нерейтинговым и будет длиться 5 часов. Задачи готовили craus и Shlakoblock.

А вот полный список наших предыдущих контестов:

• 2012, V Самарская областная межвузовская олимпиада по программированию
• 2012, Отборочный контест СГАУ на четвертьфинал ACM ICPC
• 2013, VI Самарская областная межвузовская олимпиада по программированию
• 2013, Отборочный контест СГАУ на четвертьфинал ACM ICPC
• 2014, VII Самарская областная межвузовская олимпиада по программированию
• 2014, Отборочный контест СГАУ на четвертьфинал ACM ICPC
• 2015, VIII Самарская областная межвузовская олимпиада по программированию

Всем привет!

Всего через два дня, 16 ноября в 00:00 официально стартует ставшее уже ежегодным соревнование Russian AI Cup — Российский кубок по программированию искусственного интеллекта. В этом году темой соревнования являются гонки без правил. Участникам предстоит не только научить свой кодемобиль быстро и правильно ездить, но также и помешать соперникам добраться до финиша раньше вас. Бета-тест мероприятия уже идёт, и если вас не пугают недоработки системы и возможные изменения правил, то вы можете начать создавать свою стратегию прямо сейчас. Не волнуйтесь выступить неудачно: рейтинг всех участников перед релизом будет сброшен к начальному значению.

Что?

Russian AI Cup — крупнейший в России чемпионат по программированию искусственного интеллекта и третье по счёту открытое соревнование для талантливых IT-специалистов, являющееся частью стратегии Mail.Ru Group по формированию и развитию конкурентной в мировых масштабах российской IT-индустрии.

Официально поддерживаются следующие языки программирования: C++, C#, Java, Pascal, Python 2 и Python 3. Однако, как и все прошлые годы, мы готовы поддержать языковые пакеты, разработанные сообществом. В этот раз, благодаря Марату Якупову и Александру Гришину, вы можете создать стратегию на языке Scala.

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

Простейшая стратегия, способная доехать до финиша, состоит всего из десятка строк. Вот пример на языке Java:

import model.*;

import static java.lang.StrictMath.*;

public final class MyStrategy implements Strategy {
    @Override
    public void move(Car self, World world, Game game, Move move) {
        double nextWaypointX = (self.getNextWaypointX() + 0.5D) * game.getTrackTileSize();
        double nextWaypointY = (self.getNextWaypointY() + 0.5D) * game.getTrackTileSize();

        double angleToWaypoint = self.getAngleTo(nextWaypointX, nextWaypointY);
        double speedModule = hypot(self.getSpeedX(), self.getSpeedY());

        move.setWheelTurn(angleToWaypoint * 32.0D / PI);
        move.setEnginePower(0.75D);

        if (speedModule * speedModule * abs(angleToWaypoint) > 2.5D * 2.5D * PI) {
            move.setBrake(true);
        }
    }
}

Когда?

• Песочница: с 9 ноября до 20 декабря открыта для всех желающих; первая неделя будет проходить в режиме бета-тестирования, в этот период возможны нестабильная работа системы и существенные изменения в правилах, а 16 ноября в 00:00 рейтинг в Песочнице будет сброшен до первоначального состояния
• Раунд 1: 28–29 ноября.
• Раунд 2: 5-6 декабря.
• Финал: 12–13 декабря.

Призы

В этом году лучшие стратегии, помимо традиционной "яблочной" продукции, смогут претендовать на специальные призы от партнёров мероприятия — компаний WD и Kingston. Также все участники Раунда 2 получат футболку, а все финалисты — толстовку с символикой соревнования.

Полезные ссылки

• о Russian AI Cup
• o CodeRacing
• Быстрый старт
• Правила

Удачи!

Привет, Codeforces!

13 ноября 2015 года в 18:00 MSK состоится первый учебный раунд Educational Codeforces Round #1 для участников из первого и второго дивизионов.

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

Учебные раунды будут нерейтинговыми (мы продолжаем обсуждать этот вопрос). Соревнование будет проводиться по немного расширенным правилам ACM ICPC. На решение задач у вас будет два часа. После окончания раунда будет период времени длительностью в один день в течении, которых вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования. Таким образом вы можете локально тестировать решение, которое хотите взломать, или, например, запустить стресс-тест. Подробнее об учебных раундах написано здесь.

Подготовкой учебных раундов занимаюсь я, Эдвард Давтян из команды Saratov SU Daemons. Идеи задач были придуманы совместно с MikeMirzayanov. Спасибо моему сокоманднику danilka.pro за тестирование и вычитывание условий и MikeMirzayanov за системы Codeforces, Polygon и идею учебных раундов.

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

Good luck and have fun!

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

UPD2: Пожалуйста не используйте недетерменированные генераторы. Например не стоит писать в языке С++ srand(time(NULL)) и потом использовать функцию rand(). Ваш генератор должен всегда генерировать один и тот же тест.

Всем привет!

Во-первых, приглашаю вас принять участие в неофициальном тестовом раунде Testing Round 12. Дело в том, что команда Codeforces внесла множественные изменения в платформу (о чем чуть позже), и все мы хотим быть уверенными, что основная функциональность осталась без изменений. Этот раунд будет иметь сокращенную длительность 1.5 часа, состоять из 3 (может, и 4) задач, которые вы могли уже где-то и видеть ранее. Цель его — с одной стороны, протестировать систему, а с другой — скрасить вечер среды. Конечно, раунд будет нерейтинговым.

Теперь самое главное. В ближайшую пятницу (да, 13-го ноября) Codeforces стартует еще одну линейку раундов. Мы назвали их учебными раундами (Educational Rounds). На примере моих студентов в Центре олимпиадной подготовки программистов Саратовского государственного университета (ЦОПП-СГУ) я регулярно замечаю, что даже те из них, кто имеет заметный прогресс в результатах на раундах, зачастую имеют неширокий кругозор в плане стандартных тем и идей, не знакомы с многими методами. Дело в том, что раунды обычно избегают каких-то фольклорных или классических тем, в результате страдает кругозор очередного поколения участников.

Мы рады объявить о старте серии учебных раундов! Они будут проходить с регулярностью 2-4 раунда в месяц.

Вот их характерные черты:

• продолжительность классическая — 1.5 — 2.5 часа;
• ставят перед собой в большей степени тренировочную и образовательную цель, чем соревновательную;
• допускается использование не только задач, но и упражнений;
• будут переиспользованы полезные, пусть даже и известные идеи с целью познакомить с ними широкий круг участников;
• часто формальные тексты условий;
• нерейтинговые (возможно, пока);
• будем пробовать проводить в режиме ACM-ICPC (если будут большие очереди, возможно, поменяем подход);
• те результаты, что получаются после окончания раунда, являются предварительными;
• после окончания раунда будет период (длительностью в сутки) открытых взломов — любой посетитель Codeforces может попытаться взломать любое полное решение задачи из прошедшего раунда (как с контеста, так и прошедшее в дорешивании); при такого вида взломах доступен текст решения (можно копировать текст и, например, стрессить);
• все успешные взломы из предыдущего пункта будут добавлены в официальный набор тестов, и немногим более чем через сутки после окончания раунда будет сделано перетестирование всех полных решений;
• только после окончания перетестирования подводятся окончательные результаты раунда; результаты раунда подводятся отдельно по дивизионам;
• наши возможности по проработке таких задач ограничены, поэтому в самом деле наборы тестов от жюри ожидаемо могут оказаться неполны — мы надеемся на ваши взломы!

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

Пока подготовка задач к этим раундам будет сосредоточена в Центре олимпиадной подготовке программистов СГУ, основную работу по задачам будет выполнять Эдвард Edvard Давтян. Пожелаем ему удачи, энтузиазма и сил!

До встречи на Testing Round 12, а чуть позже и на Educational Codeforces Round 1.

Добрый день, Codeforces!

Рад сообщить, что в это воскресенье, 8го ноября в 19:30 MSK состоится Codeforces Round #330 для участников обоих дивизионов.

Задачи для вас уже не в первый раз с удовольствием придумывали и готовили Александр fcspartakm Фролов и я, Данил Сагунов. Мы говорим спасибо координатору Codeforces Глебу GlebsHP Евстропову за существенную помощь в подготовке задач, Михаилу MikeMirzayanov Мирзаянову за системы Codeforces и Polygon, Марии Delinur Беловой за перевод условий на английский язык, а также Владиславу winger Исенбаеву и Александру AlexFetisov Фетисову за тестирование и прорешивание задач раунда.

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

Желаем всем удачи и высокого рейтинга!

UPD. Еще раз приносим свои извинения за задачу Cdiv2/Adiv1 — авторское решение неправильно работало в случае нечетных n. Мы очень надеемся, что остальные задачи контеста оказались (или окажутся в дорешивании) для вас полезными и интересными.

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

Победители первого дивизиона:

1. jcvb
2. 2222
3. KAN

победители второго дивизиона:

1. Tagrimar
2. fsps60312
3. uhateme

Разбор задач можно найти здесь.

UPD. Задача Cdiv2/Adiv1 была исправлена, и теперь имеет то условие и решение, которое предполагали авторы. Задача вернулась в соревнование и доступна для дорешивания.

Добрый день, дорогие пользователи Codeforces!

2 ноября начался заочный этап X Открытой олимпиады школьников по программированию. В контест добавлен первый пакет из пяти задач, остальные задачи будут добавлены позднее. Те из вас, кто знает что такое Открытая олимпиада (она же "заочка") и её правила, могут не читать дальше и сразу переходить на сайт олимпиады :) Первый пакет задач подготовили для вас: Zlobober, romanandreev, snarknews и GlebsHP.

Те, кто раньше в данной олимпиаде не участвовал, могут так же пойти на сайт и прочитать полную информацию там, а в этом посте будут обозначены лишь основные моменты. Олимпиада состоит из двух этапов: заочного и очного. Заочный этап проходит со 2 ноября по 18 января, и традиционно состоит из 10-15 задач различной сложности, тематики и формата. Мы подбираем задачи таким образом, чтобы они были интересны как совсем новичкам, так и "зубрам" олимпиадной информатики. Лучшие n участников (n приблизительно равно 400) будут приглашены на очный этап олимпиады.

Очный этап пройдёт в Москве, ориентировочные даты проведения — 7-8 марта. Площадка проведения — учебный центр нашего генерального спонсора 1С на м. Тимирязевская. Также, благодаря нашему спонсору, участникам оплачивается проживание в гостинице на время проведения олимпиады. Очный этап состоит из двух туров, уровень участников немного превосходит уровень Всероссийской олимпиады по информатике за счёт приезда сильных школьников из ближнего зарубежья. Возможно это прозвучит слишком пафосно, но на наш вкус качество задач олимпиады в последние годы превосходит Всероссийскую олимпиаду и сравнимо с IOI. Олимпиада имеет первый уровень и даёт соответствующие льготы при поступлении.

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

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

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

Любые оставшиеся вопросы смело задавайте в комментариях.

UPD: в контест добавлены четыре новые задачи: F, G, H и I. Для вас их подготовили: thefacetakt, Sender, haku и ipavlov.

UPD2: в контест добавлены последние три задачи: J, K и L. За подготовку задач мы благодарим: romanandreev, Vaness и mingaleg.

UPD3: на сайте олимпиады доступны предварительные результаты и архив олимпиады. Рады сообщить, что Zlobober подготовил для вас разбор задач заочного этапа.

Всем привет!

Завтра в 19.30 по московскому времени состоится Codeforces Round #329, который настоятельно не рекомендуется кому-либо пропускать.

Задачи для вас готовили я и Станислав josdas Наумов. Я уверен, что это не последний раунд, в котором мы являемся авторами. Мы очень надеемся, что вам понравится раунд, и каждый найдет себе задачу по вкусу. Для того, чтобы увеличить вероятность этого события, пожалуйста, прочтите все задачи этого контеста.

Как всегда, благодарим GlebsHP за неоценимую помощь при подготовке контеста, Delinur за перевод условий на английский язык и MikeMirzayanov за потрясающие системы Codeforces и Polygon.

Отдельное спасибо хотим сказать Алексею Саплину, Эрике Шефер, Евгению Казакову, Богдану Трубецкому.

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

Желаю удачи и высокого рейтинга!

UPD1: Разбалловка будет динамической.

UPD2: Разбор задач

Codeforces Round #328 (Div. 2) will take place on October 31, 19:30 MSK, as usual Div. 1 participants can join out of competition.

Problem Setter: Morphy (Alei Reyes)

Coordinator: GlebsHP (Gleb Evstropov)

English to Russian translator: Delinur (Maria Belova)

Codeforces and Polygon: MikeMirzayanov (Mike Mirzayanov)

Hope you enjoy the problem set.

The score distribution will be announced later.

UPD. Score Distribution: 500 — 1000 — 1500 — 2000 — 3000

UPD. Problem Analysis is available

Congrats to the winners!

Div. 2

shamir0xe

lbn187

SuperLoser

Div. 1

uwi

NanoApe

Haghani

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

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

Каждый участник характеризуется величиной рейтинга r_i — целое число (возможно отрицательное). Грубо говоря, чем это значение выше, тем лучше участник выступает в соревнованиях. Рейтинг это подсчитывается/пересчитывается таким образом, чтобы выполнялось равенство:

где P_i, j вероятность того, что i-й участник победит на соревновании j-го. Таким образом вероятность победы одного участника над другим определяется только разностью их рейтингов. Например, если разница рейтингов двух участников равна 200, то побеждает сильнейший с вероятностью примерно 0.75. При разнице рейтинга 400 вероятность возрастает до 0.9.

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

Рассмотрим момент до начала раунда и посчитаем для каждого участника его ожидаемое место (его называют seed_i). Ожидаемое место равно сумме вероятностей по всем другим участникам обойти данного плюс один (плюс один берется из-за 1-индексации):

Например, перед Codeforces Round 318 [RussianCodeCup Thanks-Round] (Div. 1) при рейтинге 3503 ожидаемое место у tourist было примерно 1.7, а у Petr при рейтинге 3029 ожидаемое место было примерно 10.7.

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

Посчитаем для участника среднее геометрическое его текущего места и ожидаемого, пусть эта величина равна m_i. В самом деле, это какое-то среднее значение между ними, оптимистично сдвинутое в сторону меньшего из мест. Найдем (с помощью бинарного поиска) такой рейтинг R, которым должен бы был иметь этот участник, чтобы всё-таки ожидаемо занимать место m_i (среди того же набора участников). Текущий рейтинг участника должен быть изменен так, чтобы стремиться к R. Поэтому, изменение рейтинга участника в раунде вычисляется как d_i = (R - r_i) / 2.

Это почти всё, кроме фазы борьбы с инфляцией. Заметим, что при инфляции богатые становятся еще богаче, поэтому будем бороться именно с этим. Если предположить, что рейтинг был уже посчитан справедливо (то есть каждый участник имеет свой статистически обоснованный рейтинг), то математическое ожидание изменения рейтинга по любому участнику должно быть равно 0. Выберем группу наиболее высокорейтинговых участников раунда (по рейтингу r_i — до начала раунда) и скажем, что сумма их рейтингов должна остаться неизменной. В качестве размера такой группы выбирается эвристическая величина . Если d_i таковы, что их сумма для этой группы не равна 0, то ко всем им (по всем n участникам) прибавляется некоторое значение (вычитается) так, чтобы их сумма по s наиболее высокорейтинговым участникам стала равна 0.

После раунда 327 ограничили этот эффект: сначала к каждому изменению прибавляется величина inc =  - sum(d_i) / n - 1 (то есть d_i меняются), затем прибавляется inc = min(max( - sum(d_i) / s,  - 10), 0). Таким образом, эффект изменения рейтингов из абзаца выше ограничен падением каждого рейтинга не более чем на 10.

Кстати, для любого логически непротиворечивого рейтинга должны выполняться несколько инвариантов:

• если участник A имел рейтинг хуже участника B и выступил хуже него на текущем раунде, то и его рейтинг после пересчета должен быть не лучше чем у B;
• если A выступил лучше B, но имел до раунда хуже рейтинг, то ему должны прибавить не меньше единиц рейтинга чем участнику B.

В частности, для обновленного рейтинга Codeforces эти инварианты проверяются на выполнение при любом пересчете рейтинга.

Ознакомиться с используемым кодом можно по ссылке: 13861109.

Здравствуйте, уважаемые участники сообщества Codeforces!

Начиная с Codeforces Round #327, я буду координировать подготовку регулярных раундов и прочих контестов, которые проводятся на платформе Codeforces. Обещаю приложить максимум усилий, чтобы улучшить качество подготовки контестов, хотя это и будет проблематично сделать — Zlobober установил высокую планку. Давайте ещё раз поблагодарим Максима за хорошо проделанную работу!

Завтрашний раунд проводится на задачах Московcкой городской командной олимпиады по программированию среди школьников. Пусть вас не смущает, что это школьное соревнование, — среди участников есть золотой призёр IOI 2015 и несколько кандидатов в сборную России этого года, поэтому мы постарались сделать все задачи интересными, а некоторые ещё и сложными. Уверен, что каждому из вас должна понравиться хотя бы одна задача предстоящего раунда.

Задачи были подготовлены коллективом московских авторов в составе (список пополняется): Zlobober, romanandreev, meshanya, wilwell, glebushka98, timgaripov, thefacetakt, haku, LHiC, Timus, Sender, sankear, iskhakovt, andrewgark, ipavlov, StopKran, AleX. Руководство подготовкой осуществляли ваш покорный слуга GlebsHP и председатель жюри олимпиады Андреева Елена Владимировна.

Отдельно благодарим Delinur за перевод условий на английский язык и stella_marine за вычитку.

В каждом дивизионе будет предложено для решения пять задач, разбаловка будет опубликована позднее (не будем нарушать эту традицию).

UPD. Время раунда. Обратите внимание, что во многих странах мира этой ночью переводят часы, а в России не переводят — не пропустите случайно раунд :)

UPD2. Обратите внимание, разбаловка как бы намекает, что надо прочитать все задачи! Div1.: 750-1000-1250-1750-2500 Div2.: 500-1000-1750-2000-2250

UPD3. Результаты раунда и разбор будут опубликованы позднее, когда завершится официальное соревнование.

UPD4. Системное тестирование завершено, доступны окончательные результаты, открыто дорешивание задач. Поздравляем победителей в первом дивизионе:

1. Endagorion
2. JoeyWheeler
3. sdya
4. RAD
5. -XraY-

UPD5. Появился разбор.