adamant's blog

By adamant, history, 2 weeks 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, 4 weeks 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, 4 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, 4 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, 5 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, 5 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, 12 months 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, 14 months ago, In English,

is it true that ?

Read more »

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

By adamant, 14 months 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, 15 months 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, 16 months 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, 19 months 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, 23 months 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, 2 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, 3 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, 3 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, 3 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, 3 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, 3 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, 3 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  

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

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.

Read more »

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

By adamant, 3 years ago, In Russian,

Всем привет!

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

Read more »

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

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

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

Read more »

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

By adamant, 3 years ago, In Russian,

Всем привет! Недавно меня заинтересовала такая задача: дано дерево с корнем в вершине 0. Поступают запросы двух видов.

  1. Добавить к вершине k сына.
  2. Выдать номер предка вершины k, у которого высота равна h.

Вершины пронумерованы в порядке добавления.

Пока что я знаю только два метода решения:

  1. Двоичный подъём. Ну тут всё очевидно, времени и памяти.
  2. С помощью индексированного двоичного дерева поиска (например, неявная дерамида) поддерживаем эйлеров обход графа. Далее либо сводим к k-ой порядковой статистике на префиксе, либо храним для каждой высоты список вершин и находим нужную бинарным поиском. Это потребует O(n) памяти, но времени (возможно, при грамотной реализации можно и , но я точно не знаю), ещё и с большущей константой.

Интересно то, что оба метода подозрительно похожи на LCA. В связи с этим возникает вопрос — может, задачу можно как-то свести к LCA непосредственно? Ну и, конечно, интересно, какие ещё есть способы решения этой задачи, в том числе и в оффлайне.

Read more »

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

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

Hi everyone! 2 years ago Logvinov_Leon asked about way to get the suffix array from suffix automata. Oddly enough, he had not received answer. However, as you may have noticed, I'm interested in the topic of transformations of some string structures to others, so I decided to shed some light on how this is done.

Read more »

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