Circular Subarrays

You are given a circular array of size N and an integer K. On this array you can perform operations of incrementing or decrementing an element. The cost of such an operation is 1. You can perform more than one operation on a single element.

You want each subarray of length K to have the same sum of elements. Compute the minimum cost needed to achieve this.

Standard input

The first line contains two integer values N and K.

The second line contains N integers, the values of the array.

Standard output

The output should contain a single integer value representing the minimum cost needed.

Constraints and notes

• 1 ≤ N ≤ 100 000
• 1 ≤ K ≤ N
• The values of the array are between -10 000 and 10 000
• The array is circular, so there are always exactly N subarrays of lengthK.

Task Limits

• Time limit: 400 ms
• Memory limit: 128 MB

Input	Output
10 1 1 2 3 4 5 6 7 8 9 10	25
10 2 1 6 2 7 3 8 4 9 5 10	12
9 3 1 4 7 2 5 8 3 6 9	6
10 10 1 2 3 4 5 6 7 8 9 10	0

------------------------------------------------editorial----------------------------------------------------

after some observation i find that for making  each k segment array with  equal sum, we need to do operation like 

if  input is like  9 3

than 

we have to make valuse at index

till m-1 do this 

 0=0+(3-1)=0+(3-1)+(3-1)

1=1+(3-1)=1+(3-1)+(3-1)

2=2+(3-1)=2+(3-1)+(3-1)

and making equal we need to set all element at its median value (this is the least costly to make all element equal )

above approach will work if n%m==0 or array will be not circular else this approach will give wa

like for 10,4 this approach will fail , 

soo  for general case we have to use dsu to group all elements which need to make equal in a single group ,
---------------------------------------------------or-----------------------------------------------------------

A first observation we can make is that it is sufficient to ensure that every two consecutive subarrays of size K have equal sum. Lets suppose we look at the two subarrays that start on positions i and i+1. If they are equal it follows that elements v[i] and v[i+K] need to be equal too. We get N equality constraints between the elements of the array. We can group the elements such that all the values in a group need to be equal. It can be proven that there will always be gcd(N, K) groups of size N / gcd(N, K), but this information is not relevant for solving the problem.

Each group can be solved independently. Basically, the subproblem we need to solve now is to make all the elements of a set equal, minimising the total cost. This is a classical problem and the answer is to make all the elements equal to the median of the set. A proof can be found

---------------------------------for clearity see code-----------------------------------------------------------

#include<iostream>

#include<stdio.h>

#include<vector>

#include<algorithm>

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

int rankwa[1000000];

int parent[1000000];

lli arr[1000000];

vector<lli> v[1000000];

lli solve(vector<lli> vv,int mid)

 {

  vector<lli> v;

  int size=vv.size();

  for(int i=0;i<size;i++)

   {

    // storing values from index 

  v.push_back(arr[vv[i]]);

  }

 //  cout<<endl;

  sort(v.begin(),v.end());

  lli ret=0;

  //  cost to make all elements equal to median

  for(int i=0;i<size;i++)

   {

    ret+=abs(v[mid]-v[i]);

  }

  return ret;

 }

lli find(lli a)

  {

    if(parent[a]!=parent[parent[a]])

     {

      parent[a]=find(parent[a]);

     }

     return parent[a];

 }

int merge(int a, int  b)

{

  int x=find(a);

  int y=find(b);

  if(rankwa[x]>rankwa[y])

  {

      parent[y]=x;

      //parent[y]=-1;

   

  }

  else

  {

      parent[x]=y;

      

   if(rankwa[x]==rankwa[y])

   rankwa[y]++;

  }

}

int main()

{

 int n,m;

cin>>n>>m;

int mn=n;

for(int i=0;i<n;i++)

cin>>arr[i];

for(int i=0;i<=m-1;i++)// making array circular  by copying firmst m elements 

 { 

  arr[n+i]=arr[i];

 }

 

for(int i=0;i<=3*n;i++)

 {

  parent[i]=i;

  rankwa[i]=1;

 }

 n=n+m;

 

 

 

for(int j=0;j<m;j++)

 {

for(int i=j;i<n;i+=m)

 {

   int id=i;

id=id%mn;// sinse extra elements are from index 0to m

     if(find(id)!=find(j))

      {

      merge(id,j);

}

 }

    }

    lli ans=0;

    for(int i=0;i<n;i++)

     {

      v[find(i)].push_back(i); 

//storing  indexs accorting to its particular group

}

 

 

for(int i=0;i<m;i++)

 {

        if(v[i].size()!=0)

        {

        // for each group finding ans to make elements of thst group equal

         if(v[i].size()%2==1  )// if size of group odd than only 1 median element

           {

          ans+=solve(v[i],v[i].size()/2);

             }

     // 2 medians         

    else

     ans+=min(solve(v[i],v[i].size()/2),solve(v[i],v[i].size()/2-1));

 }

}

     cout<<ans<<endl;

 return 0;

}