Привет, Codeforces!

Встречайте небольшую инновацию на Codeforces — сложности задач (а заодно и новый виджет фильтрации задач архива). Для всех задач архива мной были подсчитаны сложности в шкале рейтинга участников. Примерно это означает, что если рейтинг задачи равен вашему, то на типичном раунде вы бы решили задачу с вероятностью 0.5. И, вообще, если ваш рейтинг равен r_i, а рейтинг задачи равен r_j, то задача во время раунда может быть решена примерно с вероятностью:

Например, если рейтинг задачи меньше вашего на 200, то ожидаемая вероятность решения задачи равна 0.75. При разности рейтингов 400 вероятность возрастает до 0.9.

Для удобного подбора задач в архиве теперь можно пользоваться специальным виджетом:

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

Сложности задач также отображаются при подборе задач в мэшапы.

Надеюсь, теперь вы сможете эффективнее заниматься дорешиванием задач, а процесс сборки тренировок станет проще.

UPD 1: Вы уже заметили новые всплывашки о результатах тестирования попыток?

UPD 2: Добавил в API опциональное поле rating к объекту Problem.

UPDATE: появилась форма для регистрации команд. Данные из этой формы будут перенесены в базу данных ICPC. Командам, уже заполнявшим подобную форму для отдельной площадки, заполнять форму второй раз не нужно.

Регистрация команд

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

Напоминаем, что узбекистанский четвертьфинал 2018 года пройдёт на нескольких площадках в воскресенье, 11 ноября 2018 года. Университеты, желающие принять участие и открыть площадку, должны зарегистириоваться в этой форме.

Зарегистрировать площадку

Информация по регистрации команд будет опубликована позднее.

Важное обновление: университеты из Таджикистана и Туркменистана также могут создавать площадки для участия в Узбекистанском четвертьфинале. Ждём университеты и команды этих стран в ICPC!

Я рад пригласить вас принять участие в рейтинговом Codeforces Round 519 by Botan Investments. Дата и время раунда: 28.10.2018 18:35 (Московское время).

Этот раунд будет совмещенный для обоих дивизионов и будет содержать 7 задач на 2 часа, раунд будет рейтинговым.

Задачи были подготовлены Anadi, Grzmot, isaf27 и Rzepa. Также спасибо:

KAN и cdkrot за помощь в подготовке задач; --Pavel--, Nerevar, map, GR1n, rutsh, AlexFetisov и winger за тестирование раунда; MikeMirzayanov за платформы Codeforces и Polygon.

Раунд проходит при поддержке фонда Botan Investments.

Призы! Лучшие 50 участников и 20 случайных участников, занявших место с 51 по 500, получат персональную толстовку с хендлом Codeforces.

Фонд Botan Investments занимается инвестициями в стартапы на ранней стадии помимо поддержки курсов и соревнований по спортивному программированию и машинному обучению. Один из стартапов имеет офис в Сочи и занимается проектами, связанными с Computer Vision и Augmented Reality. При разработке приходится эффективно решать задачи, нерешенные никем ранее. Опыт решения олимпиадных задач очень помогает и в нашей команде разработки ядра технологии более половины людей с богатым олимпиадным прошлым: --Pavel--, Nerevar, map, Babanin_Ivan, GR1n, rutsh, mekagem

Сейчас есть отличная возможность присоединиться к команде и поучаствовать в создании и развитии уникальных технологий. В недавнем прошлом фонд Виктора Шабурова инвестировал в Looksery, который в 2015 году присоединился к Snapchat за $150M.

Разбалловка будет анонсирована позже. Желаю вам повышения рейтинга и надеюсь увидеть вас в таблице результатов!

UPD: I'll be on the community Discord server shortly after the contest to discuss the problems.

UPD: Scoring: 500 1000 1500 2000 2250 2750 3500

UPD: Editorial

The round is over, congratulations to the winners!

1. scott_wu
2. mnbvmar
3. HIR180
4. ksun48
5. Benq
6. geniucos
7. Alex_2oo8
8. Petr
9. Um_nik
10. V--o_o--V

Всем привет!

Текстовая трансляция Условия

В воскресенье, 28 октября, пройдет большая часть отборов на девятнадцатую Всероссийскую командную олимпиаду школьников по программированию, которая состоится в Санкт-Петербурге, Барнауле, Алматы, Тбилиси и Кременчуге 8-9 декабря 2018 года.

В том числе в воскресенье пройдет отбор в Санкт-Петербурге и Интернет-тур. Начало запланировано на 12:00. Ссылка на монитор в таблице.

Результаты и даты проведения отборов по регионам приведены в таблице:

