I was trying to solve the CSES problem Food Division.
I had a rough idea as below:
Calculate the difference between the food a child has and the food the child wants so I have a difference array
I have no idea how to distribute the food with minimum steps. However, I can know if a certain range has too much food or I need to get food from outside the range. Thus, I calculate a prefix sum array from the difference array.
In the end, I try to find a way to minimize the ‘movement’ of each range (the prefix sum) and it is the median value of all prefix sum.
Though the solution works but I’m not sure if it’s just coincident.
It will be appreciated if anyone can guide how to tackle the problem and prove the correctness.
Thank you.
Hey ! I just solved this problem and googled editorials to see if any different solution from mine existed
Anyway, it might be a bit late to help you but I hope it will help others
I’ll try to provide a small intuitive proof of the solution.
First, we might find interesting to compute for each guy how much food he will pass to his left neighbor. Let’s see how we can do this:
Assume the array is NOT cyclic. Then we know for each element how much he needs to add to it’s own food (this quantity can be negative, if it’s negative it just means the child needs more food), let’s call this quantity delta.
Now let’s call flow[i] the quantity of food that the i-th child needs to give to it’s left neighbor. flow[i] will be flow[i - 1] + delta[i - 1]. Indeed, there is only one way to give food to the left children so you definitely need to afford flow[i - 1]. Also you need to afford the food that the left neighbor needs (delta[i - 1]).
The answer to the problem (again WITHOUT cycle) is the sum of absolute values of flows. This is true by definition of the flow array.
Now let’s consider again the array being cyclic (and let’s keep delta/flow array the same as I described earlier). Let’s fix the flow between the first and last children to be 0 (notice this is equivalent to solve the problem without cycle).
Now imagine that the flow between first/last children increases by 1. What will happen ? All the flows will be increased by one ! (this can be proved by induction but it’s also really intuitive, if you say you already give 1 unit of food to the first child, then he needs to take one less unit (or give one more unit) meaning that the flow the second child gives will increase…)
More generally increasing flow between first and last children by X will increase all the other flows by X.
Notice that increasing by X is equivalent to substract -X.
So the answer of the problem is
| X | + | flow[1] + X | + …| flow[n - 1] + X | = | -X | + | flow[1] - (-X) | + …| flow[n - 1] - (-X) |
We now need to find -X such that this sum is minimum.
The best value for -X is the median of the flow array (this is another cses problem: CSES - Stick Lengths which is much easier)
Intuitive way of seeing this is to imagine that -X is a point in the numbers line. Now imagine that values of your flow array are points too. flow[i] - (-X) is the distance between the two points. It becomes way easier to see why the median of all points gives smallest sum of distances (prove is easy by exchange arguments).
