# CONCUSSIVE - Editorial

Author: wuhudsm
Tester: tabr
Editorialist: iceknight1093

1973

None

# PROBLEM:

You’re given an array A. Find a rearrangement of it that satisfies

• For each 1 \lt i \lt N, either (A_{i-1} \gt A_i \lt A_{i+1}) or (A_{i-1} \lt A_i \gt A_{i+1})

# EXPLANATION:

A preliminary observation is that we aren’t allowed to have adjacent equal elements.
In particular, this means that if some element occurs \gt \left \lceil \frac{N}{2} \right\rceil times, then no solution exists.

Why?

Suppose x occurs \gt \left \lceil \frac{N}{2} \right\rceil times. Then, two occurrences of x will always be adjacent to each other.

Intuitively, this can be seen if you just attempt to construct a sequence.
Suppose we set the first element to x.
Then, the second can’t be x, so the best we can do is set the third to x.
Continuing this way, x is placed at positions 1, 3, 5, \ldots, 2k+1
However, there are only \left \lceil \frac{N}{2} \right\rceil odd positions we can use, so there’s at least one unplaced instance of x with nowhere to place it.

This idea can be formalized into a proof by induction on N:

• For N = 2 and N = 3, the claim is easily seen to be true.
• For N \gt 3, look at the first two positions. At most one of them can contain x, so the remaining N-2 positions should contain all other instances of x.
However, this would require those positions to have \gt \left \lceil \frac{N-2}{2} \right\rceil non-adjacent instances of x, which by the inductive hypothesis is impossible.

Now, we need to deal with the case when all the elements occur \leq \left \lceil \frac{N}{2} \right\rceil times.
For convenience, let M = \left \lceil \frac{N}{2} \right\rceil.

Let’s consider two separate cases.

Case 1: some element occurs M times

Let x be the element occurring M times.
There are two sub-cases here: when N is odd, and when it’s even.

When N is odd, the positions of x are fixed: we must have A_1 = A_3 = A_5 = \ldots = A_N = x, there is no other way to keep them non-adjacent.
Now:

• If all the remaining even elements are \lt x, or all of them are \gt x, placing them in the even positions in any order gives us a valid solution.
• If some element is \lt x and some other element is \gt x, no valid solution exists.
This is because some occurrence of x must be adjacent to an element that’s less than it, and an element that’s greater than it — and then this x won’t satisfy the necessary condition.

When N is even, we have slightly more freedom over where to place the x's.
In particular, we can separate one pair of x's by two spaces if we want to, instead of just one.
This allows for a solution to always exist, via the following construction:

• Let L be the list of elements that are \lt x, and G be the list of elements that are \gt x.
• Let B be the answer sequence, initially empty.
• For each y \in L, append [x, y] to B.
• Then, for each y \in G, append [y, x] to B.

For example, suppose A = [1, 2, 3, 3, 3, 3, 4, 4].
Then, we’d have x = 3, L = [1, 2] , and G = [4, 4].
B would be constructed as follows:

• After y = 1, B = [3, 1]
• After y = 2, B = [3, 1, 3, 2]
• After y = 4, B = [3, 1, 3, 2, 4, 3]
• After y = 4, B = [3, 1, 3, 2, 4, 3, 4, 3]

It’s not hard to see that this construction always works:

• Each instance of x is adjacent to either two elements of L, or two elements of G.
• All but one element of L is adjacent to two x's
• All but one element of G is adjacent to two x's
• One element of L and one element of G are adjacent to each other, and both are also adjacent to an x, hence satisfying the required property.
Case 2: every element occurs < M times

This case has a rather simple solution.
Sort the array A, so that A_i \leq A_{i+1} for each i.

Let B be the answer array. We fill the odd positions of B first, and then the even positions; going in increasing order of elements of A.
That is, if we have A = [A_1, A_2, A_3, A_4, A_5], we form B = [A_1, A_4, A_2, A_5, A_3].

It’s not hard to see that for the array B constructed this way:

• All elements at odd indices are strictly less than both their neighbors.
• All elements at even indices are strictly greater than both their neighbors.

And we’re done.

