Help with codeforces problem

I was trying to solve a codeforces problem https://codeforces.com/contest/713/problem/C.
Basically we have to convert a sequence in minimum increment decrement operations to a strictly increasing sequence.
To solve the problem, every element of the sequence a[i] is subtracted by i and then the problem changes to coverting the array to a Non-increasing sequenc.

The solution that I thought of was naive(I am a beginner in competitive coding), so I read the editorial. I understood the dynamic programming solution but then I found a blog post - https://codeforces.com/blog/entry/47821 that describes an (nlogn) solution to the problem.
I tried hard to understand the details but I do not understand why they are considering slope and that too when they already have a recurrence relation at the start. After looking at the implementation, basically what they did I think was just consider the largest element found so far in the sequence and keep it as the key point. Any other element that is less than that number is changed to that number rather than considering decreasing the larger number because this reduces the chances of further modification in array. Is there something I am missing which was the point of whole mathematical slope analysis. I would appreciate if anybody could shed some light in simple manner as to what the blog tries to say or explain the why this approach is correct in simple manner. Here is the implementation

#include<stdio.h>
#include<queue>
 
int main()
{
	int n, t;
	long long ans = 0;
	std::priority_queue<int> Q;
	scanf("%d%d", &n, &t);
	Q.push(t);
	for(int i=1; i<n; i++)
	{
		scanf("%d", &t); t-=i;
		Q.push(t);
		if(Q.top() > t)
		{
			ans += Q.top() - t;
			Q.pop();
			Q.push(t);
		}
	}
	printf("%lld", ans);
	return 0;
}

1 Like

I have been stuck on this problem for many days now. Any hint ot explanation is rrally appreciated.

2 Likes

Do I need to edit something? Nobody interested in discussing a codeforces problem. That is surprising.

2 Likes