PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: wuhudsm
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
1973
PREREQUISITES:
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);
}
}
string readOne() {
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);
string res = readOne();
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);
int res = stoi(readOne());
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);
long long res = stoll(readOne());
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++) {
res[i] = readInt(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
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++) {
res[i] = readLong(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
int main() {
input_checker in;
int tt = in.readInt(1, 1e5);
in.readEoln();
int sn = 0;
while (tt--) {
int n = in.readInt(3, 3e5);
in.readEoln();
sn += n;
auto a = in.readInts(n, 1, 1e9);
in.readEoln();
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);
in.readEof();
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)