nitr0gen's blog

By nitr0gen, history, 6 weeks ago, In English

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.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I solved it by creating two different array for negative and positive elements here is the link of my submission hope it helps .

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 < j

After 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.