No editorial has been added yet and I’m really eager to know how to solve it. I looked up on youtube and some solutions were posted during the contest itself. I was not interested in participating in yesterday’s contest but this question caught my interest.
Take these two examples
First:
1 2 3 15
In this question the answer is 2. Now the how part is if you look carefully if we take sub array 1 to n-1, we see it is taking less steps to make 1 to 2 and 3 to 2 rather taking any other subarray and increasing or decreasing.
Second:
1 15 16 17
Same goes here. Taking 1 to n subarray and making 15 to 16 and 17 to 16. It takes less steps.
So the conclusion is if in the array after sorting the first and last element are pretty huge then we handle that cases by running those two loops.
Hope I was clear.
Thanks.
These two loops are calculating the cost of making all elements equal of subarray (0,n-1) & (1,n).
The first observation for solving is to know that maximum and minimum element would always be present in different arrays for optimal partitioning.