TLE's blog

By TLE, history, 2 months ago, In English,

1081A - Definite Game

Idea: yjq_naiive Developer: yjq_naiive

Code (yjq_naiive)

1081B - Farewell Party

Idea: yanQval Developer: yanQval

Code (yanQval)

1081C - Colorful Bricks

Idea: fjzzq2002 Developer: fjzzq2002

Code1 (fjzzq2002)
Code2 (fjzzq2002)

1081D - Maximum Distance

Idea: fateice Developer: fateice

Sorry for the weak pretest.

Code (fateice)

1081E - Missing Numbers

Idea: fjzzq2002 Developer: fjzzq2002

Code1 (fjzzq2002)
Code2 (fjzzq2002)

1081F - Tricky Interactor

Idea: fjzzq2002 Developer: fateice, fjzzq2002

Yet another binary search?

Code (fjzzq2002)

1081G - Mergesort Strikes Back

Idea: quailty Developer: fateice, fjzzq2002, yjq_naiive

Code (fjzzq2002)

1081H - Palindromic Magic

Idea: fjzzq2002 Developer: fjzzq2002, yjq_naiive

This problem is quite educational and we didn't expect anyone to pass. :P

Code (yjq_naiive)

Hope you enjoyed the round! See you next time!

Read more »

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

By TLE, 2 months ago, In English,


I'm glad to invite you to participate in Avito Cool Challenge 2018 which starts on Dec/16/2018 17:35 (Moscow time). The round will be rated to participants of both divisons.


The problem setters are fjzzq2002, yjq_naive, fateice, yanQval and quailty.

We would like to thank:

This round is conducted on the initiative and support of Avito. is a Russian classified advertisements website with sections devoted to general good for sale, jobs, real estate, personals, cars for sale, and services. is the most popular classifieds site in Russia and is the third biggest classifieds site in the world after Craigslist and the Chinese website

Avito presents nice gifts for participants. Top 30 participants and also 10 random participants with places 31-130 will be awarded with a special T-shirt.

You will be given 8 problems and 2.5 hours to solve them. As usual, the score distribution will be revealed shortly before the contest.

This is the first contest on Codeforces for most of us. Hope to see you participating! Good luck!

There will be an interactive problem in the round. If you have never solved interactive problems before, please read this.

UPD: The scoring distribution is standard 500-1000-1500-2000-2500-3000-3500-4000.

UPD: Congratulations to winners!

Also, you can find the list of T-shirt receivers here.

UPD: Editorial

Read more »

Announcement of Avito Cool Challenge 2018
  • Vote: I like it  
  • +557
  • Vote: I do not like it  

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

Hello CodeForces Community!

It’s time to gear up for CodeChef’s November Long Challenge sponsored by ShareChat! 10 days of coding fun plus opportunities to work at ShareChat! More details can be found on the contest page.

Joining me on the problem setting panel are:

  • Admin: mgch (Misha Chorniy)
  • Problem Tester: fjzzq2002 (Zhong Ziqian)
  • Editorialist: taran_1407 (Taranpreet Singh)
  • Problem Setters: yjq_naiive (Xiuhan Wang), bciobanu (Bogdan Ciobanu), altruist (Denis Anishchenko), fjzzq2002 (Zhong Ziqian), teja349 (Teja Vardhan Reddy), adamant (Alexander Kulkov), danya.smelskiy (Danya Smelskiy), Shivam Gupta, hm2 (Himanshu Mishra), well_ (Sumegh Roychowdhury)
  • Statement Verifier: Xellos (Jakub Safin)
  • Russian Translator: Fedosik (Fedor Korobeinikov)
  • Mandarin Translator: huzecong (Hu Zecong)
  • Vietnamese Translator: VNOI Team
  • Hindi Translator: Akash Srivastava
  • Bengali Translator:solaimanope (Mohammad Solaiman)

I enjoy this set of problems personally and hope you will enjoy solving them too. You can give your feedback on the problem set in the comments below, after the contest.

