I think the main thing was just confidence in my ability to solve harder problems after getting the two really good performances. I see a lot of people who don't focus as hard as they can on problems that are slightly out of their comfort zone as they think they are 'too hard' — which becomes a self-fulfilling prophecy as with reduced focus they can't solve the problem.

I also think that a lot of it was just variance in topics (as I am generally better at math problems), and my jump in performance wasn't as large as the rating graph makes it look (I had plenty of master perfs near the end of 2020).

First, you binary search on the answer. If no value of $$$G$$$ works then the answer is $$$-1$$$. If a high enough value of $$$G$$$ works (say, $$$10^9 + 1$$$ works) then the answer is infinity.

So to check if a value of $$$G$$$ works, you want to find the longest subsequence $$$a$$$ in the given array where $$$a[i]−a[i−1]\geq G$$$ after assigning values to all of the $$$−1$$$ elements. You need to check if this subsequence has length at least $$$k$$$.

It is optimal to use as many $$$−1$$$ elements in the given array as possible. If you let $$$a[i]$$$ and $$$a[j]$$$ be immediately after eachother in the subsequence and you skip some $$$−1$$$ elements in the subarray $$$a[i+1, j−1]$$$, then you can replace one of $$$a[i]$$$ or $$$a[j]$$$ with a $$$−1$$$.

Now, let $$$dp[i]$$$ be the maximum length of a subsequence ending at $$$i$$$, where $$$a[i]$$$ is not $$$−1$$$. Let $$$p[i]$$$ be the number of $$$−1$$$ elements in the prefix $$$i$$$. From our observation, you only jump from $$$i$$$ to $$$j$$$ where $$$a[i]+G(p[j]−p[i]+1) \leq a[j]$$$, so $$$a[i]−p[i]∗G+G\leq a[j]−p[j]∗G$$$. You set $$$dp[i]=\max(dp[i],dp[j]+p[j]−p[i]+1)$$$ for all such j. This transition is easy to optimize with a segment tree