Привет, Codeforces!

8 апреля 2016 года в 18:00 MSK состоится очередной одиннадцатый учебный раунд Educational Codeforces Round 11 для участников из первого и второго дивизионов.

<Изменения в последенем абзаце>

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

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

Если у вас есть идеи каких-то задач, которые вам кажутся интересными, или может есть уже что-то почти готовое, что вы по каким-то причинам не можете дать на раунд (злой координатор сказал, что задача БАЯН), официальное соревнование (жюри не хочет переграбливать соревнование), можете писать мне.

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

</Изменения в последенем абзаце>

Комплект задач был предложен участниками сообщества. Задачу А предложил Ali Ibrahim C137. Задачу B прислал Srikanth Bhat bharsi. Задача C предложена Mohammad Amin Raeisi Smaug. Задачу D очень давно прислал Sadegh Mahdavi smahdavi4. Задача E является последней (четвёртой) из предложенных пользователем Lewin Gan Lewin. Задача F последняя (если не ошибаюсь третья) из присланных пользователем Kamil Debowski Errichto.

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

Задача F подготовлена пользователем Kamil Debowski Errichto. Остальные задачи подготовил я (Эдвард Давтян). Спасибо Маше Беловой Delinur за проверку английских текстов условий. Задачи вычитывали и тестировали пользователи, предложившие их, соответственно Ali Ibrahim C137, Srikanth Bhat bharsi, Mohammad Amin Raeisi Smaug, Sadegh Mahdavi smahdavi4, Lewin Gan Lewin, Kamil Debowski Errichto. Большое им за это спасибо!

На раунде вам по традиции будут предложено шесть задач. Надеюсь они вам понравятся! В данный момент я рассматриваю возможность повторения задачи E с большими ограничениями, в качестве задачи G. Как вы смотрите на такое?

Good luck and have fun!

P.S.: Тот самый автобус из задачи B.

UPD 1: Взломы идут полным ходом. Разбор задач на русском языке готов.

UPD 2: Соревнование закончено. Поздравляю победителей tribute_to_Ukraine_2022 и uwi! Также поздравляю halyavin с победой в гонке хакеров — 93 взлома!

Привет!

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

Были даже комментарии из серии "я же говорил, что так и будет"

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

    private double getSeed(List<Contestant> contestants, Contestant contestant, int rating) {
        Contestant extraContestant = new Contestant(null, 0, 0, rating);
        double result = 1;
        for (Contestant other : contestants) {
            result += getEloWinProbability(other, extraContestant);
        }
        return result;
    }

Напомню, что эта функция вычисляла ожидаемое место участника, если бы его рейтинг был равен rating. Конечно, она не должна учитывать самого участника, кому мы в данный момент присвоили гипотетической значение рейтинга. Правильный код должен содержать проверку:

        for (Contestant other : contestants) {
            if (other != contestant) {
                result += getEloWinProbability(other, extraContestant);
            }
        }

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

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

Посоветовавшись с tourist и Petr, я пришел с следующему плану действий:

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

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

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

М.

Контест окончен, надеюсь, вам понравилось :-) Разбор задач — здесь. До следующего года!

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

В этом раунде вас ждет 7 необычных задач, на решение которых дается два часа. Раунд будет проводиться по схеме ACM ICPC (без взломов, положение в результатах определяется количеством решенных задач и набранным штрафным временем) и будет нерейтинговым. Решения можно сдавать на любом языке, поддерживаемом Codeforces — если, конечно, иное не оговорено в условии задачи ;-) Чтобы получить представление о том, что вас ждет, можно взглянуть на контесты прошлых лет: 2012, 2013, 2014.

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

Привет, Codeforces!

30 марта 2016 года в 19:05 MSK (время московское) состоится очередной раунд Codeforces #346 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса. Этот раунд будет необычным: будет предложено 7 задач и 2,5 часа на их решение. Надеюсь, что все найдут для себя интересные задачи. Обратите внимание на необычное время начала раунда!

Задачи для вас готовили я (IlyaLos), Эдвард Давтян (Edvard), Данил Сагунов (danilka.pro), Роман Глазов (Roms) и Владимир Петров (vovuh). Хотелось бы сказать большое спасибо Глебу Евстропову (GlebsHP) за помощь в подготовке задач, Марии Беловой (Delinur) за перевод условий на английский и Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon, а так же за помощь в подготовке контеста и идеи нескольких задач.

Разбалловка будет объявлена позднее.

UPD Разбалловка: 500-1000-1000-1250-1500-2000-2500

UPD2 Соревнование завершено! Всем спасибо! Разбор

В понедельник, 28-го марта, в 19:35 будет дан старт Раунду 1 чемпионата по программированию VK Cup 2016! Я (Radewoosh) и Kamil Dębowski (Errichto) подготовили для вас комплект задач к этому раунду.

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

