rlajkalspowq's blog

By rlajkalspowq, 4 years ago, In English

Finally ARC comes back...

I think ARC is suitable for people with rating between 2000 and 2200 on CF because ABC is a bit easy for them and AGC is a bit difficult. So it's really a delight to see the return of ARC.

Anyway, I would like to know what is the reason behind the disappearance of ARC for two years. Can anyone tell me?

Full text and comments »

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

By rlajkalspowq, history, 5 years ago, In English

You're given $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$, you need to count the number of ways to choose some of them (no duplicate) to make the sum equal to $$$S$$$. Print the answer in modulo $$$10^9+7$$$. How to solve this problem in polynomial time?

Note: The $$$n,S$$$ can be as large as $$$10^5$$$ so using single DP can't work. Using polygon $$$ln$$$ or $$$exp$$$ might work. But I don't know how to use them (I've just heard of it). Can anyone explain it?

Full text and comments »

  • Vote: I like it
  • -3
  • Vote: I do not like it

By rlajkalspowq, history, 5 years ago, In English

I'm recently thinking of a problem. Given a sequence $$$a$$$, find the value of $$$\sum_{l=1}^n \sum_{r=l+1}^n lis(a[l...r])$$$. Where $$$lis(a)=$$$ the longest non-decreasing sequence of $$$a$$$ and $$$n$$$ is the length of $$$a$$$. $$$n$$$ is large to $$$10^5$$$ and $$$a_i$$$ is extremely small, only $$$20$$$? I can't think of a solution. Can anyone help me? Please.

Full text and comments »

Tags lis
  • Vote: I like it
  • +3
  • Vote: I do not like it

By rlajkalspowq, history, 5 years ago, In English

Is it a bug or it is done intentially? Two contests with similar title make me feel nervous.

MikeMirzayanov vovuh please give a response after reading this blog.

UPD: the contest name has already been undated.

Full text and comments »

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