Привет, Codeforces!

В 27.08.2018 19:35 (Московское время) состоится AIM Tech Codeforces Round 5.

Раунд подготовили сотрудники компании AIM Tech: Kostroma, riadwaw, Edvard, yarrr, zemen, Errichto, malcolm, gchebanov, VadymKa и zeliboba.

Раунд пройдет во время Петрозаводских сборов, спонсором которых является наша компания.

Благодарим Михаила Мирзаянова (MikeMirzayanov) за замечательные платформы Polygon и Codeforces, и координатора задач Codeforces Николая Калинина (KAN) за помощь в подготовке раунда. Огромное спасибо Golovanov399, Arterm, winger за ценные замечания и прорешивание раунда!

Наша компания занимается алгоритмической торговлей на бирже, ключевыми понятиями для нас являются low latency и high frequency trading. Перед ребятами в нашей компании стоят разнообразные задачи: написание стратегий для торговли, оптимизация торговых систем для достижения минимально возможной скорости реакции на биржевые события, сохранение и обработка больших объемов исторических данных. Умение писать эффективный C++ код, алгоритмическое мышление и математическая интуиция очень полезны в нашей работе, поэтому большая часть наших сотрудников — олимпиадники по программированию и математике. У нас работает несколько финалистов ACM ICPC, три золотых медалиста и чемпион мира (и золотой медалист). В свободное от работы время мы участвуем в разных соревнованиях по программированию и не только, испытываем себя на прочность в походах и покоряем горные вершины.

Узнать о нас больше можно на сайте aimtech.com, в facebook и instagram. Можно отправить нам резюме через эту форму, даже если вы не участвуете в раунде.

Участникам совмещенного раунда будет предложено 8 задач и 2:15 на их решение.

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

Призы с 502 раунда в память о Leopoldo Taravilse будут разыграны в этом раунде.

Топ-25 получат 100$ каждый, 26-71 места получат по 50$ каждый.

Разбалловка 500-750-1250-2000-2500-3250-3250-3500

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

Спасибо за участие, поздравляем победителей!

1. LHiC
2. jqdai0815
3. bmerry
4. Um_nik
5. Egor
6. Benq
7. tqyaaaaang
8. DearMargaret
9. Marcin_smu
10. Swistakk

Разбор

Краткий разбор от bmerry

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

<copy-pasted-part>

Привет! В Aug/24/2018 17:50 (Moscow time) начнётся Codeforces Round 506 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Наверное, участникам из первого дивизиона они будут совсем не интересны, а для 1600-1899 покажутся простыми. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

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

Вам будет предложено 6 или 7 задач и 2 часа на их решение.

Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.

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

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

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

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Михаилу awoo Пикляеву, Максиму Neon Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.

Удачи!

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

</copy-pasted-part>

UPD1:

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

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

Всего было сделано 1217 успешных взломов и 926 неудачных взломов!

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

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

NOTE : Knowledge of Binary Indexed Trees is a prerequisite.

Problem Statement

Assume we need to solve the following problem. We have an array, A of length N with only non-negative values. We want to perform the following operations on this array:

1. Update value at a given position

2. Compute prefix sum of A upto i, i ≤ N

3. Search for a prefix sum (something like a lower_bound in the prefix sums array of A)

С 6 по 13 ноября 2018 года студенты, нацеленные на победу в ICPC и региональных соревнованиях по спортивному программированию, приглашаются на сборы в МФТИ (г. Долгопрудный). Международный семинар по программированию в рамках мирового первенства будет проходить на английском языке, поэтому участвовать могут команды со всего мира.

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

Дивизион А – для опытных команд с серьезным уровнем подготовки, которые претендуют на выход в финал

Дивизион В – для участников, которые готовятся к участию в региональных соревнованиях.

Основным модератором контестов выступит Олег Христенко, координатор Открытого кубка им. Е.В. Панкратьева и главный редактор Snarknews. Учебную программу координируют Михаил Тихомиров и Глеб Евстропов.

