Need Help with CSES Problem

Revision en1, by Makise_Kurisu, 2021-06-29 23:57:58

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Makise_Kurisu 2021-06-29 23:57:58 1770 Initial revision (published)