В этом раунде могут принять все те команды, которые прошли квалификацию. Напомним, что из первой квалификации допущены все те команды, что набрали не менее 4800 баллов. Таких оказалось 505. Вторую квалификацию прошли 956 команд, все те, что набрали не менее 500 баллов. Таким образом, принять участие в Раунде 1 могут 1461 команды!

Участников ждет соревнование по правилам классических раундов Codeforces с некоторыми адаптациями:

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

Отметим, что одновременно с официальным раундом чемпионата будут проведены онлайн-трансляции: VK Cup 2016 — Round 1 (редакция для Div. 1) и VK Cup 2016 — Round 1 (редакция для Div. 2). Фактически это будут классические Codeforces-раунды для всех тех из вас, кто не участвует в VK Cup 2016 или не прошел квалификацию.

Все три варианта проведения будут рейтинговыми.

Мы хотим поблагодарить GlebsHP за помощь в подготовке задач и MikeMirzayanov, потому что без него бы не было замечательной платформы Codeforces, где мы соревнуемся и тренируемся.

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

Напомним, что в Раунд 2 пройдут все те команды, которые наберут положительный балл не меньший, чем у команды на 400-м месте.

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

UPD Разбалловка:

For VK: 500 — 750 — 1000 — 1500 — 2000 — 3000

For Div.2: 500 — 1000 — 1500 — 2000 — 2500

For Div.1: 500 — 1000 — 1500 — 2000 — 3000

UPD Разбор уже готов.

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

В чемпионате VK Cup:

1.Never Lucky: subscriber и tourist
2.SobolevTeam: Seyaua и sdya
3.LNU Penguins: witua и RomaWhite
4.Dandelion: Um_nik и sivukhin
5.uıɟɟnɯ ɐuɐuɐq ǝɥʇ ɟo uɹnʇǝɹ╰(º o º╰): enot110 и romanandreev

В Div.1

1.dotorya
2.kcm1700
3.JoeyWheeler
4.KrK
5.Swistakk

И в Div.2

1.osmanorhan
2.nhho
3.fudail225
5.agaga
4.alanM

Отдельное спасибо qwerty787788 и AlexFetisov за тестирование задач, ценные советы и рекомендации!

Добрый день.

26-го марта в 10:00 (московское время) стартует Отборочный Раунд 2 чемпионата Технокубок 2016. Раунд будет длиться два часа, участникам будут предложены 5 задач. По его результатам лучшие 150 участников (но не более 45% от общего числа участников раунда) будут приглашены на финальный этап в Москву. Для регистрации на раунд и участия перейдите по ссылке http://codeforces.me/contests/649. Не забудьте заранее зарегистрироваться на раунд. Впрочем, если забудете — не беда. Через 10 минут после старта будет открыта дополнительная регистрация для опоздавших (ее длительность — 100 минут).

Зарегистрироваться на Отборочный Раунд 2 →
Для зарегистрированных участников олимпиады

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

• короткое описание формата
• полное описание формата

Напоминаем, что регистрация на олимпиаду еще открыта. На кону — дополнительные баллы при поступлении в престижные технические вузы России и ценные призы. Если вы — школьник 8-11 классов и пока не зарегистрировались на Технокубок, то самое время сделать это:

Зарегистрироваться на олимпиаду →

В финал соревнования будут приглашены лучшие 150 участников каждого из отборочных раундов (но не более 45% от общего числа участников раунда).

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

Желаем удачи на олимпиаде,
MikeMirzayanov и команда Технокубка

UPD 1: Раунд будет рейтинговым для всех участников олимпиады "Технокубок", то есть как для официальных участников раунда, так и участников вне конкурса.

UPD 2: Дорешивание доступно в Тренировках: 2016 Технокубок: Отборочный Раунд 2.

Привет, Codeforces!

25 марта 2016 года в 16:00 MSK после продолжительного перерыва состоится очередной десятый учебный раунд Educational Codeforces Round 10 для участников из первого и второго дивизионов. Перерыв, конечно же, связан с большой плотностью соревнований и чемпионатов на Codeforces.

<То же, что и было раньше>

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

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

Если у вас есть идеи каких-то задач, которые вам кажутся интересными, или может есть уже что-то почти готовое, что вы по каким-то причинам не можете дать на раунд (злой координатор сказал, что задача БАЯН), официальное соревнование (жюри не хочет переграбливать соревнование), можете писать мне.

Не стесняйтесь присылать простые (и даже очень простые) задачи (но обязательно интересные). Почти каждый раунд достаточно быстро выбираются кандидаты для задач C, D, E, F, а вот задача A обычно ставится самой последней, когда уже почти всё готово.

</То же, что и было раньше>

Теперь уже традиционно комплект задач был полностью предложен участниками сообщества. Задачу А уже в третий раз предложил пользователь unprost (ну сами понимаете не стоит ждать короткого условия :-)). Задачу B прислал пользователь Smaug. Задача C — ещё одна задача из комплекта, который прислали Bayram Berdiyev bayram, Allanur Shiriyev Allanur, Bekmyrat Atayev Bekmyrat.A. Задачи D и E были предложены Алексеем Дергуновым dalex. Задачу F ещё давно прислал Lewin Gan Lewin.

