### nitr0gen's blog

By nitr0gen, history, 6 weeks ago, Can anyone please explain this problem: https://codeforces.com/contest/1405/problem/B

The tutorial is so bad explained and I don't get it.

Thanks. Comments (3)
 » 6 weeks ago, # | ← Rev. 2 →   I solved it by creating two different array for negative and positive elements here is the link of my submission hope it helps .
 » Since we have to spend minimum amount of coins to make everything 0, lets first focus on the operation which is cost free i.e where i < j. It is evident from the question statement that we can only decrement A[i] but cannot increment it which means A[i] has to be a element which is larger than 0. Now we will look for a A[j] closest to the right hand side of A[i] (A[j] has to be incremented which means it is less than 0). Why closest to the right hand of A[i]? That way we will give next A[i] most possible chance to use a A[j] which is at the rightmost side of the array. Once we have decided A[i] and A[j], A[i] will become A[i] = A[i] — min(abs(A[i]), abs(A[j])) and A[j] will become A[j] = A[j] — min(abs(A[i]), abs(A[j])). (We are making the smaller one of A[i] and A[j] equal to zero)If A[i] becomes 0 and A[j] is still not 0, find the next possible A[i] and the most appropriate A[j] for it. You can use the same leftover A[j] if i < j is satisfied. Do this till there no possible A[j] for A[i] which satisfied i < jAfter doing this you have used all the possible free operations.Now just add the remaining values which are not 0 in the array, because making them 0 will cost 1 coin, it doesn't matter which A[j] we use for which A[i]. Sum of this array will be your answer.
•  » » Thank you