Hi everyone!

It's been a while since I posted anything. Today I'd like to talk about problem I from Oleksandr Kulkov Contest 2. Well, on some similar problem. Problem goes as follows: There is a rational number $$$x=\frac{p}{q}$$$, and you know that $$$1 \leq p, q \leq C$$$. You want to recover $$$p$$$ and $$$q$$$ but you only know number $$$r$$$ such that $$$r \equiv pq^{-1} \pmod{m}$$$ where $$$m > C^2$$$. In original problem $$$m$$$ was not fixed, instead you were allowed to query remainders $$$r_1,\dots,r_k$$$ of $$$x$$$ modulo several numbers $$$m_1,\dots,m_k$$$, which implied Chinese remainder theorem.

Hi everyone!

This summer I gave another contest in summer Petrozavodsk programming camp and (although a bit lately) I want to share it with codeforces community by adding it to codeforces gym: 2018-2019 Summer Petrozavodsk Camp, Oleksandr Kulkov Contest 2. To make it more fun I scheduled it on Sunday, 5 january, 12:00 (UTC+3). Feel free to participate during scheduled time or, well, whenever you're up to. Good luck and have fun :)

Problems might be discussed here afterwards, I even may write some editorials for particular problems (per request, as I don't have them prepared beforehand this time).

UPD: 17h reminder before the start of the contest

UPD2: It wasn't an easy task to do, but I managed to add ghost participants to the contest! Enjoy!

Hi there!

During preparation of Oleksandr Kulkov Contest 1 I started writing some template for polynomial algebra (because 3 problems in contest in one or another way required some polynomial operations). And with great pleasure I'd like to report that it resulted in this article on cp-algorithms.com (English translation for e-maxx) and this mini-library containing all mentioned operations and algorithms (except for Half-GCD algorithm). I won't say the code is super-optimized, but at least it's public, provides some baseline and is open for contribution if anyone would like to enhance it!

Article also provides some algorithms I didn't mention before. Namely:

• Interpolation: Now the described algorithm is and not as it was before.
• Resultant: Given polynomials A(x) and B(x) compute product of A(μ_i) across all μ_i being roots of B(x).
• Half-GCD: How to compute GCD and resultants in (just key ideas).

Feel free to read the article to know more and/or use provided code :)

tl;dr. article on operations with polynomials and implementation of mentioned algorithms.

Okay, so compare these two submissions: 51053654 and 51053605

The only difference is that first one made via GNU C++17 and the second one via MS C++ 2017. Code is same, but first gets RE 16 and second one gets AC.

WTF, GNU C++??

Hi everyone!

I gave a contest in winter Petrozavodsk programming camp and now I'd like to share it with codeforces by making it a contest in codeforces gym: 2018-2019 Зимние Петрозаводские сборы, Oleksandr Kulkov Contest 1. It was my first experience giving a contest to the camp and I'm pretty much excited about it!

In the camp only 7 out of 11 problems were solved, so there should be something in the contest for everyone. To make the contest more interesting I suggest you to participate in it as live contest on Saturday, 9 March, 12:00 (UTC+3), which may be changed in case of overlap with some other contest or if it's inconvenient for many participants. After this I suggest to gather here and discuss problems (if anyone's going to participate, of course). I will also post editorial which may (or may not) contain some neat stuff.

Uhm, good luck and have fun :)

P.S. It appears you already may see problems if you have coach mode enabled, I'd ask you to not do this unless you're not going to participate in contest!

UPD: Gentle reminder that it's less than 24 hours before the contest and it's hopefully not going to be rescheduled this time.

UPD 2: Thanks everyone for participating in the contest! Here are editorials: link

UPD 3: Google drive link got broken, so I uploaded the editorial to the contest directly.

Hi there!

Consider the following problem: You're given set of n items with weights a₁, ..., a_n. How many ways are there to select k items (order of choosing matters) with total weight of m (let's denote it as b_m)? There are two main variants of the problem:

• You may take any item arbitrary number of times. In this case b_m = [x^m](x^a₁ + ... + x^a_n)^k.
• You may take each item exactly once. In this case b_m = m...(1 + yx^a_n)

First case is quite explicit and allows you to calculate answer in like as .

But what about the second? If you define P(x) = x^a₁ + ... + x^a_n and Q_k(x) = b₀ + b₁x + b₂x² + ..., you may say for example that Q₁(x) = P(x), Q₂(x) = P²(x) - P(x²) or Q₃(x) = P³(x) - 3P(x)P(x²) + 2P(x³) which allows to calculate Q_k(x) for small k quickly. But does anybody know any fast way to calculate Q_k(x)? Newton's identities seem to allow something like if I'm not mistaken. Can anybody suggest any faster algorithm?

