 # MINDIF - Editorial

Author: fellas
Preparer: notsoloud
Tester: yash_daga
Editorialist: iceknight1093

TBD

Sorting

# PROBLEM:

Given an array A, find any rearrangement D of it such that:

• D is not sorted, in either ascending or descending order
• \min(|D_i - D_{i+1}|) (1 \leq i \lt N) is minimum across all valid D

# EXPLANATION:

Let’s get a couple of edge cases out of the way first:

• If N = 2, the answer is obviously -1 since any rearrangement is sorted in ascending or descending order.
• Similarly, if A contains only a single distinct element, there’s only one ordering (which is trivially sorted), so the answer is -1.

Let’s now solve the remaining cases, i.e, N \geq 3 and A contains at least two distinct elements.
First, note that \min(|D_i - D_{i+1}|) is minimized when D is a sorted array, since that’s what keeps adjacent elements as close to each other as possible.

In particular, let’s sort the array A and find an index p such that A_{p+1} - A_p is minimum.
Ideally, if we are able to find a non-sorted rearrangement such that these two elements stay adjacent, we’ll be done.

There are several ways to do this.
One of them is follows:

• Consider the two arrays [A_N, A_1, A_2, \ldots, A_{N-1}] and [A_2, A_3, \ldots, A_N, A_1]
Note that this is constructed based on the sorted array A, i.e, A_1 \leq A_2 \leq \ldots \leq A_N
• At least one of these two arrays will definitely be a valid answer, so find the minimum adjacent difference for both, and print the one with the lower value.
Note that one of these two might end up being sorted (in descending order), so make sure to check for that as well so that you don’t print a sorted array.
Why does this work?

Let
X = [A_N, A_1, A_2, \ldots, A_{N-1}]
Y = [A_2, A_3, \ldots, A_N, A_1]

Since A contains at least two distinct elements, neither X nor Y are sorted in ascending order.

Now, suppose X is sorted in descending order.
This tells us that A_N \geq A_{1} \geq A_2 \ldots \geq A_{N-1}.
Note that we already know that A_1 \leq \ldots \leq A_N and A contains at least two distinct elements.
Together, this tells us that A_1 = A_2 = \ldots = A_{N-1} \lt A_N.

It’s not hard to see that this makes the array Y unsorted and (when N \geq 4) have two adjacent equal elements (its first two elements) which is the best-case scenario.

Similar analysis applies to when Y is sorted in descending order, when you’ll have A_1 as the unique minimum and all the other elements equal.

If neither X nor Y are sorted, then it’s not hard to see that at least one of them preserves the minimum adjacent difference, since the pair (p, p+1) we found in A can only be ‘broken’ if:

• p = 1, in which case it remains intact in X
• p+1 = N, in which case it remains intact in Y

# TIME COMPLEXITY

\mathcal{O}(N\log N) per testcase.

# CODE:

Preparer's code (C++)
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <utility>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <math.h>
#include <ctime>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <cassert>
#define int long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;

const int N=500023;
bool vis[N];
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}

if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}

return x;
} else {
assert(false);
}
}
}

string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}

long long readIntSp(long long l,long long r){
}

long long readIntLn(long long l,long long r){
}

}

}

int sumN = 0;
int check(vector<int> &a){
vector<int> b = a;
sort(b.begin(), b.end());
int minm = 1e18;
bool allAscending = true;
bool allDescending = true;
for(int i = 0; i<a.size(); i++){
if(a[i] != b[i]){
allAscending = false;
}
if(a[i] != b[a.size()-1-i]){
allDescending = false;
}
if(i>0){
minm = min(minm, abs(a[i]-a[i-1]));
}
}
if(allAscending || allDescending){
return 1e18;
}
return minm;
}
void solve()
{
sumN += n;
int a[n];
unordered_set<int> s;
for(int i=0;i<n-1;i++){
s.insert(a[i]);
}
s.insert(a[n-1]);
if(s.size()==1 || n==2){
cout<<-1<<'\n';
return;
}
sort(a,a+n);
vector<int> ans1, ans2;

for(int i = 1; i<n; i++){
ans1.push_back(a[i]);
}
ans1.push_back(a);
ans2.push_back(a[n-1]);
for(int i = 0; i<n-1; i++){
ans2.push_back(a[i]);
}

if(check(ans1) < check(ans2)){
for(int i = 0; i<n-1; i++){
cout<<ans1[i]<<" ";
}
cout<<ans1[n-1]<<'\n';
}else{
for(int i = 0; i<n-1; i++){
cout<<ans2[i]<<" ";
}
cout<<ans2[n-1]<<'\n';
}
cerr << check(ans1) <<' '<<check(ans2)<<endl;
}
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
while(T--){
solve();
// cout<<'\n';
}
cerr << sumN << endl;
assert(sumN<=200000);
assert(getchar()==-1);
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
return 0;
}

