Perfect !
https://www.codechef.com/viewsolution/72171766
Can someone please tell how this approach is wrong or different from the greedy one given in the editorial.
I finally have some intuition behind the reverse traversal.
Consider elements: [i, i + 1, i + 2]
We try to decrease the right elements to 0 or 1 and decrease the left element accordingly. So, from front traversal approach, decrease (i + 1) to 1 or 0, and decrease i accordingly. But now when we decrease (i + 2) to 1 or 0, (i + 1) being already 0(worst case) will only increase its absolute value. So, (i + 1) is affected 2 times.
Now consider reverse traversal, we decrease (i + 2) to 0 or 1 and (i + 1) accordingly. Now when we try to decrease (i + 1) again we know that we will not decrease it beyond 0. So in worst case(0), it isn’t affected second time and hence the absolute value stays minimum.
2 Likes