# PROBLEM LINK:

Author: Sakchi Agarwal

Tester: Abhishek Chaudhary

Editorialist: Sakchi Agarwal

# DIFFICULTY:

MEDIUM

# PREREQUISITES:

NONE

# PROBLEM:

Given an array, arrange it in such a way that there are exactly K changes (a change means increasing to decreasing or decreasing to increasing order) such that the sum of absolute difference between adjacent elements is maximized and K is given to be even in all test cases.

# EXPLANATION:

If number of elements N is less than (K+2), then it is not possible to make an array with K changes. In this case, answer is -1.

If N is greater than or equal to (K+2), then we put K/2+1 smallest elements in array named small and K/2+1 largest elements in array named large. We arrange elements alternatively by placing one element from small then one element from large and so on. Also, The remaining N-2*(K/2+1) elements will get cancelled while calculating the sum so we are not considering them.

After arranging the elements, we check if we are getting K possible changes or not.

If not, then we print -1.

If yes, we calculate the sum and print the answer.

# SOLUTIONS:

## Setter's Solution

```
#include<bits/stdc++.h>
```

using namespace std;

#define ll long long int

void rev(ll k, ll small[])

{

ll i;

for(i=1;i<=k/4;i++)

{

ll t=small[i];

small[i]=small[k/2-i+1];

small[k/2-i+1]=t;

}

}

int main()

{

ll t;

cin>>t;

while(t–)

{

ll n,k;

cin>>n>>k;

ll a[n];

ll i;

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

cin>>a[i];

sort(a,a+n);

ll s=0;

ll ans=0;

if(k==0)

cout<<a[n-1]-a[0]<<"\n";

else if(k+2<=n)

{

ll small[k]={0};

ll large[k]={0};

ll c=0;

for(i=1;i<=k/2;i++)

small[i]=a[c++];

small[0]=a[c++];

c=n-1;

for(i=0;i<=k/2;i++)

{

large[i]=a[c–];

}

if(small[0]==large[0])

ans=-1;

else if(small[k/2]==large[k/2])

{

rev(k,small);

}

ll temp=k/2;

while(temp>=1)

{

if(small[temp]==large[temp] || small[temp]==large[temp-1])

{

ans=-1;

break;

}

temp–;

}

if(ans==0)

{

for(i=0;i<(k/2);i++)

{

s=s+2*a[n-1-i]-2*a[i];

}

s=s+a[n-1-i]-a[i];

ans=max(ans,s);

}

cout<<ans<<"\n";

}

else

cout<<"-1\n";

}

return 0;

}