Всем привет!

Завтра в 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. Появился разбор.

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

• Екатеринбург
  
• Саратов
  
• Рыбинск
  
• Минск
  

В воскресенье 25 октября 2015 года в Санкт-Петербурге в Университете ИТМО состоится Командный чемпионат школьников СПб по программированию. В соревновании будут участвовать более 90 команд. Информацию и расписание соревнований можно найти здесь.

Кроме того, на сайте состоится отборочный интернет-тур. Начало контеста ожидается в 12:00 по московскому времени.

А также в воскресенье на тех же задачах, что и в Санкт-Петербурге, пройдут отборочные соревнования в Казани (Иннополисе), Кирове, Гомеле, Челябинске, Ижевске, Калининграде, Казахстане, Кременчуге, Узбекистане и Грузии.

Фотографии можно будет найти на страничке ВК и в Instagram.

Новости будут публиковаться в twitter.

Официальный хэш-тег #СПбКОШП

Удачи всем участникам,
Пресс-служба соревнования.

UPD:
Окончательные результаты в СПб
Окончательные результаты в Казани
Результаты интернет-отбора
Результаты олимпиады в Кирове
Результаты олимпиады в Гомеле
Предварительные результаты олимпиады в Челябинске
Результаты олимпиады в Ижевске
Результаты олимпиады в Казахстане
Результаты олимпиады в Узбекистане
Результаты олимпиады в Грузии
Результаты олимпиады в Калининграде
Результаты олимпиады в Кременчуге

UPD2: Команды, прошедшие на ВКОШП от Санкт-Петербурга:

• СПб, ФМЛ 239: Фанаты long long-а (Анопренко, Иванов, Морозов)
• СПб, ФМЛ 239: МИГ (Ютман, Тух, Коротеев)
• СПб, ФМЛ 239 + ФТШ: С++ не нужен (Ждан, Орешников, Никифоровская)
• СПб, Лицей 533: Клешнёй неудобно (Епифанов, Фёдоров, Серикова)
• СПб, ФМЛ 239 + ФТШ + ЮМШ: Фан-клуб IT (Кириллов, Трилис, Селиванов)
• СПб, ФМЛ 239: Камень (Бартош, Михайлов, Заварин)
• СПб, ФМЛ 30 #24: 11-14-A (Алексеев, Безбородов, Истомин)
• СПб, ФМЛ 239: rand() (Брильянтов, Новиков, Терехов)
• СПб, ФМЛ 239 + ЮМШ: Зато мы милые! (Амиров, Ерохина, Ерохина)
• СПб, Лицей ФТШ: Smart Bugs (Анищенко, Богомолов, Лабутина)
• СПб, Лицей ФТШ: Untitled(566) (Елфимова, Ярков, Старков)
• СПб, Лицей 533: Тонущий ёжик (Беляков, Беляков, Цителова)

Всем привет от пресс-службы NEERC.

Мы рады заявить, что новый сезон ACM ICPC уже наступил и некоторые подрегионы провели свои четвертьфинальные соревнования. А в восточном подрегионе даже потребовалась квалификация на четвертьфинал, на которую зарегистрировалось 396 команд, а послали хотя бы одно решение во время соревнования 379 команд. Квалификация проводилась на четырнадцати площадках, и на четвертьфинал отобрались 97 команд. Восточный четвертьфинал пройдет 24 октября на задачах Северного четвертьфинала.

Результаты прошедших соревнований:

• Квалификация восточного четвертьфинала
  
• Центральный четвертьфинал
  
• Московский четвертьфинал
  
• Южный четвертьфинал
  

Четвертьфинал Северного подрегиона состоится в субботу, 24 октября, в Санкт-Петербурге в главном здании Университета ИТМО. Сегодня прошел инструктаж волонтеров, и ведется работа по переоборудованию аудиторий в холлы для соревнований и на кафедру компьютерных технологий уже запрещено заходить участникам завтрашнего четвертьфинала. За выход на юбилейный двадцатый полуфинал Северо-восточного европейского региона (NEERC) посоревнуются 96 команд из 23 университетов. Четыре последних года команда, побеждавшая на этом четвертьфинале, становилась абсолютным чемпионом ACM ICPC World Finals, поэтому соревнование будет интересным. Мне кажется, что главными фаворитами являются команды:

• Университет ИТМО 2 (Иван Belonogov Белоногов, Илья izban Збань, Владислав vlad107 Подтелкин)
  
• Университет ИТМО 1 (Адам subscriber Бардашевич, Владимир enot110 Смыкалов, Антон antonkov Ковшаров)
  
• СПбГУ 1 (Игорь -XraY- Пышкин, Алексей Copymaster Гордеев, Станислав ershov.stanislav Ершов)
  

А каковы ваши ставки? :)

В этом году также проводится ставший уже традиционным Кубок трех четвертьфиналов. Северный четвертьфинал, наряду с Московским и Западным, является этапом этого кубка. Начало тура 24 октября в 13:00 по московскому времени.