Tester's code (C++)
//clear adj and visited vector declared globally after each test case
//check for long long overflow
//Mod wale question mein last mein if dalo ie. Ans<0 then ans+=mod;
//Incase of close mle change language to c++17 or c++14
//Check ans for n=1
// #pragma GCC target ("avx2")
// #pragma GCC optimize ("O3")
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);cout.precision(dbl::max_digits10);
#define pb push_back
#define mod 1000000007ll //998244353ll
#define lld long double
#define mii map<int, int>
#define pii pair<int, int>
#define ll long long
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rep(i,x,y) for(int i=x; i<y; i++)
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>
#define setbits(x) __builtin_popcountll(x)
#define print2d(dp,n,m) for(int i=0;i<=n;i++){for(int j=0;j<=m;j++)cout<<dp[i][j]<<" ";cout<<"\n";}
typedef std::numeric_limits< double > dbl;
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
const long long N=200005, INF=2000000000000000000;
const int inf=2e9 + 5;
lld pi=3.1415926535897932;
int lcm(int a, int b)
{
int g=__gcd(a, b);
return a/g*b;
}
int power(int a, int b, int p)
{
if(a==0)
return 0;
int res=1;
a%=p;
while(b>0)
{
if(b&1)
res=(1ll*res*a)%p;
b>>=1;
a=(1ll*a*a)%p;
}
return res;
}

int getRand(int l, int r)
{
uniform_int_distribution<int> uid(l, r);
return uid(rng);
}
int cal(vi a)
{
int n=a.size();
vi b=a;
sort(all(b));
if(b==a)
return 2e9;
reverse(all(b));
if(b==a)
return 2e9;
int mi=2e9;
rep(i,1,n)
mi=min(mi, abs(a[i]-a[i-1]));
return mi;
}
int32_t main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
vi a(n);
rep(i,0,n)
cin>>a[i];
sort(all(a));
if(n==2 || a==a[n-1])
cout<<-1<<"\n";
else
{
vi a1=a, a2=a;
rep(i,0,n-1)
{
a1[i]=a[i+1];
a2[i+1]=a[i];
}
a2=a[n-1];
a1[n-1]=a;
if(cal(a1)>cal(a2))
a1=a2;
for(int i=0;i<n;i++)
cout<<a1[i]<<" ";
cout<<"\n";
}
}
}

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
a.sort()
if a == a[-1] or n == 2: print(-1)
else:
cand1 = [a[-1]] + a[:n-1]
cand2 = a[1:] + [a]

dif1 = min(abs(cand1[i] - cand1[i-1]) for i in range(1, n))
dif2 = min(abs(cand2[i] - cand2[i-1]) for i in range(1, n))

if (cand2 == a[::-1]) or (dif1 < dif2 and cand1 != a[::-1]): print(*cand1)
else: print(*cand2)

1 Like
//g++  7.4.0

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define boost ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define all(a) a.begin(),a.end()
#define f first
#define s second
void solve() {
int n;cin>>n;

vector<int>v;
unordered_map<int,int>mp;
for(int i = 0;i<n;i++){int x;cin>>x;v.push_back(x);}

for(int i:v){++mp[i];}

if((mp[v] == n) || (n == 2)){
cout<<"-1\n";return;
}
sort(all(v));

if(n==3){
int pp = -1;
for(int i = 0;i<n;i++){
if(mp[v[i]]==2){
pp = i;
}
}
if(pp!=-1){
if(v[pp] == v){swap(v,v);}
else if(v[pp] == v){swap(v,v);}}
for(int i:v){cout<<i<<' ';}cout<<'\n';
return ;

}
int mn = INT_MAX;
int ind = -1;
for(int i = 0;i+1<n;i++){
if(mn >= abs(v[i+1]-v[i])){
mn = min(mn,abs(v[i+1]-v[i]));
ind = i;
}
}

if(ind != 0){
cout<<v[ind]<<' '<<v[ind+1]<<' ';
}
for(int i = 0;i<n;i++){
if(i!=ind and i!=(ind+1))
cout<<v[i]<<' ';
}
if(ind == 0){
cout<<v[ind]<<' '<<v[ind+1]<<' ';
}
cout<<'\n';

}
int main()
{boost;
int t;cin>>t;

while(t--)solve();
}


failing TC anyone?

test case : {3 3 3 5} wrong answer

1 Like
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define mod 998244353
#define int long long
#define setpres cout << fixed << setprecision(10)
#define all(x) (x).begin(), (x).end()
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
const int INF = 1e18;

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }

int32_t main() {
fast;
int tt = 1;
cin >> tt;
while(tt--) {
int n;
cin >> n;
vector<int> v(n);
for(int i=0;i<n;i++) {
cin >> v[i];
}
if(n == 2) {
cout << -1 << endl;
continue;
}
sort(all(v));
if(v == v[n - 1]) {
cout << -1 << endl;
continue;
}
int curr = 0;
for(int i=1;i<n;i++) {
curr += v[i] - v[i - 1];
}
int ind = -1;
int ans = INF;
for(int i=1;i<n;i++) {
if(v[i] == v[i - 1]) continue;
int temp = curr;
if(i != 1) {
temp -= v[i - 1] - v[i - 2];
temp += v[i] - v[i - 2];
}
if(i + 1 < n) {
temp -= v[i + 1] - v[i];
temp += v[i + 1] - v[i - 1];
}
if(temp < ans) {
ans = temp;
ind = i;
}
}
dbg(ind);
assert( ind != -1);
swap(v[ind], v[ind - 1]);
for(auto& i : v) {
cout << i << " ";
}
cout << endl;
}
}


Why is this wrong? I’m considering every possible adjacent swap.

consider the example, arr = [1, 4, 6, 10, 30] :

your code gives the output : [ 4, 1, 6, 10, 30] . Sure, this is neither in ascending nor descending order but it doesn’t have the minimum score out of all possible answers.

Why is this happening?

arr - arr = 3 (minimum diff that your code considers),
and arr - arr = 2 (actual minimum diff).

your code works on the 2nd index two times (see your if conditions) and only once on index 1 so it sees the diff as 4, and 3 < 4 so your ind variable stores 1 and not 2 like it should.