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+2a[n-1-i]-2a[i];
}
s=s+a[n-1-i]-a[i];
ans=max(ans,s);
}
cout<<ans<<“\n”;
}
else
cout<<“-1\n”;
}
return 0;
}