#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 получат фирменного плюшевого персика!

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

Удачи!

Hello, codeforces!

All signs in the sky and on the ground indicate that you've enjoyed my first blog, so here is the second one. I've decided to choose a Polish task again, as there are plenty of interesting ones. This time we'll take a look at the "plot purchase" (you can submit here), which is a bit easier, but a few years ago I was very proud of myself when I solved it. The statement goes as follows:

You are given a square n × n grid (1 ≤ n ≤ 2000). In every cell, there is a number from the range [1, 2·10⁹]. You are also given an integer k (1 ≤ k ≤ 10⁹). A task is to find a subrectangle of this grid such that the sum of values in this subrectangle lies in the range [k, 2·k] (or report that there is no such subrectangle). Just print coordinates of its opposite corners.

Hello, codeforces!

The community wants so the community gets it! :D Here it is, my very first blog about tasks and algorithms. At the beginning I've decided to post my entries on codeforces, maybe I'll switch to something different if it becomes uncomfortable.

To pour the first blood I decided to choose a task from one of the old ONTAK camps. Task's name is "different words" (you can submit here). The statement goes as follows:

You are given n words (2 ≤ n ≤ 50 000), every of length exactly 5 characters. Each character can be a lowercase letter, an uppercase letter, a digit, a comma... basically, it can be any character with ASCII code between 48 and 122 (let's say that k is the number of possible characters). A task is to find all pairs of indexes of words which are . Two words are if they differ at all 5 corresponding positions. So for example words and are really different and words and are not, because in both of them the third character is . As there can be many such pairs (up to ), if there are more than 100 000 pairs, then the program should print that there are only 100 000 and print this number of pairs (arbitrary chosen).

Please, note that this task comes from the contest which took place a few years ago, so don't think about bitsets. :P

Важный день! Сегодня мы узнаем победителей VK Cup 2018. Призовой фонд чемпионата как и в прошлом году связаны с круглыми числами в двоичной системе счисления:

• 1 место — 1048576 рублей
• 2 местo — 524288 рублей
• 3 местo — 262144 рубля
• 4-8 места — 131072 рубля

Планируем начинать в 10:40. Следить за ходом соревнования можно вот тут.

Удачи участникам! Вечером добавлю в пост победителей.

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

1. [Спб] 120 Minutes Adventure: Александр el_sanchez Логунов, Михаил SpyCheese Путилин
2. [Спб] я и моя девушка: Айдар aid Сайранов
3. [Москва] Нижний Магазин SU: Владислав V--o_o--V Макеев, Михаил LHiC Ипатов
4. [Москва] Road to the Gucci store: Александр Golovanov399 Голованов, Никита -imc- Уваров
5. [Украина] Ананас: Марк AllCatsAreBeautiful Михно, Антон arsijo Ципко
6. [Украина] Accepted, cats and dogs: Андрій Andrew_Makar Макар, Матвей BigBag Асландуков
7. [Спб] ИТМО 2.0: Арсений craborac Кириллов, Александра demon1999 Дроздова
8. [СПб] Pareidolia: Алексей Copymaster Гордеев, Анастасия Lilith Софронова

Всем спасибо за участие и интерес, вы крутые. Раунд по мотивам задач финала будет через несколько дней. Следите за новостями!

Идет первый день VK Cup 2018!

На открытии послушали вступительные слова организаторов. Участники заранее прислали забавные фотки и ответили на анкету с фактами о себе. На фотки мы приклеели стикеры с Персиком — символом и хранителем VK Cup в этом году, а самые интересные ответы рассказали, пока волонтеры выдавали участникам бейджи.

Некоторые команды из топ-20 Раунда 3 отказались от участия в финале, чтобы сохранить попытку на следующих год. Мы пригласили следующих по рейтингу. Итого, финалисты этого года, встречайте!

1. Нижний Магазин SU: V--o_o--V & LHiC
2. ИТМО 2.0: craborac & demon1999
3. 120 Minutes Adventure: el_sanchez & SpyCheese
4. Кекс столичный: Melnik & hloya_ygrt
5. Z: egor_bb & Nikitosh
6. Saint Veronika: aytel & kokokostya
7. Road to the Gucci store: Golovanov399 & -imc-
8. Группа внутренних автоморфизмов: MrKaStep & bixind
9. Keksik: Tinsane & kb.
10. Свист минигана: Sert & Alexandr_TS
11. Ананас: AllCatsAreBeautiful & arsijo
12. Pareidolia: Copymaster & Lilith
13. я и моя девушка: aid
14. Типичная вечеринка с бассейном: Au-Rikka & Seemann
15. Accepted, cats and dogs: Andrew_Makar & BigBag
16. Московский Вентиляторный Завод: Дудка и Трубник: mHuman & komendart
17. QuietGenius: Semenar & Vaterlou
18. Влюбленные Мудаки: super_azbuka & Khusainov
19. R3tired: totsamyzed
20. Вупсень и Пупсень: Roms & adedalic

На пробном туре проверили работу системы — все огонь! Первая задача пробного тура — традиционная викторина. Вопросы были про Codeforces и ВКонтакте. Первыми ее решила команда Saint Veronika: kokokostya, aytel. Это оказалось не так просто :)