Despite the problem looking rather caseworky, it’s possible to implement this without much casework at all.
It can be proved that if an answer exists, then one of the two following arrays will be valid:

• Place the sorted elements of A in odd positions first, then even positions (the same construction we used for case 2 above); or
• Place the sorted elements of A in even positions first, then odd positions.

At least one of these two arrays will coincide with the solutions we constructed for each case.
So, simply create both arrays and check if either of them work; otherwise no solution exists.
(See the tester’s code below for an implementation of this)

# TIME COMPLEXITY

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

# CODE:

Author's code (C++)
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n,mx,key;
int a[N];
map<int,int> cnt;

int main()
{
//freopen("test.in","r",stdin);

scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
mx=0;
cnt.clear();
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
{
cnt[a[i]]++;
if(cnt[a[i]]>mx) mx=cnt[a[i]],key=a[i];
}
if(n&1)
{
if(mx>(n+1)/2) printf("-1\n");
else if(mx==(n+1)/2)
{
if(key==a[1])
{
for(int i=1;i<=n/2;i++) printf("%d %d ",a[i],a[i+(n+1)/2]);
printf("%d\n",a[1]);
}
else if(key==a[n])
{
for(int i=1;i<=n/2;i++) printf("%d %d ",a[i+(n+1)/2],a[i]);
printf("%d\n",a[n]);
}
else printf("-1\n");
}
else
{
for(int i=1;i<=n/2;i++) printf("%d %d ",a[i],a[i+(n+1)/2]);
printf("%d\n",a[(n+1)/2]);
}
}
else
{
if(mx>n/2) printf("-1\n");
else
{
for(int i=1;i<=n/2;i++) printf("%d %d ",a[i+n/2],a[i]);
printf("\n");
}
}
}

//fclose(stdin);
return 0;
}

Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;

struct input_checker {
string buffer;
int pos;

const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";

input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}

assert(pos < (int) buffer.size());
string res;
while (pos < (int) buffer.size() && buffer[pos] != ' ' && buffer[pos] != '\n') {
res += buffer[pos];
pos++;
}
return res;
}

string readString(int min_len, int max_len, const string& pattern = "") {
assert(min_len <= max_len);
assert(min_len <= (int) res.size());
assert((int) res.size() <= max_len);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}

int readInt(int min_val, int max_val) {
assert(min_val <= max_val);
assert(min_val <= res);
assert(res <= max_val);
return res;
}

long long readLong(long long min_val, long long max_val) {
assert(min_val <= max_val);
assert(min_val <= res);
assert(res <= max_val);
return res;
}

vector<int> readInts(int size, int min_val, int max_val) {
assert(min_val <= max_val);
vector<int> res(size);
for (int i = 0; i < size; i++) {
if (i != size - 1) {
}
}
return res;
}

vector<long long> readLongs(int size, long long min_val, long long max_val) {
assert(min_val <= max_val);
vector<long long> res(size);
for (int i = 0; i < size; i++) {
if (i != size - 1) {
}
}
return res;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}

assert((int) buffer.size() == pos);
}
};

int main() {
input_checker in;
int sn = 0;
while (tt--) {
sn += n;
auto a = in.readInts(n, 1, 1e9);
sort(a.begin(), a.end());
auto Check = [&](vector<int> d) -> bool {
for (int i = 1; i < n - 1; i++) {
if (d[i - 1] > d[i] && d[i] < d[i + 1]) {
} else if (d[i - 1] < d[i] && d[i] > d[i + 1]) {
} else {
return false;
}
}
return true;
};
vector<int> b(n), c(n);
{
int j = 0;
for (int i = 0; i < n; i += 2) {
b[i] = a[j];
j++;
}
for (int i = 1; i < n; i += 2) {
b[i] = a[j];
j++;
}
}
{
int j = 0;
for (int i = 1; i < n; i += 2) {
c[i] = a[j];
j++;
}
for (int i = 0; i < n; i += 2) {
c[i] = a[j];
j++;
}
}
if (Check(b)) {
for (int i = 0; i < n; i++) {
cout << b[i] << " ";
}
cout << '\n';
} else if (Check(c)) {
for (int i = 0; i < n; i++) {
cout << c[i] << " ";
}
cout << '\n';
} else {
cout << -1 << '\n';
}
}
assert(sn <= 3e5);
return 0;
}

