Hi, I was trying to solve this problem from CSES problemset and I myself wasn't able to solve it but I checked a few submissions and noticed the following as the simplest approach to solve this problem.
ALGORITHM:
We create a new array $$$D$$$ where $$$D_i=A_i-B_i$$$(the excess or deficit for that particular element) and we create a prefix array $$$\displaystyle P_i=\sum_{j=1}^iD_i$$$ and then sort it. Once sorted we do the usual median trick where we sum up the absolute differences with the median for each element $$$P_i$$$ and report that sum as the answer.
Now I have the following explanation of why this algorithm works.
Once we create prefix array $$$P$$$ from $$$D$$$ difference between any 2 elements $$$P_i-P_{j-1}$$$ gives the total deficit/extra in the subarray $$$D[i \dots j]$$$ and since we want to achieve a state where $$$D_i=0 \ \forall 1 \le i \le N $$$ hence we want $$$P_i-P_j=0$$$ for any i and j. hence we try to bring all $$$P_i$$$'s to a single value using a minimum number of moves and that's a very standard problem where we bring everything to the median.
Can anyone confirm if my inference is correct or not?
Now here I have 3 questions:
1.When we make some non-median $$$P_i$$$ equal to the median by doing $$$\displaystyle|P_i-P_{\frac{N}{2}}|$$$ operations won't the other prefix values change for all $$$j$$$ where $$$i \le j \le N$$$ since all such $$$P_j$$$'s are dependent on $$$P_i$$$, so what makes us ignore that fact?
2.Here we're given that the array is circular so where is this fact coming into play?
3.How will we solve the problem if array had not been circular?
My apologies if I asked something very lame, I'd grateful if anyone can help me with this :)
I'll try to answer your questions. Your solution is correct.
1) Notice what happens when we swap with neighbors $$$i$$$ and $$$i+1$$$. Either $$$A_i$$$ decreases by $$$1$$$ and $$$A_{i + 1}$$$ increases by $$$1$$$, or vice versa, which is equivalent to doing the same operation on $$$D$$$ (since $$$B_i$$$ doesn't change). But if you look at the prefix array $$$P$$$, then either $$$P_i$$$ decreases by $$$1$$$, or $$$P_i$$$ increases by $$$1$$$. Thus, an operation only affects a singular element of the prefix array and moving them to the median will not affect any other prefix values.
2) If the array wasn't circular then your method wouldn't work. The above operation I described only holds when $$$i = 1$$$ to $$$i = N - 1$$$, meaning we can only do the operation on $$$P_1, P_2, \cdots P_{N - 1}$$$. Note that when we exchange with neighbors $$$1$$$ and $$$N$$$, then either $$$P_1, P_2, \cdots, P_{N - 1}$$$ all increase or decrease by $$$1$$$. Suppose we do this operation $$$x$$$ times. Then, our new array $$$P$$$ becomes $$$P_1 - x, P_2 - x , \cdots, P_{N - 1} - x, P_N$$$. What is the cost of this in total? Since we have to bring all $$$P_i$$$ to $$$0$$$ ($$$A_i = B_i$$$ at termination), it is $$$x + \sum_{i = 1} ^ {N - 1} |P_i - x| + P_N = \sum_{i = 1} ^ {N} |P_i - x|$$$ (since $$$P_N = 0$$$ is given). And now we can see why we want the median: the sum I just wrote is minimized when $$$x$$$ is equal to the median of $$$P_1, P_2, \cdots, P_N$$$.
3) The problem isn't very hard if it's not circular. You can note that you never want to do exchanges with $$$i$$$ and $$$i + 1$$$ as well as $$$i + 1$$$ and $$$i$$$ simultaneously, so it's a simple greedy from there.
Let me know if you have any equations. Hope this helped.
Wow! what a wonderful explanation, thanks a lot for this. So here's what I understand is this do correct me if I got it wrong.
1. Since we cannot alter $$$P_N$$$(it'll remain 0 throughout) so we bring everything but $$$P_N$$$ equal to the median, so now $$$P$$$ have $$$N-1$$$ values equal to the $$$\displaystyle P_{\frac{N}{2}}$$$ and one zero($$$P_N$$$). Then we do the swaps among $$$1$$$ and $$$N$$$ and following the points which you highlighted in point 2 we'll be able to get everything to zero. Hence the algorithm is correct.
2.For solving the problem for a non-circular array we can maintain a multiset where we store all the elements which have an excess in it. Now we iterate over all elements which have a deficit then we find the nearest excess element which is present in the multiset(using upper_bounds/lower_bounds) and we transfer the required amount from the nearest excess and we continue to do this until the deficit is not fixed then update the multiset and then move on to the next deficit element.
Again thank you very much for taking out time to answer my queries :)
Yes for 1.
For 2 I'd just loop in increasing order. For the first index if it's an excess then add that excess to the answer and transfer all of that to the second neighbor. If it's deficit then add the absolute value of deficit to the answer and subtract the absolute value of deficit from second neighbor. Then you have the first neighbor solved and can repeat the operation for neighbors 2 and 3, then 3 and 4, etc. until you're done. It runs in $$$O(N)$$$.
Ah.. very neat, I get it completely now, thanks a ton!!
For a linear array A, I believe the answer will simply be the sum of absolute value for each element in A's prefix sum array(given that A is valid).
I don't fully follow your explanation. The way I look at the solution is as follows:
Hopefully this explanation is a useful alternative way of understanding the solution.
Great! this certainly gives a better insight into the problem, your greedy solution for non-circular array is lovely. Thanks!!
Please add the problem title in the blog, so that it will come in google search.
Food division CSES
https://cses.fi/problemset/task/1189/
I guess this comment will be helpful to search