А также в субботу на тех же задачах, что и в Санкт-Петербурге, пройдут четвертьфиналы в Азербайджанском, Армянском, Восточном, Казахстанском, Таврическом и Узбекистанском подрегионах.

Я, Борис Минаев (qwerty787788), Геннадий Короткевич (tourist) и Павел Кунявский (PavelKunyavskiy) проведем текстовую трансляцию в твиттере. Следите и пишите по хештегу #NSNEERC.

Подписывайтесь на страницу VK и аккаунт в Instagram. Там можно будет найти фотографии и интересную информацию.

Всем хороших выходных,
Нияз Нигматуллин,
Представитель пресс-службы соревнований

UPD: Текущие результаты

UPD2: Список команд, вышедших в полуфинал:

• SPb ITMO University 1 (Kovsharov, Bardashevich, Smykalov)
• SPb State University 1 (Ershov, Pyshkin, Gordeev)
• SPb State University 3 (Simonov, Logunov, Ryazanov)
• SPb ITMO University 3 (Budin, Latyshev, Yakutov)
• SPb ITMO University 2 (Belonogov, Podtelkin, Zban)
• SPb Academic University 1 (Bogomolov, Podguzov, Smirnov)
• SPb State University 2 (Savchenkov, Makarov, Sayranov)
• SPb ITMO University 4 (Kisialiou, Berinchik, Korchagin)
• SPb State University 4 (Gulikov, Malinovskii, Kulikov)
• SPb Academic University 7 (Moskvitin, Smirnov, Plyushchenko)
• Northern (Arctic) Federal University 1 (Popovich, Chesnokov, Dodin)
• Petrozavodsk State University 1 (Ermishin, Starkov, Pyatin)
• Petrozavodsk State University 2 (Ermolin, Titov, Alkin)
• SPb State Polytechnic University 1 (Svitkin, Vinokhodov, Tretiakov)
• Pskov State University 1 (Shalabod, Shantarin, Dmitriev)
• Northern (Arctic) Federal University 2 (Guriev, Urusovskiy, Rudniy)

Hello, Codeforces!

I'm glad to invite you to participate in the online mirror of the Baltic Selection Contest for ACM ICPC 2015–2016 that will take place in Gym on the 22nd of October, 13:00 UTC.

This competition determines the best teams throughout the universities of Latvia, Lithuania and Estonia that will participate in ACM ICPC NEERC Western subregional contest in Minsk, Belarus. The onsite contest was held on the 12th of October. The participating universities were University of Latvia, Vilnius University, Kaunas University of Technology, Vilnius Gediminas Technical University, Estonian Information Technology College and others.

As a bonus, I'm posting some photos of the onsite action at University of Latvia. :)

The top 5 teams at the onsite competition were:

1. LU: 64428b862de0207ba0385b1ed2df43e1 (Alex_2oo8, zmad)
2. VU: 2B||!2B (vstrimaitis, jDomantas, JustasK)
3. LU: 0x7DF (Pakalns, Candyman, A_Le_K)
4. LU: leet (Instasamka, how_to_become_purple, JustN)
5. KTU #1 (wi_lius, lukgar, ASBusinessMagnet)

The detailed onsite standings will be posted after the contest.

The problems were prepared by a group of authors from University of Latvia: gen, KarlisS, andreyv, cfk.

Good luck & have fun!

Вы можете распечатать PDF-версию условий: http://assets.codeforces.com/statements/589.pdf

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

• 1 место: Нижегородский государственный университет #1 (Владислав vepifanov Епифанов, Николай KAN Калинин, Михаил mike_live Кривоносов)
• 2 место: Университет Иннополис (Евгений savinov Савинов, Сергей sokian Киян, Александр map Машрабов)
• 3 место: Саратовский государственный университет #1 (Эдвард Edvard Давтян, Виталий kuviman Кудасов, Данил danilka.pro Сагунов)

В субботу (17-го октября) в 11:00 здесь состоится неофициальная трансляция прошедшего соревнования. Вас ждут интересные задачи, которые жюри постаралось сделать интересными как для начинающих, так и опытных участников. К участию приглашаются как команды из 1-3 человек, так и индивидуальные участники. Контест не будет влиять на рейтинг Codeforces.

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

Желаю участникам!

Председатель жюри MikeMirzayanov.

P.S. Мы сожалеем, что наша трансляция пересекается с другими онлайн-турнирами, но поскольку запланированное изначально время в воскресенье оказалось занято трансляцией московского четвертьфинала NEERC, то подвинуть наше соревнования не представляется возможным. Если вы являетесь школьной командой, то рекомендуем обратить внимание на Интернет-версию Уральской региональной командной олимпиады.

Hello Codeforces.

I'm honored to announce you, that Codeforces round #326 is gonna take place soon on Codeforces.

Writers are AmirMohammad Dehghan(PrinceOfPersia) and Ali Haghani(Haghani). There will be 6 problems in each division(4 problems are common) and you'll have 2 and a half hour to solve them. I hope you enjoy the problems.