Contest Details:

Time: 2nd November 2018 (1500 hrs) to 12th November (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Contest link:

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. First to solve each problem except challenge — 100 laddus. Know more here.
(For those who have not yet got their previous winning, please send an email to

Good Luck and Have Fun! Hope to see you participating!

Read more »

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

By TLE, history, 6 months ago, In English,


It seems there isn't any blog about Berlekamp-Massey Algorithm around here, so I decided to go on a try. :P

Acknowledgement: Hats off to matthew99 for introducing this algorithm.

What is 'linear recurrence'?

Assuming there is a (probably infinity) sequence a0, - 1, we call this sequence satisfies a linear recurrence relation p1,, iff . (Obviously, if m ≥ n any p can do :P)

How to calculate k-th term of a linear recurrence?

For a polynomial , we define .

Obviously G satisfies G(f) ± G(g) = G(f ± g).

Because , if we let , then G(f) = 0. Also G(fx), G(fx2)... = 0. So G(fg) = 0 (g is any polynomial).

What we want is G(xk). Because G(fxk / f⌋) = 0, then .

Read more »

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

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

Two months ago, I came across a problem.

Initially there are n elements, they are in n tiles.

There are 3 kinds of queries:

  1. merge two tiles into one tile.
  2. split one tile into two tiles. (Formally for a tile of size k, split it into two tiles of size k1 and k2, k=k1+k2, the first tile contains the smallest k1 elements and the second tile contains the rest)
  3. find the k-th smallest element in one tile.

Recently I found this technique (in Chinese) which can be used to solve this problem. This blog is my own explanation :p

First, let's suppose the values in the sorted lists are integers between 1~n. If not, you may just sort and map them.

Let's build a segment tree for every sorted list, segment trees are built based on values (1~n). In every node of a segment tree stores how many numbers are in this range, let's call this the value of a node.

It seems that it requires O(nlogn) space to store every segment tree, but we can simply ignore the nodes that value=0, and really allocate these nodes only when their value become >0.

So for a sorted list with only one element, we simply build a chain of this value, so only O(logn) memory is needed.

int s[SZ]/*value of a node*/,ch[SZ][2]/*a node's two children*/;
//make a seg with only node p, return in the first argument
//call with sth. like build(root,1,n,value);
void build(int& x,int l,int r,int p)
    x=/*a new node*/; s[x]=1;
    if(l==r) return;
    int m=(l+r)>>1;
    if(p<=m) build(ch[x][0],l,m,p);
    else build(ch[x][1],m+1,r,p);

When we split a segment tree (sorted list), simply split two children recursively:

//make a new node t2, split t1 to t1 and t2 so that s[t1]=k
void split(int t1,int& t2,int k)
    t2=/*a new node*/;
    int ls=s[ch[t1][0]]; //size of t1's left child
    if(k>ls) split(ch[t1][1],ch[t2][1],k-ls); //split the right child of t1
    else swap(ch[t1][1],ch[t2][1]); //all right child belong to t2
    if(k<ls) split(ch[t1][0],ch[t2][0],k); //split the left child of t1
    s[t2]=s[t1]-k; s[t1]=k;

When we merge two sorted lists, merge them forcely:

//merge trees t1&t2, return merged segment tree (t1 in fact)
int merge(int t1,int t2)
    if(t1&&t2);else return t1^t2; //nothing to merge
    s[t1]+=s[t2]; /*erase t2, it's useless now*/ return t1;

Also, just query k-th simply.

//query k-th of segment tree x[l,r]
int ask(int x,int l,int r,int k)
    if(l==r) return l;
    int ls=s[ch[x][0]]; //how many nodes in left child
    int m=(l+r)>>1;
    if(k>ls) return ask(ch[x][1],m+1,r,k-ls);
    return ask(ch[x][0],l,m,k);

It looks very simple, isn't it? But its total complexity is in fact O(nlogn).


Happy new year~

Read more »

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