By adamant, history, 2 months ago, ,

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 1p + 2p + ... + np 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 Sp = 1p + ... + np. Consider its exponential generating function (EGF):

Now you can simply find S0, ..., Sk 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.

•
• +131
•

By adamant, history, 8 months ago, ,

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!

•
• +191
•

By adamant, 9 months ago, translation, ,

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:

Div. 2:

Here are editorials.

•
• +959
•

By adamant, history, 11 months ago, translation, ,

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.

•
• +201
•

By adamant, 11 months ago, translation, ,

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)
• 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!!

•
• +55
•

By adamant, history, 14 months ago, translation, ,

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?

•
• +82
•

By adamant, 14 months ago, ,

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++;
rin[in[v]] = v;
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.

•
• +296
•

By adamant, 15 months ago, ,

Всем привет!

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

•
• +26
•

By adamant, 15 months ago, ,

Всем привет!

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

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

•
• +58
•

By adamant, 22 months ago, translation, ,

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

•
• +296
•

By adamant, history, 2 years ago, ,

is it true that ?

•
• +40
•

By adamant, 2 years ago, translation, ,

Hi everyone!

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

•
• +47
•

By adamant, history, 2 years ago, translation, ,

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.

•
• +128
•

By adamant, history, 2 years ago, ,

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 Sk consider set Vk of vertices/states of tree/automaton that corresponds to the substrings of Sk. Is it true that ? Can you prove it or make a counter-example?

•
• +46
•

By adamant, 2 years ago, translation, ,

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.

•
• +694
•

By adamant, history, 3 years ago, translation, ,

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.

•
• +209
•

By adamant, 3 years ago, translation, ,

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

•
• +62
•

By adamant, 4 years ago, translation, ,

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.

•
• +104
•

By adamant, 4 years ago, translation, ,

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.

•
• +141
•

By adamant, 4 years ago, translation, ,

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.

•
• +100
•

By adamant, 4 years ago, translation, ,

Hi everyone!

As some of you may know, on this summer camp in Petrozavodsk MikhailRubinchik 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 :)

•
• +160
•

By adamant, 4 years ago, translation, ,

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.

•
• +52
•

By adamant, 4 years ago, translation, ,

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.

•
• +79
•

By adamant, 4 years ago, translation, ,

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.

•
• +85
•

By adamant, 4 years ago, ,

Всем привет!

Буду краток. Возможно ли искать число K-инверсий быстрее, чем за ? Если да, то как? Если нет, то почему?

•
• +11
•