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.

# | User | Rating |
---|---|---|

1 | tourist | 3619 |

2 | Um_nik | 3493 |

3 | ecnerwala | 3446 |

4 | Radewoosh | 3383 |

5 | ksun48 | 3357 |

6 | yosupo | 3324 |

7 | Benq | 3299 |

8 | maroonrk | 3243 |

9 | apiadu | 3238 |

10 | Petr | 3217 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 207 |

2 | Monogon | 196 |

3 | SecondThread | 195 |

4 | vovuh | 188 |

5 | pikmike | 186 |

5 | Um_nik | 186 |

7 | antontrygubO_o | 185 |

8 | Ashishgup | 182 |

9 | pashka | 169 |

10 | Radewoosh | 167 |

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.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/30/2020 22:40:15 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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 sideof 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 therightmostside 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.

Thank you