Благодарю их и всех кто присылает задачи или просто наброски!

Задачи D и E были подготовлены Алексеем Дергуновым dalex. Остальные задачи подготовил я (Эдвард Давтян). Хочу отметить генератор тестов по задаче E, который я писал примерно столько же, сколько решение задачи F. Спасибо Маше Беловой Delinur за проверку английских текстов условий. Задачи тестировали пользователи unprost, Smaug, Aleksa Plavsic allllekssssa, Алексей Дергунов dalex и Lewin Gan Lewin. Большое им за это спасибо!

На раунде вам по традиции будут предложено шесть задач. Надеюсь они вам понравятся!

P.S.: Мне очень нравится задача F, надеюсь увидеть Accepted-ы по ней.

Good luck and have fun!

UPD: Соревнование закончено. Разбор задач готов.

Добрый день.

Теперь пропустить раунд из-за невнимательности при регистрации станет сложнее. В ближайшие раунды в экспериментальном режиме будет запущена функциональность дополнительной регистрации (может надо называть как-то по-другому: расширенной регистрации?).

Это означает, что после окончания периода основной регистрации (как обычно, за 5 минут до старта раунда) будет еще один дополнительный период. Он будет начинаться через 10 минут после старта раунда и закончится через 20 минут, то есть после 30 минут от старта раунда. Роль 10 минут двойная:

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

При регистрации в период дополнительного времени участник автоматически отправляется в случайную из комнат (среди подходящих под его роль).

Добрый день.

23-го марта в 18:00 (московское время) стартует Отборочный Раунд 1 чемпионата Технокубок 2016. Раунд будет длиться два часа, участникам будут предложены 5 задач. По его результатам лучшие 150 участников (но не более 45% от общего числа участников раунда) будут приглашены на финальный этап в Москву. Для регистрации на раунд и участия перейдите по ссылке http://codeforces.me/contests/648. Не забудьте заранее зарегистрироваться на раунд. Впрочем, если забудете — не беда. Через 10 минут после старта будет открыта дополнительная регистрация для опоздавших (ее длительность — 20 минут).

Зарегистрироваться на Отборочный Раунд 1 →
Для зарегистрированных участников олимпиады

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

• короткое описание формата
• полное описание формата

Напоминаем, что регистрация на олимпиаду еще открыта. На кону — дополнительные баллы при поступлении в престижные технические вузы России и ценные призы. Если вы — школьник 8-11 классов и пока не зарегистрировались на Технокубок, то самое время сделать это:

Зарегистрироваться на олимпиаду →

В финал соревнования будут приглашены лучшие 150 участников каждого из отборочных раундов (но не более 45% от общего числа участников раунда).

Второй отборочный раунд будет открыт для всех тех, кто не прошел в финальный этап из первого отборочного раунда. Причина (не участие или недостаточный результат) — не важна. Второй отборочный раунд состоится 26 марта 10:00-12:00.

Желаем удачи на олимпиаде,
MikeMirzayanov и команда Технокубка

UPD 1: Раунд будет являться рейтинговым соревнованием, то есть на основании его результатов будут пересчитаны рейтинги участников.

UPD 2: Соревнование закончено, спасибо за участие! Поздравляем топ-150 с приглашением в Финал олимпиады. Скоро вам будет отослано письмо с формой участника, пожалуйста, не задерживайте с заполнением.

UPD 3: В силу ряда причин дорешивать задачи можно в Тренировках: 2016 Технокубок: Отборочный Раунд 1, приношу извинения за некоторое неудобство.

Добрый день.

21-го марта в 17:00 (московское время) стартует Ознакомительный Раунд 1. Его продолжительность составит двое суток, его результаты не будут как-либо влиять на прохождение в следующие этапы. Его единственная цель — дать вам возможность ознакомиться с платформой Codeforces и её тестирующей системой. Приглашаем вас принять в нём участие! Для участия перейдите по ссылке http://codeforces.me/contests/646. Раунд будет содержать несколько несложных ознакомительных задач и будет открыт для официальных участников Технокубка.

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

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

Напоминаем, что еще открыта регистрация на олимпиаду для школьников Технокубок. Mail.Ru Group совместно с МФТИ, МГТУ им. Н. Э. Баумана и Codeforces в этом году впервые проводит Технокубок — первую совместную олимпиаду по программированию для школьников. На кону — дополнительные баллы при поступлении в престижные технические вузы России и ценные призы.

Зарегистрироваться на олимпиаду!

В финал соревнования будут приглашены лучшие 150 участников каждого из отборочных раундов (но не более 45% от общего числа участников раунда). Отборочные раунды состоятся:

• первый отборочный раунд: 23 марта 18:00-20:00
• второй отборочный раунд: 26 марта 10:00-12:00

Желаем удачи на олимпиаде,
MikeMirzayanov и команда Технокубка