### PROBLEM LINK:

**Author:** Hasan Jaddouh

**Tester:** Teja Vardhan Reddy

**Editorialist:** Hussain Kara Fallah

### DIFFICULTY:

Easy-Medium

### PREREQUISITES:

Greedy,sorting

### PROBLEM:

Given an array A of N integers A_1,A_2,...,A_N. An array is called beautiful if it has a chain of K consecutive identical elements (K is given).

In one operation you can swap 2 adjacent elements. What’s the minimum number of operations to make this array beautiful.

K \leq N \leq 300000

Numbers are less than or equal to 300000.

### Explanation:

It’s obvious that we should solve this problem for each different number separately.

Let’s maintain a sorted list of each different number’s occurrences, and calculate minimum number of operations we need to gather K of them consequently.

First of all, let’s suppose the current number has X occurrences. If X < K then we can do nothing.

For each consecutive K entries in this occurrences list, let’s find the cost to gather them, and pick the best option among the X-K+1 possible windows (segments of K consecutive entries).

It’s always better to gather consecutive ones. (Think why it’s better than if they were discrete, it’s easy).

So now, we have K elements positioned at different places in our array. How should we gather them?

It’s always better to gather them around the middle element (the middle one among these K). We will prove this one.

Assume that we have different items positioned at integral points on an axis line, and we need to gather them at one point. It’s clearly our problem but reformulated.

Let’s assume we decided to gather them at the point X with A items to its left and B items to its right (A>B). Assume that the cost of doing this is C. You can notice that if we move the destination point to X-1 our cost will change by B-A<0, so it’s a better solution.

Also, if B>A we should move it to the right in the same logic. So the target point must have the same number of elements to its left and to its right. Otherwise, we can decrease our total cost by moving it in direction with more elements than the other.

Let’s get back.

For each consecutive K entries in this occurrences list, let’s find the cost to gather them in the middle entry (the middle one of K entries, not the whole list).

In my implementation, each time I process a number’s occurrences list L. I create a prefix sum array such that sum_i contains the sum of positions of first i entries in the list.

Each time I maintain a window (l=i \,, r=i+K-1 \,, mid = \frac{l+r}{2}). I calculate the cost of gathering the elements (L_l,L_{l+1},...,L_{r}) at L_{mid} through my prefix sum array.

You can find the details of my calculations inside the implementation. It’s easy to come up with it though.

It’s recommended to check the Editorialist solution for a better understanding of this implementation.

Complexity: O(N)