adamant's blog

By adamant, history, 3 weeks ago, In English,

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?

Read more »

 
 
 
 
  • Vote: I like it  
  • +117
  • Vote: I do not like it  

By adamant, history, 6 weeks ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +247
  • Vote: I do not like it  

By adamant, history, 4 months ago, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it  
  • +131
  • Vote: I do not like it  

By adamant, history, 10 months ago, In English,

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!

Read more »

 
 
 
 
  • Vote: I like it  
  • +191
  • Vote: I do not like it  

By adamant, 11 months ago, translation, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it  
  • +959
  • Vote: I do not like it  

By adamant, history, 12 months ago, translation, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it  
  • +201
  • Vote: I do not like it  

By adamant, 13 months ago, translation, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +55
  • Vote: I do not like it  

By adamant, history, 16 months ago, translation, In English,

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?

Read more »

 
 
 
 
  • Vote: I like it  
  • +82
  • Vote: I do not like it  

By adamant, 16 months ago, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it  
  • +296
  • Vote: I do not like it  

By adamant, 17 months ago, In Russian,

Всем привет!

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +26
  • Vote: I do not like it  

By adamant, 17 months ago, In Russian,

Всем привет!

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

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +58
  • Vote: I do not like it  

By adamant, 2 years ago, translation, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +296
  • Vote: I do not like it  

By adamant, history, 2 years ago, In English,

is it true that ?

Read more »

 
 
 
 
  • Vote: I like it  
  • +40
  • Vote: I do not like it  

By adamant, 2 years ago, translation, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it  
  • +47
  • Vote: I do not like it  

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

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.

Read more »

 
 
 
 
  • Vote: I like it  
  • +128
  • Vote: I do not like it  

By adamant, history, 2 years ago, In English,

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?

Read more »

 
 
 
 
  • Vote: I like it  
  • +46
  • Vote: I do not like it  

By adamant, 3 years ago, translation, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it  
  • +694
  • Vote: I do not like it  

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

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.

Read more »

 
 
 
 
  • Vote: I like it  
  • +209
  • Vote: I do not like it  

By adamant, 3 years ago, translation, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +62
  • Vote: I do not like it  

By adamant, 4 years ago, translation, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it  
  • +104
  • Vote: I do not like it  

By adamant, 4 years ago, translation, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it  
  • +141
  • Vote: I do not like it  

By adamant, 4 years ago, translation, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it  
  • +100
  • Vote: I do not like it  

By adamant, 4 years ago, translation, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +160
  • Vote: I do not like it  

By adamant, 4 years ago, translation, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it  
  • +52
  • Vote: I do not like it  

By adamant, 4 years ago, translation, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it  
  • +79
  • Vote: I do not like it