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 (300iq) 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_love_AA

Div. 2:

1. UoA_Kaori
2. noelnadal
3. mtw
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 [email protected])

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 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.

// 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.

UPD2: Please also refer to Wikipedia article on this topic. I'm the main author of its current (29 Oct 2021) version.

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.

Hi everyone!

This time I would like to write about the Aho-Corasick algorithm. This structure is very well documented and many of you may already know it. However, I still would try to describe some of the applications that are not so well known.

Hi everyone!

As some of you may know, on this summer camp in Petrozavodsk droptable presented a new data structure, palindromic tree. I had the honor to participate in the study of the structure for the six months before that, and I want to tell about it now :)

Hi everyone!

Today summer Petrozavodsk summer training camp 2014 has been started. I hope that I don't violate any unofficial taboo by writing about it :)

If you, just like me, are in a group of people who do not have the opportunity to participate in this celebration of life, you can follow the camp, for example, at SnarkNews or acm.math.spbu.ru.

Hi everyone!

Some of you may remember my entry about policy based data structures. In addition to a review article on these structures, I also wanted to write about the possibility of using your own Node_Update class. Then I hadn't enough time for it, but now I can and I want to catch up and share with you some new knowledge.

Hi everyone!

I recently read about such an interesting data structure as skip-list. It seemed to me, the structure is very interesting and at the same time easy to use. That is the reason I decided to experiment with the structure in various problems and try to implement the various modifications of it.

Hi everyone!

It's no secret that in competitive programming we often have to work with graphs^{[citation needed]}. We also often have to draw graphs. And maybe some people already know that there is tool for visualization of graphs called GraphViz, which parses the DOT code into visual image with the corresponding graph.

Example of a graph that can be obtained using graphviz — compressed suffix tree for the string abaabbaaa. Yes, the graph contains a small mistake, but it is not important :)

Now, actually, to the subject. How do you feel about adding DOT language support to the Codeforces editor? I think it would be cool, and you? :)