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 Winter Petrozavodsk Camp, 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

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!

Hi everyone!

Missed me? I bet no! In either way, here goes another one round which I dared to spoil by my participation in problemsetting. Welcome to the world of extremely unoriginal problems, awkwardly long and boring statements and trifling jokes in anouncements.

This time round was prepared by Ildar Gainullin (gainullin.ildar) and me (I'm ashamed to place link of such color here, you know who). We want to thank Vladislav Isenbaev (winger), Konstantin Semenov (zemen), Alexey Shmelev (ashmelev), Ivan Smirnov (ifsmirnov) and Alex Fetisov (AlexFetisov) for testing problems and help in preparation. Also special thanks goes to Nikolay Kalinin (KAN) for his help as coordinator and, of course, MikeMirzayanov for polygon and codeforces.

We hope that you will enjoy the problems, good luck and have fun!

UPD. Also thanks to akvasha for completing our problemset by his problem.

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

Div. 1:

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

Div. 2:

1. UoA_Nirvana
2. noelnadal
3. Dededededestruction
4. Kroma
5. Yjsu

Here are editorials.

Hi everyone!

On this Saturday I'm giving a lecture on Fast Fourier Transform on Moscow International Workshop ACM ICPC. Due to this I wrote lecture notes which anybody can use as reference for Fast Fourier Transform. I added there almost anything one should need while using FFT in contests. Even if you suppose you know the algorithm I dare you to look this paper through since there still can be some new ideas for you. Also you can see Russian version here.

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 winners@codechef.com)

Good Luck! Hope to see you participating!!

Hi everyone!

I suggested adding policy based data structures from SGI STL into C++ standard. You can know this useful library from here. What do you think of it?

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 Nobik_Glem'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

// Finally translated!

Hi everyone!

Do you like ad hoc problems? I do hate them! That's why I decided to make a list of ideas and tricks which can be useful in mane cases. Enjoy and add more if I missed something. :)

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 already know (if you don't then I advice you to learn it), in 2D geometry it is convenient to use complex numbers to handling points operations and rotations. Now I would like to tell you about similar construction, which allows you to work efficiently with 3D geometry, in particular to use vectors and linear operations on them, calculate many popular operations (like dot or cross products) and maintain rotations in 3D space.

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?

Hi everyone!

Yeah, you guessed it right, after a long four month break after the latest div. 1 round which was not dedicated to any official competition, you will once again have the unique opportunity to participate in usual codeforces round. No t-shirts for top-x competitors! No multi-level selection system for the opportunity to compete in final! No esoteric languages or marathon-like problems! We even will not tell you the scoring untill the very end of the round! That's it, like the good old days.

So this round was prepared for you by Ivan Smirnov (ifsmirnov) and me (adamant). We want to thank Max Akhmedov (Zlobober), Alex Frolov (fcspartakm), Edvard Davtyan (Edvard) and Mike Mirzayanov (MikeMirzayanov) for the help in round preparing, and useful advice. Special thank to Edvard for taking the role of coordinator this time and traditionally MikeMirzayanov for polygon and codeforces systems.

Good luck to everyone! We really hope that you will have a lot of fun participating in this round :)

UPD. Score distribution:

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

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

UPD. 2. Also thanks a lot to Alex Fetisov (AlexFetisov). Forgive me, please, I have totally forgotten about you :)

UPD. 3. If you missed the editorial, you can find it here.

Hi everyone!

This summer in Moscow IPT was held Moscow International Workshop ACM ICPC. I gave a lecture on suffix structures there (it was only about suffix automaton and suffix tree actually). In this regard, I would like to present to you the lecture notes. So here are Russian and English versions. Enjoy and Happy Holidays :)

P. S. My very apologies for my bad English :(

UPD: Thanks to Burunduk1 for help in code formatting.

Hi everyone!

Today I want to talk about one quite famous and interesting problem.

So, here it is: given string S. Split it in the minimum possible amount of palindromic strings. Rather unpretentious, isn't it? You can find this problem here or here. But whenever you see it, in the best case intended solution would be a quadratic (or even cubic). Here will be described a solution to this problem in online (ie, answer will be received for each prefix).

First part, I guess. Even if you think that you are familiar with suffix tree, please, take a look at the code below. It may be interesting to you.

Hi everyone! Finally I learnt this one :)

In this entry I would like to avoid long and complex theory which scared me from suffix tree for a long time. So straight to the point. I will not prove algorithm if you want some proofs, you may check stackoverflow or Dan Gusfield's book... Or somewhere else, I don't know.

Hi everyone!

Recently, at the MIPT: The Fall training camp on the contest from Alexander Milanin was a problem from Petr Mitrichev Contest 7. We were given a graph and a set of queries like "suppose we removed from the graph k ≤ 4 edges. Check whether graph is still connected?" I want to talk further about the solution of a more general problem, when the edges are added and removed without additional constraints in offline. The first algorithm with such an assessment was offered by David Eppstein in 1992, reducing it to fully dynamic minimum spanning tree problem, but here we will focus on a simple algorithm, proposed in 2012 by Sergei Burunduk1 Kopeliovich.