Hi everyone!

As you may know, I'm an attention whore seeker. For this (well, not only this) reason year and almost a half ago I've created public page on vk.com: Зайчатки разума. Name is some old Russian semi-linguistic meme without adequate English translation, thus I decided to use 'Mindbun' as presumably closest to literal translation as English name. There was announce on codeforces, which didn't get any particularly positive or negative reaction. Or any reaction at all :)

On that page I mostly post maths things interesting to me and information of any similar activities by me on other places (like, here). It serves as some kind of public notebook to me. Why won't I just post stuff on codeforces, as before? Well, my tastes may be very specific and I'm greatly afraid that I will bother community by posting dozens of short posts on topics which only partially relevant to competitive programming and strongly imbalanced (on mentioned page there is like half of content is about polynomials and/or complex numbers). Thus I decided to throw my thoughts on some other channel and leave only 'big' content for codeforces.

And it was pretty successful as for me. VK page has 506 followers currently and I really enjoy making that stuff! You can see compilation of my older posts and newer ones (Russian, sorry!). So now I decided that it's good time for i18n. Thus I'm going to crosspost English versions of original VK public page in special telegram channel. Welcome! Also since I really like to chat with people, I also created Mindbun-related chat for anyone interested in it :)

And to give you some example of what's it like, I'll just provide you first post from the channel :)

P.S. Channel has not any content yet. I'll start by translating some newer posts from VK page, and will post any future entries there. I'd like to translate all the previous stuff, but there's vast of it and I really can't afford it right now, and I feel shy about some of my older posts :(

P.P.S. I would really appreciate your feedback on the following question: how should I inform on updates in Mindbun here? There are several variants I'm considering right now.

• Post only big stuff on codeforces and keep notes to Mindbun only
• Make some kind of digest with updates once a... Week? Month? Year? Random moment of time?..
• Any other formats I haven't considered yet?

Hi everyone! This one will be long and contain a lot of off-topic, prepare yourself (or skip down to solution of mentioned problem)!

Intro

In this blog post I would like to talk about some problem that somehow was on my mind for several years and yet only now I have some more or less complete understanding of how to deal with it. The problem is as follows:

You're given string S and q queries. In each query you have to count amount of distinct substrings of S[l, r].

Hi there! Imagine you're participating in codechef long challenge and you see a problem from chemthan asking you to calculate some sums of powers like 1^p + 2^p + ... + n^p for all p from 0 to k. You immediately understand what's going on here and take Faulhaber's formula from your wide pants, do ya? Just take a look at it!

Beautiful, right? Wrong! This formula is dumb and it's hard to understand and remember! Why would you ever think about Bernoulli's number on any contest which lasts less than a week? And what the hell are those Bernoulli numbers?! Here is what you should do:

Let S_p = 1^p + ... + n^p. Consider its exponential generating function (EGF):

Now you can simply find S₀, ..., S_k by finding inverse series for and multiplying it with . Enjoy your power sums without Stirling and/or Bernoulli numbers!

Exercise: Solve this problem in .

P.S. Yes, you basically perform the same calculations as in Faulhaber's formula, but now you hopefully understand what you're doing.

Hi everyone!

Perhaps you heard about github project on translating e-maxx. The thing is that project is actually more than just translating it. You see, there are bunch of algorithms and approaches which either do not have proper elaborations or have but they're written in some weird uncommon languages like, you know, russian or chinese. And there are some sites which just don't fit for this purpose for some reasons.

Years ago when I started doing competitive programming e-maxx.ru was the main resource to learn things. Things changed a bit now. E-maxx is Russian only and it wasn't updated for years. And now I hope that e-maxx-eng will manage to fill this gap of common resource for everyone to learn new things and keep updated on recent competitive programming tricks and new algorithms.

So I encourage everyone to collaborate in making e-maxx-eng comprehensive guide into competitive programming, and not only on hacktoberfests :). And to begin with I would like to share with you my article on convex hull trick and Li Chao tree I wrote for this resource. Enjoy!

If you were too lazy to read it thoroughly: There is a link to CHT and Li Chao tree article just above this sentence!

Всем привет!

Скучали? Уверен, что нет! Но так или иначе, вашему вниманию представляется ещё один раунд, к подготовке которого я приложил руку. Добро пожаловать в мир безыдейных задач, заунывно длинных и скучных условий и плоских шуток в анонсах.