Для тех, кто оплачивает участие заранее, действуют скидки. Граждане из стран Евразийского Экономического Союза (ЕАЭС) могут совершать платежи в рублях, а резиденты других стран — в американских долларах. В стоимость участия входит учебная программа, питание и проживание в кампусе МФТИ, а также программа досуга.

Стоимость (на 1 человека) до 21 сентября — 26.000 рублей (для резидентов ЕАЭС), $630 USD. Две команды могут получить возможность бесплатного участия — об этом подробнее на сайте.

Регистрируйтесь на Международный семинар по программированию и побеждайте!

Ждем вас и желаем удачи!

Hello, codeforces!

This time I've decided to choose a task from my own contest which took place last April and was known as the Grand Prix of Poland. If you want to write this contest virtually in the future, then consider not reading this blog. If you've participated in this contest and maybe even solved this task, then anyway I recommend reading it, cause this task has many very different solutions, each of them being very interesting (in my opinion). It's also a reason why this blog is longer than previous ones.

I'll write about task C "cutting tree" (not uploaded to the ejudge yet :/). The statement goes as follows:

You are given a tree with n vertices (1 ≤ n ≤ 2·10⁵). The task is to calculate f(k) for each integer k from the range [1, n] where f(k) is defined as the maximum number of connected components of size k which we can "cut off" from the tree. A connected component of size k is a set of k vertices such that it's possible to traverse in the tree between any pair of these vertices using only vertices from this set. Chosen components are not allowed to intersect, so each vertex must belong to at most one component.

#IjustWantContribution

It seems there isn't any blog about Berlekamp-Massey Algorithm around here, so I decided to go on a try. :P

Acknowledgement: Hats off to matthew99 for introducing this algorithm.

What is 'linear recurrence'?

Assuming there is a (probably infinity) sequence a₀, a₁...a_n - 1, we call this sequence satisfies a linear recurrence relation p₁, p₂...p_m, iff . (Obviously, if m ≥ n any p can do :P)

How to calculate k-th term of a linear recurrence?

For a polynomial , we define .

Obviously G satisfies G(f) ± G(g) = G(f ± g).

Because , if we let , then G(f) = 0. Also G(fx), G(fx²)... = 0. So G(fg) = 0 (g is any polynomial).

What we want is G(x^k). Because G(f⌊ x^k / f⌋) = 0, then .

Привет.

В 19.08.2018 16:35 (Московское время), состоится общий рейтинговый раунд Codeforces Round #505. Этот раунд идет в паре с раундом #504.

Часть задач взята с Финала VK Cup 2018 (ashmelev, Errichto, Lewin), часть придумана мной. Спасибо моим товарищам — Диме (cdkrot), который, кстати, является координатором этого раунда, Коле (KAN), который позвал меня его проводить, а также Грише (vintage_Vlad_Makeev) и Ильдару (300iq) за то, что они просто клевые.

Также спасибо Майку MikeMirzayanov за множественные баг-фиксы и замечательный Codeforces!

Задач будет семь со следующей разбалловкой:
500 — 1000 — 1500 — 1750 — 2250 — 2750 — 3500

UPD. Систесты окончены. Разбор

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

1. Swistakk
2. DearMargaret
3. Kostroma
4. Benq
5. AwD
6. xumingkuan
7. webmaster
8. TLE
9. Egor
10. kriii

Так же, как и в прошлом раунде, по инициативе компании ВКонтакте будут разыграны очки GP30.

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

Напоминаю, что лучшие 10 по сумме очков GP30 получат фирменного плюшевого персика.

Надеюсь, что вам понравится. Удачи!

Привет, Codeforces!

В такой замечательный день недели, как 18.08.2018 17:35 (Московское время) состоится Educational Codeforces Round 49.

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

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

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

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

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

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

Hi Codeforces!

Our Hello Barcelona Programming Bootcamp will be kicking off next month from Sept 26 — Oct 4, and we’d love to see you there!

