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?