В этот раз раунд для вас готовили Ильдар Гайнуллин (300iq) и я (ну мне стыдно делать ссылку с этим цветом, сами знаете, кто). Мы хотим поблагодарить Владислава Исенбаева (winger), Константина Семёнова (zemen), Алексея Шмелева (ashmelev), Ивана Смирнова (ifsmirnov) и Александра Фетисова (AlexFetisov) за прорешивание раунда и помощь в подготовке. Также отдельная благодарность отходит Николаю Калинину (KAN) за его помощь в роли координатора и, конечно, MikeMirzayanov за polygon и codeforces.

Мы очень надеемся, что вам понравятся задачи, удачи на контесте!

UPD. Также спасибо akvasha за то, что любезно дополнил наш проблемсет своей задачей.

UPD 2. The contest is over, congratulations to winners!

Div. 1:

1. dotorya
2. Um_nik
3. Radewoosh
4. ainta
5. dreamoon_love_AA

Div. 2:

1. UoA_Kaori
2. noelnadal
3. mtw
4. Kroma
5. Yjsu

Here are editorials.

Всем привет!

На следующей неделе начнётся Moscow International Workshop ACM ICPC. Я буду вести на этих сборах лекцию по быстрому преобразованию Фурье, в связи с чем я подготовил конспект, в котором описал большую часть того, что нужно знать про него для использования в контестах. Даже если вы считаете, что знаете FFT, советую посмотреть, там всё ещё могут быть новые идеи для вас. Ближе к лекции также будет английский вариант :)

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

UPD: Добавлена английская версия. Также в русской версии добавлен параграф про вычисление последовательностей методом разделяй и властвуй.

Hello CodeForces Community!

The clock is ticking and Chef is ready with Lunchtime meal of October. So get ready to knuckle down October Lunchtime and mark your calendars for below. Joining me on the problem setting panel, we have:

• Problem Setter: chemthan (Trung Nguyen)
• Problem Tester & Editorialist: adamant (Alexander Kulkov)
• Contest Admin: kingofnumbers (Hasan Jaddouh)
• Russian Translator: CherryTree (Sergey Kulik)
• Mandarin Translator: huzecong (Hu Zecong)
• Vietnamese Translator: Team VNOI

I hope you will enjoy solving them. Please give your feedback on the problem set in the comments below after the contest.

So, note down the details and be there when the contest starts:

Time: 28th October 2017 (1930 hrs) to (2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: https://www.codechef.com/LTIME53

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Prizes: * Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://www.codechef.com/laddu. (For those who have not yet got their previous winning, please send an email to [email protected])

Good Luck! Hope to see you participating!!

Всем привет!

Я тут подал предложение о введение PBDS из SGI STL в российскую национальную рабочую группу по стандартизации С++. Кто не в курсе -- это проработанный концепт сбалансированных бинарных деревьев, с достаточно гибкой возможностью поддержки метаданных в вершинах (см. здесь). Для нас наиболее видная особенность -- наличие встроенных order_of_key и find_by_order, которые отсутствуют в set и map. В случае добавления pbds в стандарт мы также можем ожидать, что там, наконец, починят merge и split, которые сейчас работают за вместо заявленных .

Предлагаю сообществу codeforces поучаствовать в обсуждении данного предложения.

UPD: Предложение на std-proposals.

Hi everyone!

tl;dr. If you write the following code:

void dfs_sz(int v = 0) {
    sz[v] = 1;
    for(auto &u: g[v]) {
        dfs_sz(u);
        sz[v] += sz[u];
        if(sz[u] > sz[g[v][0]]) {
            swap(u, g[v][0]);
        }
    }
}

void dfs_hld(int v = 0) {
    in[v] = t++;
    for(auto u: g[v]) {
        nxt[u] = (u == g[v][0] ? nxt[v] : u);
        dfs_hld(u);
    }
    out[v] = t;
}

Then you will have such array that subtree of correspond to segment and the path from to the last vertex in ascending heavy path from (which is ) will be subsegment which gives you the opportunity to process queries on pathes and subtrees simultaneously in the same segment tree.

Inspired by Vladyslav's article and Alex_2oo8's problem Persistent Oak. You can find my solution to this problem here to learn how it can be used to maintain persistent hld over the tree.

Всем привет!

Я тут всё пишу разбор к June Challenge на Codechef. Задача Euler Sum может быть решена довольно интересной идеей, которой, как мне кажется, стоит поделиться. Спасибо I_love_natalia за то, что поделился. Собственно, вот:

Всем привет!

Мне понравилась идея тезисно излагать интересные вещи и идеи, как это было в предыдущем моём одноимённом посте. К сожалению, Codeforces не вполне предназначен для такого формата, так как подразумевает скорее редкие, но обширные и детализированные посты, чем относительно частые и короткие, что было бы удобнее мне. Но мне всё же захотелось попробовать писать в другом формате, поэтому я решил в тестовом режиме завести под это дело паблик вконтакте. Пока что там 10 постов, но в планах вести там активность регулярно. Надеюсь, будет интересно :)