The boot camp will once again feature the all-time greats Mike MikeMirzayanov Mirzayanov, Andrey andrewzta Stankevich, Michael Endagorion Tikhomirov, Gleb GlebsHP Evstropov, Artem VArtem Vasilyev, Ivan ifsmirnov Smirnov and other world renowned Russian coaches to train the participants.

You will be competing and learning side by side with some of the greatest teams in the world, while learning from the best coaches the ICPC has to offer.

Be sure to register before September 1st so everyone has time to get visas if needed, and of course for the Early Bird Discount of 5% or the Loyalty Discount* of 20% off registration for the boot camp!

*The loyalty discount is offered to universities and individual participants that took part in Hello Barcelona Bootcamps and Moscow Workshops ICPC.

Learn more about Barcelona ICPC Bootcamp

You can ask any questions by email: [email protected]

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

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

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

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

Вот уже пять лет мы вместе с Сodeforces проводим VK Cup. На этот раз на чемпионат зарегистрировались рекордное количество команд — 3279. Это на 553 больше, чем в прошлом году. Мы гордимся, что турнир привлекает всё больше участников. Ведь для молодых разработчиков — это отличная возможность проявить себя. Для нас — шанс отыскать талантливых специалистов и пополнить ими свои ряды.

Я четыре года участвовал в олимпиадах по программированию, дошёл до чемпионства мира ACM ICPC и не понаслышке знаю, какие эмоции дарят такие турниры и победы в них. Но вне этого мира есть мир реальных рабочих задач. У олимпиадников — особый склад ума, и не все компании знают, как его лучше применять. В итоге в минусе обе стороны: способные разработчики не раскрывают полностью свой потенциал, а работодатели не готовы к нестандартным решениям, которые предлагают олимпиадники.

ВКонтакте давно использует уникальные навыки олимпиадников для решения прикладных задач. Мы знаем, что интересно разработчику и как этот интерес реализовать во благо проекта. Все базы данных VK написаны олимпиадниками. Сейчас сотрудники команды, семь из которых — олимпиадники разного уровня, отвечают за обработку информации пользователей (а их 97 миллионов в месяц). Более того, в зоне нашей ответственности — оптимизация ядра backend’a и развитие собственного компилятора PHP в C++.

Заполни до 1 сентября анкету, если у тебя загораются глаза при мысли о:

• реализации сложных алгоритмов и структур данных в высоконагруженных распредёленных базах данных;
• борьбе за проценты производительности кода;
• работе над моделями машинного обучения и множестве других сложных задач.

Мы рассчитываем, что тебе уже есть 18, ты живёшь или переедешь в Санкт-Петербург и что ты готов к работе с полной занятостью и гибким графиком.

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

Дмитрий Егоров, директор по высоконагруженным системам и оптимизации.

Всем привет!

Совсем недавно ВКонтакте и Codeforces провели Финал VK Cup 2018 (поздравляем победителей!), а теперь вас ждут рейтинговые раунды по мотивам прошедшего мероприятия.

17 августа, 17.08.2018 17:35 (Московское время), состоится общий рейтинговый раунд Codeforces Round #504. Некоторые задачи будет совпадать с некоторыми задачами Финала VK Cup 2018, а awoo и vovuh подготовили еще несколько задач для проведения полноценного раунда.

Задачи этого раунда предлагали, готовили и тестировали: MikeMirzayanov, awoo, vovuh, Errichto, Lewin, Endagorion, Um_nik, YakutovDmitriy, budalnik, izban, Belonogov, scanhex, 300iq, qoo2p5, Livace.

Спасибо компании ВКонтакте — в этом раунде также будут разыграны призы! А именно, участникам, занявшим первые 30 мест этого раунда и раунда #505, также частично основанного на задачах Финала VK Cup 2018, будут засчитаны очки GP30.

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

Лучшие 10 получат фирменного плюшевого персика!

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

Удачи!