Puzzle Statement:
You are given an array $$$[a_1, a_2, a_3 ... a_N]$$$ and two other numbers $$$N$$$ and $$$K$$$ to make the array correct.
Correct array is the array where all the absolute differences between all consecutive pairs are less than or equal to $$$K$$$ in other words $$$|a_i - a_{{i+1}}| \le K$$$ for each $$$i$$$ $$$(0 \le i < N - 1)$$$.
You can only make two operations, either increase one element $$$a_i$$$ in the array by $$$1$$$ or decrease it.
You should return the minimum number operations to make the array correct.
$$$N$$$ $$$(1 \le N \le 2 \cdot 10^5)$$$ is the number of elements in the array and each element $$$a_i$$$ in the array $$$[a_1, a_2, a_3 ... a_N]$$$ is in range $$$(0 \le a_i \le 10^9)$$$.
$$$K$$$ $$$(0 \le K \le 10^9)$$$ is the number that you should make the absolute differences between the consecutive elements in the array less than or equal to.
time limit per test: 1 second
memory limit per test: 64 megabytes
Discussion:
I have come up with modeling the problem as graph by adding source before the first element and sink after the last element in the array. And for each element in the array we have a separate column of vertices that represent candidate values that that element value can become by increasing or decreasing it. The range for those vertices is $$$(min(a_i) \le v_i \le max(a_i))$$$ and the cost of edges entering each vertex will have the difference of that vertex value from the initial value of that element.
For example for this array $$$a =$$$ $$$[1, 4, 2, 0]$$$ for the first element we will have the vertices with their values $$$[4, 3, 2, 1, 0]$$$ where the costs of the edges entering each vertex will be $$$[3, 2, 1, 0, 1]$$$.
After that you just connect all the vertices that are less than or equal to $$$K$$$ units apart.
And when we build the graph like that, simply the shortest path in the graph from the source to the sink will be the solution. That can be done with Dijkstra but since $$$a_i$$$ and $$$K$$$ can go up to $$$10^9$$$ definitely will be overkill.
I'm really out of any ideas and probably missing some mathematical theorem or something.
Any hints or approaches to solve it in the memory and time constraints?
Where is this problem from?
Go thru the values of the array left to right. If you encounter $$$|a[i+1]-a[i]|>K$$$ you need to fix it. To do so, either change some values with indices $$$ \leq i$$$ by some amount or change values with indices $$$\geq i+1$$$ by some amount. To see which indices to change by what amount, you can use an array of differences. See which of these two options has a cheaper cost, and do that one. Repeat this as you sweep thru the array. The only problem is updating the array of differences when you update a range of values may be slow (perhaps this can be done fast with BIT). I'm not sure if this greedy approach works, but just an idea.
Updating the array of differences is easy — if you change everything with index $$$\le i$$$, then only one difference will change. However I think this greedy idea is not correct: let's say $$$K = 0$$$ and the array is $$$[0, 0, 1000, 0, 0]$$$. Then your solution will do something like $$$[0, 0, 1000, 0, 0] \to [0, 0, 0, -1000, -1000] \to [0, 0, 0, 0, 0]$$$, using 5000 operations. But it's easy to see that we can fix the array with 1000 operations.
The task is exactly the same as atcoder NarrowRectangles. Slope trick is the answer here.
What is slope trick can you elaborate or share code? I'm really new to that concept.
Could've googled before asking :)
By any chance you know dp solution for this problem?
Here's a direct reduction to NarrowRectangles: You are given $$$N$$$ rectangles, the $$$i$$$-th rectangle covers a horizontal range of $$$[a_i - K, a_i + K]$$$. What is the minimum cost to make all of them connected?
Now you can look at the link in the word "could've". It leads to the editorial of the problem.