Makise_Kurisu's blog

Need Help with CSES Problem
By Makise_Kurisu, history, 3 years ago, In English

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 :)

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :)

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)$$$.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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).

      → Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +3 Vote: I do not like it

I don't fully follow your explanation. The way I look at the solution is as follows:

  • You want to make D[i] = 0 for all i.
  • If the array is not circular, you have to make all D[i] = 0 by giving to/taking from elements on D[i+1]. Number of moves to individually balance i=0,1,2 is |D[0]|,|D[0]+D[1]|,|D[0]+D[1]+D[2]| respectively because I keep shifting extra stuff to/from the next element. Another way to think of this is if D[0...i-1] is balanced, its sum is 0 so sum(D[0...i]) is concentrated in D[i]. Hence, the total number of moves for each i is |p[i]| where p[i] is the prefix sum of D[0]+D[1]+...D[i]. Answer is |p[0]|+|p[1]|+...|p[n]|.
  • Now that the array is circular, you may move an optimal k elements from D[n-1] to D[0]
  • Then, D[0] becomes D[0]+k and each p[i] will become p[i]+k. Answer is now |p[0]+k|+|p[1]+k|+...+|p[n-1]+k|. Reimagining k as k*-1=-k gives ans=|p[0]-k|+|p[1]-k|+...+|p[n-1]-k| which you want to minimize. The optimal k for minimum ans is the median of p[i] because moving k away from the median means moving further from more elements and nearer to less elements causing a net increase in ans.
  • Earlier when I moved k from D[n-1] to D[0], I incurred k moves. This is taken care of because originally p[n-1]=0 (sum of all D[i] is 0 for balance). After moving k from p[n-1] to p[0], p[n-1]=-k, so for the last element, ans would have |p[n-1]|=k added to it instead of 0.

Hopefully this explanation is a useful alternative way of understanding the solution.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Great! this certainly gives a better insight into the problem, your greedy solution for non-circular array is lovely. Thanks!!

    → Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Please add the problem title in the blog, so that it will come in google search.

→ Reply