Editorialist's code (Python)
from collections import Counter
for _ in range(int(input())):
n = int(input())
a = sorted(list(map(int, input().split())))
freq = Counter(a)
mxfreq = max(freq.values())
if mxfreq > (n+1)//2: print(-1)
elif n%2 == 1 and mxfreq == (n+1)//2 and freq[a[0]] < mxfreq and freq[a[-1]] < mxfreq: print(-1)
elif mxfreq < (n+1)//2:
ans = [0]*n
ans[::2] = a[:(n+1)//2]
ans[1::2] = a[(n+1)//2:]
print(*ans)
elif n%2 == 1:
for i in range(n):
if freq[a[i]] == mxfreq:
a = [a[i]]*mxfreq + a[:i] + a[i+mxfreq:]
break
ans = [0]*n
ans[::2] = a[:(n+1)//2]
ans[1::2] = a[(n+1)//2:]
print(*ans)
else:
x = -1
for i in range(n):
if freq[a[i]] == mxfreq:
x = a[i]
break
ans = [0]*n
ans[::2] = [x]*mxfreq
ptr, flag = 1, 0
for i in range(n):
if a[i] == x: continue
if a[i] < x:
ans[ptr] = a[i]
ptr += 2
else:
ans[ptr-1] = a[i]
ans[ptr] = x
ptr += 2
print(*ans)


1
4
1 1 2 2
my output:
1 2 1 2

why it didn’t passed!!!

yeah same, my code gave
1
4
1 1 2 2
output:
1 2 1 2

but it didnt pass

It’s not hard to see that for the array B constructed this way.can u prove this formly ?

how can this solution pass all test cases??

for the input:
1
3
1 2 2

it gives -1 (but should give 2 1 2)

but, it has given correct answer… please look into it, and re-evaluate the problem.

1 Like

yup this contest was shit.

1 Like

How come this solution doesn’t get ac? It’s the same as what the editorial says.

https://www.codechef.com/viewsolution/1020451789

For test case 1 1 3 3 3 its a weak testcase
It should come 3 1 3 1 3 but output shows -1 and passed all the testcases . I request to add more testcases for the problem
Here is my solution
https://www.codechef.com/viewsolution/1020850054

Somebody tell me why my solution doesn’t work even though it was exactly according to the editorial and passes all the testcases I input even the tricky ones also like 1 1 2 and 1 2 2 : CodeChef: Practical coding for everyone

can someone help me find error in my code.I’ve used correct logic though.

for _ in range(int(input())):
n=int(input())
arr=list(map(int,input().split()))
arr.sort()
def check(arr):
j=0
for i in range(1,len(arr)-1):
if arr[i-1]<arr[i]>arr[i+1]:
j+=1
elif arr[i-1]>arr[i]<arr[i+1]:
j-=1
else:
return False
if j<-1 or j>1:
return False
return True

if n%2==1:
#upar niche
index=(n//2)+1
newarr=[None for _ in range(n)]
j=0
for i in range(index):
newarr[j]=arr[i]
j+=2
j=1
for i in range(index,n):
newarr[j]=arr[i]
j+=2

#niche upar
newarr2=[None for _ in range(n)]
index=n//2
j=0
for i in range(index,n):
newarr2[j]=arr[i]
j+=2
j=1
for i in range(index):
newarr2[j]=arr[i]
j+=2

#check
if check(newarr):
print(*newarr)
elif check(newarr2):
print(*newarr2)
else:
print(-1)

else:
newarr=[None for _ in range(n)]
newarr2=[None for _ in range(n)]
index=n//2
j=0
for i in range(index):
newarr[j]=arr[i]
j+=2
j=1
for i in range(index,n):
newarr[j]=arr[i]
j+=2
j=0
for i in range(index,n):
newarr2[j]=arr[i]
j+=2
j=1
for i in range(index):
newarr2[j]=arr[i]
j+=2
print(newarr)
print(newarr2)
#check
if check(newarr):
print(*newarr)
elif check(newarr2):
print(*newarr2)
else:
print(-1)