В общем, вот: https://vk.com/mindbun

Всем привет!

Любители ли вы задачи, которые расчитаны на Ad Hoc решение? Я — терпеть не могу! Поэтому я решил сделать подборку идей, которые могут быть применены к достаточно большому классу задач. Добавляйте ещё, если о чём-то забыл. :)

is it true that ?

Hi everyone!

23^rd edition of Week of Code will start soon. This time challenges were set by me (adamant) and tested by wanbo. Also thanks CherryTree for some help. This is first contest which entirely consists of my problems and I tried my best to make them interesting to you. Hope everyone will find at least one problem that matches ones taste :)

P. S. And some rules if you don't know them yet: Monday through Sunday, one new challenge will be unlocked each day for you to solve. The maximal score decreases by 10% at the end of every 24 hours. Your submissions will run on hidden test cases at the end of every 24 hours. Only the last submission time counts. And as usual, the top 10 hackers on the leaderboard win exclusive HackerRank T-shirts.

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

Hi everyone!

As you may know, it is possible to build a suffix automaton for a set of strings as well as suffix tree consisting of all suffixes of strings from the set. Question is as follows: for each string S_k consider set V_k of vertices/states of tree/automaton that corresponds to the substrings of S_k. Is it true that ? Can you prove it or make a counter-example?

Всем привет!

Да-да, вы всё правильно поняли, после долго перерыва в четыре месяца с того момента, как на codeforces был последний div. 1 раунд, не приуроченный к какому-нибудь соревнованию, вы вновь имеете уникальнейшую возможность поучаствовать в обычном codeforces-раунде. Да, именно то, что написано на упаковке.

Никаких футболок для top-x участников! Никаких многоуровневых систем отбора за право бороться за суперприз! Никаких эзотерических языков или оптимизационных задач! Да мы вам даже разбалловку до самого конца раунда не объявим! Всё будет именно так, как это было в старые добрые времена.

Итак, этот раунд для вас готовили Иван Смирнов (ifsmirnov) и я (adamant). Мы хотим поблагодарить Максима Ахмедова (Zlobober), Александра Фролова (fcspartakm), Эдварда Давтяна (Edvard) и Михаила Мирзаянова (MikeMirzayanov) за помощь в подготовке раунда, его прорешивание и дельные советы. Отдельно спасибо Edvard за то, что он выступил в роли координатора в этот раз и традиционно MikeMirzayanov за системы polygon и codeforces.

Всем удачи! Мы очень надеемся, что вы получите получите много удовольствия, участвуя в раунде :)

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

Div. 2: 500-1000-1500-2000-3000

Div. 1: 500-1000-2000-2000-3000

UPD. 2. Также спасибо большое Александру Фетисову (AlexFetisov). Прости, пожалуйста, совсем забыл тебя отметить :)

UPD. 3 Если вы пропустили разбор, то он здесь.

Всем привет!

Осенью на физтехе проходили сборы по программированию Moscow International Workshop ACM ICPC. На них мне довелось прочесть лекцию по суффиксным структурам (на самом деле, были затронуты только суффиксное дерево и суффиксный автомат). В связи с этим я хотел бы предоставить вашему вниманию конспект лекции. Собственно, вот русская и английская версии. Приятного просмотра и счастливого Нового года :)

P.S. любая критика, предложения, пожелания и вопросы всячески приветствуются.

P. P. S. Я попытался достаточно подробно описать доказательство линейности работы, но, скорее всего, оно до сих пор тяжело воспринимается. Вы получите +100 единиц кармы, если разберётесь в нём и предложите более простой для понимания вариант :)

UPD: Спасибо Burunduk1 за помощь в форматировании кода :)

UPD2: См. также статью на Википедии по этой теме. Я являюсь основным автором текущей (29 октября 2021) версии статьи.

Всем привет!

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

Итак, сама задача: дана строка S. Разбейте её на минимально возможное число палиндромов. Довольно незатейливо, не так ли? Задача довольно популярна. Её можно найти, например, здесь или здесь. Однако, где бы вы её не нашли, ожидаемое решение в лучшем случае будет квадратичным (а то и кубическим). Здесь же будет описано решение этой задачи за в онлайне относительно приписывания символа в конец строки (т.е. ответ будет получен для каждого префикса). Также будет рассмотрена задача разбиения строки на k палиндромов и её сведение к разбиению на минимальное число палиндромов.