PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: fellas
Preparer: notsoloud
Tester: yash_daga
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
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];
vector <int> adj[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 readString(int l,int r,char endd){
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){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,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()
{
int n=readInt(2,100000,'\n');
sumN += n;
int a[n];
unordered_set<int> s;
for(int i=0;i<n-1;i++){
a[i]=readInt(1,1000000000,' ');
s.insert(a[i]);
}
a[n-1]=readInt(1,1000000000,'\n');
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[0]);
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);
int T=readInt(1,200,'\n');
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;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
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[0]==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[0]=a[n-1];
a1[n-1]=a[0];
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[0] == a[-1] or n == 2: print(-1)
else:
cand1 = [a[-1]] + a[:n-1]
cand2 = a[1:] + [a[0]]
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)