Следите за актуальной информацией в VK, Instagram, Twitter и Telegram. А также по хештегу #СПбКОШП.

Всем привет!

Текстовая трансляция Видеотрансляция

Спешим анонсировать вам, что завтра, 27 октября, состоится несколько отборочных четвертьфинальных туров Северного Евразийского региона сезона 2018/19. Свой шаг к финалу ICPC2019 в Порту уже сделали команды Московского и Южного подрегионов, завтра же мы узнаем, с кем из Северного, Уральского, Казахстанского, Азербайджанского, Армянского, Грузинского и Таврического подрегионов они поборются в полуфинале.

На четвертьфинале Северного подрегиона в Санкт-Петербурге (который мы традиционно освещаем чуть больше остальных в силу географических причин), контест будет проходить на площадке Университета ИТМО, и начнется в 12.00. Но по возможности постараемся держать вас в курсе о происходящем в других подрегионах.

Условия задач доступны по ссылке.

Результаты и даты проведения четвертьфиналов по подрегионам приведены в таблице:

Не забывайте, что проверить свое умение решать задачи можно в контестах Кубка трех четвертьфиналов, который организован командой Яндекс.Контест и жюри Московского, Западного и Северного четвертьфиналов.

Следите за актуальной информацией в наших соцсетях: VK, Instagram, Twitter и Telegram. А также по хештегу #NSNEERC.

Московский физико-технический институт вновь приглашает учеников 9-11 классов принять участие в Зимней компьютерной школе. С 2019 года проект будет называться Moscow Workshops Juniors. Это тренировочные сборы по программированию, на которых старшеклассники пройдут усиленную подготовку к национальным олимпиадам с 25 февраля по 6 марта 2019 года.

Участников ждут ежедневные тренировочные контесты, тематические лекции с практикой, а также развлекательная программа: научно-популярные лекции, cпортивные, интеллектуальные игры. Чтобы попасть в школу, нужно принять участие в отборочных онлайн-турах (как в одном, так и в нескольких), по формату приближенных к олимпиадам по информатике. Рейтинг участников составляется по результатам четырех туров. С правилами отбора можно ознакомиться по ссылке.

По результатам отбора участники будут поделены на три дивизиона — A, B, C. Школьники смогут выбрать из предложенных тем наиболее интересные и составить оптимальную учебную программу, ориентируясь на свой уровень подготовки. Причем, если участник посчитает учебную программу слишком простой или сложной, он может перейти в другой дивизион.

Всего пройдет четыре этапа:

• 27 октября 16:00
• 18 ноября 12:00
• 16 декабря 12:00
• 20 января 12:00

Moscow Workshops Juniors предлагает несколько вариантов участия школьникам, которые имеют достижения в олимпиадах:

Бесплатное участие гарантируется победителям и призерам заключительного этапа Всероссийской олимпиады школьников (или других национальных олимпиад) по информатике 2017-2018 учебного года;

13900 рублей для победителей Открытой олимпиады школьников по программированию, Олимпиады Технокубок 2017-2018 учебного года и победителям ВКОШП 2018-2019 учебного года;

23900 рублей для призеров Открытой олимпиады школьников по программированию, Олимпиады "Технокубок", а также участникам заключительного этапа Всероссийской олимпиады школьников (или других национальных олимпиад) по информатике 2017-2018 учебного года и призерам ВКОШП 2018-2019 учебного года;

33900 рублей для остальных участников.

РЕГИСТРАЦИЯ

Если у вас еще остались вопросы, пишите на адрес оргкомитета: [email protected]

Привет, Codeforces!

В 25.10.2018 17:35 (Московское время) состоится Educational Codeforces Round 53 (рейтинговый для Див. 2).

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

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

Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров и Иван BledDest Андросов.

Удачи в раунде! Успешных решений!

А вот сообщение от наших друзей из Harbour.Space:

Hey Codeforces! We want to remind you that the Scholarship for the Master’s in Robotics programme, which starts on January 7th 2019, has an application deadline of November 12th, 2018.

Harbour.Space University and Remy Robotics are collaborating to offer graduate students from anywhere in the world a once in a lifetime opportunity, a fully funded scholarship for Harbour.Space University’s Master’s Programme in Robotics.

The scholarship value is €34.900 and it includes:

• Complete coverage of the University tuition fee (€22,900)

• Internship at Remy Robotics (20h per week during 1 year)

• €1,000 per month during 1 year (Internship earnings)

UPD: Мы с vovuh будем ждать всех желающих в местном Discord сервере сразу после контеста для обсуждения задач.

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

Поздравляем лучших взломщиков:

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

UPD2: Разбор опубликован

