Hello. I can't seem to figure out this problem's solution. I've read the editorial and I understand the first part but when the author says:

"To further optimize this solution, another transformation is needed. Ideally, we would like each ai to contribute to the answer independently of other values. And this can almost be achieved. Notice that the maximum returns 0 only if ai<ai−1 for any k, not just for k=1. This may require proof, but it is quite obvious."

I just don't get what this means. I also don't know what he's tryna do with the ci coefficient. I'd really appreciate it if someone here could explain it to me.

Alrighty which one would you choose if you were in my position?

Hello everyone,

I have updated the rating distribution histogram for this year and I have created rating percentiles so you can find out how you compare against other active users. I define an active user as a user who has 1) participated in the last 6 months and 2) participated in at least 6 contests. The second condition is to ensure that the user's rating is stabilized.

Here is the chart (n = 89352):

clearer version

And here are some previous years' histograms: 2023 note: uses >= 5 contest participations instead of >= 6 participations. 2021 note: the author of this post wrote the script that creates very nice histograms so credit to him.

Some interesting facts:

The median Codeforces rating is 1143. The mean rounded to the nearest integer is 1205. The standard deviation is 378 rounded down to the nearest integer.

A rating of 1900 places you at the 94th percentile.

A rating of 2400 places you at the 99.2nd percentile.

The minimum rating for an LGM, 3000, is at the 99.93rd percentile.

55% of Codeforces users are gray.

If you want to see an exact rating percentile, go here.

If you want to see the rating data, go here. The data is in python dictionary format.

That is all, I hope this was interesting.

My rating is remarkably stable. I bet you wish you were me with how stable my rating is. I was worried for a second that I might accidentally improve in the recent pinely contest, but thankfully I couldn't solve C and luckily for me my rating converged right under expert: the place where it is meant to stay forever.

My personal favorite has got to be tries. Almost every problem out there can be solved using some variation of a trie, which is why they are so cool. It feels like everything in programming, in one way or another, is, in an abstract sense, a trie.