TLE's blog

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

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, DarkestLight (Mohammad Nematollahi), Taran_1407 (Taranpreet Singh), danya.smelskiy (Danya Smelskiy)
  • Tester: TLE (Zhong Ziqian)
  • Editorialist: adamant (Alexander Kulkov)
  • Statement Verifier: xellos (Jakub Safin)
  • Russian Translator: Fedosik (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
  • Contest link: https://www.codechef.com/APRIL19
  • 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 winners@codechef.com)

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!

Read more »

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

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

1081A - Определенная игра

Idea: yjq_naiive Developer: yjq_naiive

Hint
Solution
Code (yjq_naiive)

1081B - Прощальная вечеринка

Idea: yanQval Developer: yanQval

Hint
Solution
Code (yanQval)

1081C - Цветные кирпичики

Idea: fjzzq2002 Developer: fjzzq2002

Hint
Solution
Code1 (fjzzq2002)
Code2 (fjzzq2002)

1081D - Максимальное расстояние

Idea: fateice Developer: fateice

Sorry for the weak pretest.

Hint
Solution
Code (fateice)

1081E - Недостающие числа

Idea: fjzzq2002 Developer: fjzzq2002

Hint
Solution
Code1 (fjzzq2002)
Code2 (fjzzq2002)

1081F - Коварный интерактор

Idea: fjzzq2002 Developer: fateice, fjzzq2002

Yet another binary search?

Hint
Solution
Code (fjzzq2002)

1081G - Сортировка слиянием наносит ответный удар

Idea: quailty Developer: fateice, fjzzq2002, yjq_naiive

Hint
Solution
Code (fjzzq2002)

1081H - Палиндромная магия

Idea: fjzzq2002 Developer: fjzzq2002, yjq_naiive

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!

Read more »

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

By TLE, 6 months ago, In English,

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.

img

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

Read more »

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

By TLE, history, 8 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: www.codechef.com/NOV18

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 winners@codechef.com)

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, 10 months ago, In English,

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

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

Proof

Happy new year~

Read more »

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