A hack for Problem C: "Set or Decrease" (Educational Round #120) [problem:1622C] ================== A few others and I had solutions for this problem that passed the system tests but had a bad time complexity of `O(aᵢ * t)`. The problem has `aᵢ <= 10^9` and `t <= 10^4` so `aᵢ * t` can be up to `10^13`, which could take over an hour for the code to run, and would obviously give the "Time Limit Exceeded" verdict. For any step, if you choose **set**, it is optimal to set the greatest element (that hasn't been set yet) equal to the smallest element, because this decreases the sum the most. If you choose **decrease**, it is optimal to decrease the smallest element. It's optimal to do all the **decrease**s before all the **set**s, because this way the largest elements can be set to an even lower number, compared to if any **set** step is done before a **decrease** step. My initial approach to this problem (with the wrong time complexity) was to simulate the steps one by one, on each step choosing greedily whether to **set** or **decrease**...

Full text and comments »

Codeforces rating deflation <div align="right"> <table> <tr> <td align="left"><em> &mdash; You know what they call an International Grandmaster in 2026?<br> &mdash; They don't call it an International Grandmaster?<br> &mdash; No, man, they got the AI there, they wouldn't know what International Grandmaster is.<br> &mdash; What'd they call it?<br> &mdash; They call it International Master. </em></td> </tr> </table> </div> ### Introduction There was a heated discussion recently, and I decided to quantify the rating deflation over the recent 1.5 years. After accounting for natural improvement, I found roughly 150-190 rating points of deflation. The following is the rating gap between AI period and pre-AI period.  ### Background - We need to estimate the recent rating dynamics and compare it with pre-AI dynamics. - Participants have natural improvement when they train, especially lower rated...

Full text and comments »