Contest 4 - Inequality reduction

CodeChef-DSA-learners
1

I’ve been frying my head over it for two days and I can’t seem to wrap my head around the solution.
I’ve read the editorial but couldn’t understand all the Math.
I read about flow decomposition, Max flow min cut and I think i have a basic layman’s understanding of these (without all the proofs involved) but couldn’t move forward with this problem.
Can anyone, please, explain the basic idea behind solution in english with few sample inputs ? It will be great if anyone explains it using binary search.

I tried running a successful submission with different inputs but cannot understand the output.
For example - I ran it with input -
4 1
5 7 9 10
Answer is 7. How ? shouldn’t it be 8 ? Can’t all the other three elements can give one coin to 5 for total of 8 ?

Thank you.

3

Thanks a lot. This helped in clearing a lot of things.
But, I think, I still have not understood the fundamental part. Why the answer is the minimum of all averages? when clearly 8 is possible (one coin transfer by each friend to minimum friend).
How B can be zero? Doesn’t minimum cut requires division of graph in two NON-EMPTY sets?

Thank you.