I am trying to solve a problem on codeforces. Given an integer array $a_1,\ldots,a_n$, our goal is to find the minimal number of instructions, each of which increments or decrements a single entry, needed to make the array strictly increasing. That is, we want to find an increasing integer array $b_1,\ldots,b_n$ while minimizing $|a_1 - b_1| + \cdots + |a_n - b_n|$.
By considering the array $a'_i = a_i - i$ instead, we can replace the condition of strictly increasing but the condition of nondecreasing.
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 that describes an $O(n\log n)$ solution to the problem.
I tried hard to understand the details, but there are two things I don't understand: why they consider slope, and why they have a recurrence relation at the very beginning.
After looking at the implementation, basically what they did I think was just to 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 the 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 in pseudocode, where the goal is to make the array nondecreasing rather than strictly increasing, and we are only interested in computing the cost (rather than actually modifying the array):
- Initialize cost to zero.
- Initialize a priority queue $Q$ with $a_1$.
- For $i = 2,3,\ldots,n$:
- Add $a_i$ to $Q$.
- If $\max(Q) > a_i$:
- Add $\max(Q) - a_i$ to the cost.
- Remove $\max(Q)$ from $Q$.
- Insert $a_i$ to $Q$.
- Return the cost.
The priority queue supports the following operations in $O(\log n)$:
- Compute the maximal element.
- Remove the maximal element.
- Add an arbitrary element.