Вчера финалисты ходили в Эрмитаж и на картинг. Посмотрите на клевые фотку с вечера:

А сегодня мы обедали на теплоходе. Там был огромный штурвал! Фотки оттуда будут позже.

Сейчас участники пишут Code Game Challenge — в этом году футбол. Вечером будем смотреть результаты, а победителям ВКонтакте подарят клевые призы. Какие — пока секрет...

А завтра выложим ссылку на результаты финала — будете следить и болеть за знакомые хэндлы ;) Еще о соревновании можно почитать в группе VK Cup Вконтакте.

Всем привет!

Летняя компьютерная школа (ЛКШ) — это летняя школа для учащихся 6-10 классов, увлеченных программированием. ЛКШ ориентирована в основном (но не только) на школьников, участвующих в олимпиадах по информатике — от начинающих до участников международных олимпиад. ЛКШ проходит в две смены (июльскую и августовскую), в каждую из которых приезжают около 200 школьников со всей России и из-за рубежа. Более подробно об ЛКШ можно прочитать на lksh.ru

Сейчас идёт августовская смена Летней Компьютерной Школы и 11-го августа состоится традиционная командная олимпиада ЛКШ. Мы рады представить рейтинговый раунд на её основе!

Раунд будет рейтинговым для обоих дивизионов, пройдёт в 11.08.2018 16:35 (Московское время), в каждом дивизионе будет 5 задач и 2 часа на их решение.

Задачи раунда и олимпиады были придуманы и подготовлены преподавателями ЛКШ: izban, achulkov2, Schemtschik, peltorator, craborac, asokol, Morokei, Burunduk2. Также спасибо Kurpilyansky за помощь с организацией олимпиады.

Спасибо meshanya, Burunduk2, vintage_Vlad_Makeev, niyaznigmatul, manoprenko за тестирование задач!

Спасибо MikeMirzayanov за системы codeforces и polygon!

Да, мы знаем о том, что контест пересекается с ProCon Junior на codechef. К сожалению, учитывая расписание ЛКШ, а также приближающийся финал VK cup, мы ничего не можем с этим сделать =/.

Желаем удачи!

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

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

Div1:

1. Marcin_smu
2. Radewoosh
3. Swistakk
4. Panole233
5. ko_osaga

Div2:

1. wnsh
2. aurelio
3. usachevd0
4. jebouin
5. etiennerossignol

Upd Спасибо за участие! В связи с проведением вк-кап пересчёт рейтинг состоится немного позднее обычного.

Upd Опубликован разбор!

Можете также обратить внимание на неоффициальный разбор, который написал neal.