Hi everyone,
I am stuck at this problem 'Food Division' from 'CSES Problem Set' for about 2 weeks. I have tried below things but still, I can't come up with the correct solution:
I used the approach in solving the 'BALIFE — Load Balancing' problem from SPOJ. Basically, I iterated over the circle, used the current node as the starting point, and then applied the algorithm used in the BALIFE problem.
Also, I wrote minimum cost maximum flow tester to stress test the above approach on random tests. The above approach is giving correct answers on random tests with input size upto 1000. So, I am unable to debug my above approach with smaller test cases.
I have also tried basic greedy strategies like saturating the highest/lowest sources/sinks first.
As a result, I am requesting your help. Any hint/similar problems with editorials would be very helpful.
Auto comment: topic has been updated by code_struck (previous revision, new revision, compare).
Auto comment: topic has been updated by code_struck (previous revision, new revision, compare).
I honestly can't understand why my own code works now (oops), and I'm not sure if you'd rather have hint than full sol, but here is my code if it's any help to you. If I understand later I'll explain.
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: 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).
Here is my code