### TLE's blog

By TLE, history, 11 months ago,

Hello Codeforces!

Being asked to propose competitive programming questions is pretty haunting. When you're out of fresh ideas, I used to do one of the two things. One, is to search in the old pile of problems, hoping to find some room of modifications and improvements. The second, is to come up with random words, like "chessboard inversion counting", and hopefully resemble interesting problems from them.

This process is pretty boring, so I have been trying to use machine learning to generate ideas and even complete competitive programming problems. The result is CPIdeas! Check it out here: https://fjzzq2002.github.io/cpideas/.

How was it made? I collected problems from AtCoder (ABC, ARC, AGC) and used these problems to fine-tune GPT-3, the OpenAI model. It's quite tricky to get things right though and it's still far from perfect.

How should I use it? Look through these ideas. Scroll down. Be tolerant and creative. That's it.

How should I use these ideas? For the generated ideas/problems, I would say probably do not use the ideas directly as problems (although you certainly can). Definitely use the search engine before actually purposing the problems. There are ~7000 shuffled ideas in the website at the moment so it's quite unlikely that multiple users worked on the same idea but that's certainly another risk.

Here are some sample ideas. They're not super logical, but hopefully pretty inspiring.

You are given a sequence of N integers A=(A1,A2,...,AN). Find the number of sequences that satisfy the following conditions, modulo 998244353. 1<=Ai<=M. There exists a permutation P=(P1,P2,...,Pk) of (1,2,...,k) such that Ai<=Pi and Pi!=Ai+1.

You are given an integer sequence of length N : A=(A1,A2,...,AN). You can do the following operation on A any number of times: choose an integer i such that 1<=i<=N-1, and replace the last element of A with ai. You want to make A a permutation of (1,2,...,N). Find the minimum number of operations needed.

You are given a string S of length N. Let the number of occurrences of each character in S be num1, num2,..., numN. Find the number of pairs of integers (i,j) that satisfy the following condition: 1<=i<j<=N, and |num1-numj|+|num2-numj|+...+|numN-i-j|<=1.


Hopefully you'll enjoy this little tool I made! If you have any thoughts/comments/suggestions you can comment below.

• +604

By TLE, history, 3 years ago,

Hello Codeforces! It's a new decade already and I decided to write a tool to help me grab first bloods faster in Codeforces rounds, and I made it open-source since the Codeforces rules say so.

Everyone knows to grab first bloods faster, you need to write code and test samples with lightning speed. There's Hightail over there already but still, it's not the most comfortable tool for me to use.

I'm too lazy to repeat it all again since there's a README in the above link there already. You can see an image of it in action by clicking here (sadly I cannot insert GIFs directly). You can also comment here (github stars are also appreciated).

• +130

By TLE, history, 4 years ago,

Greetings Codeforces community!

I'm glad to invite you to participate in CodeChef's April Long Challenge sponsored by ShareChat. This long contest lasts for 10 days and will have 7 binary/subtask problems and 1 tie-breaker problem. This is a nice opportunity for everyone to increase your rating and climb up the leaderboard. The problem statements will be available in English, Hindi, Bengali, Russian, Mandarin and Vietnamese.

ShareChat — India's fastest growing social network is seeking both interns and full-time employees to join their dynamic team. Job opportunities are open to programmers across the world and internship opportunities are exclusively aimed at final year B.Tech students who have already been placed and looking forward to gaining startup experience. Visit the contest page for more details.

I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:

• Setters: raj1238 (Raj Shah), Sumit Jain, Ashishgup (Ashish Gupta), born.kira (Arun Gupta), Surya Prakash, Utkarsh Sinha, Jas Mehta, Deemo (Mohammad Nematollahi), taran_1407 (Taranpreet Singh), danya.smelskiy (Danya Smelskiy)
• Tester: TLE (Zhong Ziqian)
• Statement Verifier: Xellos (Jakub Safin)
• Russian Translator: Mediocrity (Fedor Korobeinikov)
• Mandarin Translator: huzecong (Hu Zecong)
• Vietnamese Translator: Team VNOI
• Bengali Translator: solaimanope (Mohammad Solaiman)
• Hindi Translator: Akash Shrivastava

#### Contest Details:

• Start Date & Time: 5th April 2019 (1500 hrs) to 15th April 2019 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone
• 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: https://www.codechef.com/laddu
(For those who have not yet got their previous winning, please send an email to [email protected])

As usual, you can give your feedback on the problem set in the comments below, after the contest. Good luck and have fun! Hope to see you participating!

• +64

By TLE, history, 4 years ago,

1081A - Definite Game

Idea: sunset Developer: sunset

Hint
Solution
Code (yjq_naiive)

1081B - Farewell Party

Idea: yanQval Developer: yanQval

Hint
Solution
Code (yanQval)

1081C - Colorful Bricks

Idea: TLE Developer: TLE

Hint
Solution
Code1 (fjzzq2002)
Code2 (fjzzq2002)

1081D - Maximum Distance

Idea: fateice Developer: fateice

Sorry for the weak pretest.

Hint
Solution
Code (fateice)

1081E - Missing Numbers

Idea: TLE Developer: TLE

Hint
Solution
Code1 (fjzzq2002)
Code2 (fjzzq2002)

1081F - Tricky Interactor

Idea: TLE Developer: fateice, TLE

Yet another binary search?

Hint
Solution
Code (fjzzq2002)

1081G - Mergesort Strikes Back

Idea: quailty Developer: fateice, TLE, sunset

Hint
Solution
Code (fjzzq2002)

1081H - Palindromic Magic

Idea: TLE Developer: TLE, sunset

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

Hint
Solution
Code (yjq_naiive)

Hope you enjoyed the round! See you next time!

• +154

By TLE, 4 years ago,

Hi!

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 TLE, sunset, fateice, yanQval and quailty.

We would like to thank:

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

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

Announcement of Avito Cool Challenge 2018
• +557

By TLE, history, 5 years ago,

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:

• Problem Tester: TLE (Zhong Ziqian)
• Editorialist: taran_1407 (Taranpreet Singh)
• Problem Setters: sunset (Xiuhan Wang), bciobanu (Bogdan Ciobanu), altruist (Denis Anishchenko), TLE (Zhong Ziqian), teja349 (Teja Vardhan Reddy), adamant (Alexander Kulkov), danya.smelskiy (Danya Smelskiy), Shivam Gupta, hm2 (Himanshu Mishra), sshhhh (Sumegh Roychowdhury)
• Statement Verifier: Xellos (Jakub Safin)
• Russian Translator: Mediocrity (Fedor Korobeinikov)
• Mandarin Translator: huzecong (Hu Zecong)
• Vietnamese Translator: VNOI Team
• Hindi Translator: Akash Srivastava

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.

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 [email protected])

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

• +121

By TLE, history, 5 years ago,

#IjustWantContribution

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, a1...an - 1, we call this sequence satisfies a linear recurrence relation p1, p2...pm, 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 .

• +1492

By TLE, history, 6 years ago,

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 http://blog.csdn.net/zawedx/article/details/51818475 (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
ch[t1][0]=merge(ch[t1][0],ch[t2][0]);
ch[t1][1]=merge(ch[t1][1],ch[t2][1]);
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;