I wanna thank Maxim Akhmedov(Zlobober) for his great helps in preparing this round, MikeMirzayanov for wonderful platforms of Codeforce and Polygon, Delinur for translating problem statements into Russian and MohammadReza Maleki(mruxim) and Ali Bahjati(LiTi) for their great advices (and LiTi again for some graphics).

This is my third round on Codeforces and not the last one, I hope.

This is the last round on Codeforces with Zlobober as coordinator. It was nice working with him. We had a lot of fun and interesting contests during his coordination. I just wanna say: Thank you Maxim for all your contribution to CodeForces community and good luck in the future. After I heard these news, my first guess for the next coordinator was I_love_Tanya_Romanova; But I don't know if CodeForces hires people from out of Russia or not.

The main character of this round is Duff, but you'll also have to help her friend, Malek!

I wish you all high ratings and lots of joy.

Scoring will be posted soon.

GL & HF!

Problems are sorted by the expected difficulty, but we strictly recommend you to read all the problems.

UPD: Scoring is: 750-1000-1500-2000-2500-3000 in Div.2 and 500-1000-1500-2000-2750-2750 in Div.1 .

UPD1: Editorial is published.

UPD2: System test is over. Congratulations to all winners.

Div.1 Winners are:

1. qwer1561
2. Endagorion
3. jcvb
4. subscriber
5. wjh720

Div.2 Winners are:

1. sleepy_mario
2. BIT-silence
3. Owaski
4. Orenji.Sora
5. JavaInTheSouth

Also congratulations to JoeyWheeler, the only one who solved problem Div.1 D.

Привет, Codeforces!

12 октября 2015 года в 12:00 MSK состоится очередной раунд Codeforces #325 для участников из первого и второго дивизионов. Обратите внимание на необычное время начала раунда!

Этот раунд проводится по задачам Регионального этапа всероссийской командной олимпиады школьников по программированию 2015, который пройдет в то же время в городе Саратове. Пожелаем школьным командам удачи на соревновании!

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

Процесс подготовки задач был интересным: мы много раз переделывали условия, переписывали решения, добавляли тесты, изменяли ограничения, даже успели поменять полностью готовую задачу (пришлось останавливать конвейер типографии, который уже печатал условия :-)). Поблагодарим всех кто готовил, помогал готовить задачи, вычитывал условия, писал перекрестные решения: Адилбек adedalic Далабаев, Роман Roms Глазов, Владимир vovuh Петров, Олег Oleg_Smirnov Смирнов, Алексей Perforator Рипинен, Максим Neon Мещеряков, Илья IlyaLos Лось, Виталий gridnevvvit Гриднев, Данил danilka.pro Сагунов, Александр fcspartakm Фролов, Павел HolkinPV Холкин, Игорь Igor_Kudryashov Кудряшов, Елена elena Рогачева, Дмитрий Nerevar Матов, Виталий kuviman Кудасов. Председателем жюри олимпиады является Михаил MikeMirzayanov Мирзаянов (также автором некоторых задач из комплекта). Я же (Эдвард Edvard Давтян) готовил некоторые задачи и координировал работу авторов. Вот такая большая команда авторов получилась (надеюсь я никого не забыл)!

Также, конечно, поблагодарим Максима Ахмедова (Zlobober), Того-Чьё-Имя-Пока-Нельзя-Называть (если не ошибаюсь он/она прямо сейчас пишет дополнительные решения по задачам раунда) за помощь в подготовке задач, Марию Белову (Delinur) за перевод условий на английский язык и снова Михаила Мирзаянова (MikeMirzayanov) за замечательные системы Codeforces и Polygon.

Участникам будет предложено шесть задач и два часа на их решение. Разбалловка будет объявлена незадолго до начала раунда. Всем высокого рейтинга! Good luck and have fun!

P.S.: Также хочется пожелать удачи участникам четвертьфинала чемпионата мира по программированию южного региона, который пройдет в эту среду.

По техническим причинам раунд перенесен на 10 минут

UPD: По задаче Subway roller в наборе тестов присутствовали тесты с поездами длины 1. В данный момент проводится обсуждение того, насколько сильно это повлияло на результаты раунда. Приносим извинения всем участникам, которых затронула эта проблема. В скором времени будет сделано объявление о принятом решении.

UPD2: При подготовке задачи Subway Roller у одного из авторов было ошибочное понимание условия. Из-за этого валидатор допускал существование поездов длины 1, а так же присутствовали тесты с поездами длины 1. Жюри приняло решение, что если участник посылал в течении контеста верное решение, то оно должно быть ему зачтено. Для этого у каждого участника было выбрано первое отправленное решение, проходящее итоговый тестсет (если таковое решение имелось), а остальные решения были пропущены. Так же баллы за все взломы во время соревнования остались без изменения, включая ситуацию, когда взломанное решение считается правильным на новом тестсете (в этом случае взломщик получает свой балл, а решение участника считается полным). Контест будет признан рейтинговым, однако если вы считаете, что данная проблема сильно повлияла на ваш результат, напишите мне в течении 24 часов и мы рассмотрим возможность сделать его нерейтинговым лично для вас.

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