part 2: https://codeforces.me/blog/entry/62792

Watch my lecture-stream tomorrow (Thursday) at 14:00 CEST — https://www.youtube.com/watch?v=qdlPY37MBPo https://www.youtube.com/watch?v=U_h3IjreRek. I will go through theory and problems from this blog. The only prerequisite is knowing what is probability. The next (harder) part on Monday.

The video will be available later, with timestamps for each problem — so you don't have to watch everything.

Definition of EV

Let's say we bought a lottery ticket for 2$. We will win 10$ with probability 10%, and 20$ with p-bility 2%. On average, it gives us 0.1·10 + 0.02·20 = 1.4, so we are worse off after buying the ticket. The computed average is called the expected value.

The expected value (EV, expectation) is the average value of an event/experiment. For example, EV of the number of pips rolled on a 6-sided die is 3.5:

Linearity of EV (super important theorem):

Приглашаю Вас поучаствовать в рейтинговом Codeforces Round #518. Дата и время проведения раунда: среда, 24 октября 2018 г. в 19:35. Раунд был перенесен с 23 октября на 24 в связи с проведением в это же время ICPC Indian Online Qualifier.

Это первое соревнование, предложенное мной. Надеюсь, что оно вам понравится.

На раунде будет 6 задач для второго дивизиона и 5 задач для первого (3 задачи общие). Контест будет длиться 2 часа.

Задачи для вас составляли Алексей kristevalex Кристев и Алексей Um_nik Данилюк. Также большое спасибо:

Николаю KAN Калинину и Ильдару 300iq Гайнуллинину за помощь в подготовке задач; Ивану isaf27 Сафонову и Олегу Merkurev Меркурьеву за тестирование раунда; Михаилу MikeMirzayanov Мирзаянову за платформы Codeforces и Polygon.

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

Как вы заметили, этот раунд проводится в честь компании Mail.Ru, значительно поддержавшей Codeforces по случаю 8-летия платформы. Вот несколько слов от MikeMirzayanov:

Большое спасибо Mail.Ru за поддержку Codeforces! Мы являемся партнёрами уже много лет, и было особенно приятно получить поздравления от старых друзей. Мне кажется, Mail.Ru — чемпион мира среди компаний по организации различных интересных соревнований для любителей программирования. Вот список (уверен, неполный) активностей Mail.Ru, которые могут быть интересны аудитории Codeforces:

• Mail.Ru Cup — новое соревнование по спортивному программированию (совместно с Codeforces!), открытое как для студентов, так и для профессиональных разработчиков;
• Технокубок — олимпиада по программированию для учеников 8-11 классов из России и стран СНГ (совместно с Codeforces!);
• Russian AI Cup (RAIC) — открытое соревнование по программированию искусственного интеллекта игровых стратегий (совместно с Codeforces!);
• Mini AI Cups (Mini AIC) — мини-клон чемпионата Russian AI Cup, площадка соревнований по искусственному интеллекту, связанных с написанием ботов для игр;
• Machine Learning Boot Camp (ML Boot Camp) — онлайн-чемпионат по машинному обучению и анализу данных;
• HighLoad Cup (HLC) — соревнование разработчиков высоконагруженных систем.

Кроме этого Mail.Ru запустило большое количество образовательных инициатив, я сам неоднократно смотрел записи лекций на YouTube с занятий Техносферы и других проектов.

Еще раз спасибо за поздравление. Надеюсь на долгосрочное и плодотворное сотрудничество!

Разбалловка будет объявлена ближе к началу контеста. Желаю высокого рейтинга и жду вас на соревновании!

Я буду на Codeforces Discord server в течение некоторого времени после раунда для обсуждения задач.

UPD: разбалловка div1: 500 1000 1750 2250 2500 div2: 500 1250 1500 2250 2750 3500

UPD2: опубликован разбор.

Hello, codeforces!

Sorry for the long break, but the last weeks of holidays and the first weeks of academic year took my attention. I hope today's trick will make you forgive me. :P

I invented this trick a few years ago, but for sure I wasn't first, and some of you already know it. Let's consider the following interactive task. There are n (1 ≤ n ≤ 10⁵) hidden integers a_i, each of them from range [1, 10¹⁸]. You are allowed to ask at most 103000 queries. In one query you can choose two integers x and y (1 ≤ x ≤ n, 1 ≤ y ≤ 10¹⁸) and ask a question ''Is a_x ≥ y?'' The task is to find the value of the greatest element in the hidden array. The checker isn't adaptive.

Unfortunately, this task is only theoretical, and you cannot solve it anywhere, but it'll turn out, that solution can be handy in many other, much more complicated problems.