PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Soumyadeep Pal
Tester: Manan Grover
Editorialist: Taranpreet Singh
DIFFICULTY
Easy
PREREQUISITES
Observations
PROBLEM
A sequence A_1, A_2, \dots, A_N of length N is called good if any one of the following hold:
- The sequence is strictly increasing, or
- The sequence is strictly decreasing, or
- There exists an index i\;(1 \lt i \lt N) such that:
- A_j \lt A_{j+1}, for each 1 \le j \lt i
- A_j \gt A_{j+1}, for each i \le j \lt N
Given an array A of length N. Find the lexicographically largest good rearrangement of the array, or determine that it is not possible to obtain a good rearrangement of the given array A.
QUICK EXPLANATION
- If the maximum element appears more than once, it is not possible to obtain a good rearrangement.
- If any value other than maximum appears more than twice, it is not possible to obtain a good sequence.
- Otherwise, if an element appears twice, it must appear once before the maximum element and once after the maximum element.
- If an element appears only once, we can place it either before or after the maximum element. In order to get a lexicographically larger sequence, we place it after the maximum element.
EXPLANATION
The maximum element
Let us focus on the third condition of the good array. We can see that no element before i-th element is \geq A_i and no element after i-th element is \geq A_i. Hence, the i-th element is the maximum element of the array.
Additionally, the maximum value must appear only once, at i-th position, so if the maximum element is appearing more than once in the given array A, we can immediately prove that no good rearrangement exists.
We can prove it the same way in the first condition that the maximum element must only be the last element in the array.
Dividing the sequence into two parts
Let’s say the position of the maximum element is p. The sequence A_{1, p} is strictly increasing, and sequence A_{p, N} is strictly decreasing, where A_{l, r} denote the subarray from l-th element to r-th element of the array A.
Hence, due to strict inequalities, any value v can appear at most once in A_{1,p} and at most once in A_{p, N}. Hence, if any value has more than 2 occurrences, we cannot obtain a good sequence.
Otherwise, for each element v, if there are two occurrences of v, then we can place one occurrence of v in A_{1, p} and one occurrence in A_{p, N}. If v appears exactly once, we can place it either A_{1, p} or A_{p, N}.
Getting the lexicographically largest sequence
For any element v appearing twice, we have no choice, but to place it once in both A_{1, p} and once in A_{p, N}. A_{1, p} would be sorted in ascending order, while A_{p, N} would be sorted in descending order, so the position of v in both sequences would be determined automatically. We cannot influence it.
For an element v appearing only once, we have a choice. We can place it either in A_{1, p} or A_{p, N}.
To obtain a lexicographically larger sequence, it is optimal to place v in A_{p, N}.
Proof
Let’s assume the positions of the rest of the elements are already decided, and only once the occurrence of v is to be inserted, and v is not the maximum element. The maximum element appears at position p.
Let’s say, if inserting v in A_{1, p}, its position would be q. Since A_{1, p} is strictly increasing, we can say that v \lt A_q before insertion. Hence, by inserting v in A_{1, p}, the q-th element changes from A_q to v, which is lexicographically smaller.
For example, consider sequence [2, 4, 5, 4, 2] and we need to insert 3. p = 3 here. If we insert 3 in A_{1, 3}, it would become [2,3,4,5,4,2]. If inserted in A_{p, N}, the sequence becomes [2,4,5,4,3,2]. We obtain lexicographically larger sequence in second case.
Hence, we can first add to sequence all the elements appearing twice in increasing order, then the maximum element, and then all the remaining elements in decreasing order.
If facing an issue with implementation, feel free to refer to my commented solution.
TIME COMPLEXITY
The time complexity is O(N*log(N)) per test case due to sorting.
SOLUTIONS
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n; cin >> n;
map<int, int> m;
int mx = 0;
for (int i = 0; i < n; i++) {
int x; cin >> x;
m[x]++;
mx = max(mx, x);
}
for (auto u : m) {
if (u.first == mx && u.second > 1) {
cout << "-1\n";
return;
} else if (u.first < mx && u.second > 2) {
cout << "-1\n";
return;
}
}
vector<int> ans(n);
int l = 0, r = n - 1;
for (auto u : m) {
if (u.second == 1) {
ans[l++] = u.first;
} else {
ans[r--] = u.first;
ans[l++] = u.first;
}
}
for (int i = 0; i < n; i++) {
cout << ans[i] << ' ';
}
cout << '\n';
}
signed main() {
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t--) solve();
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define asc(i,a,n) for(I i=a;i<n;i++)
#define dsc(i,a,n) for(I i=n-1;i>=a;i--)
#define forw(it,x) for(A it=(x).begin();it!=(x).end();it++)
#define bacw(it,x) for(A it=(x).rbegin();it!=(x).rend();it++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lb(x) lower_bound(x)
#define ub(x) upper_bound(x)
#define fbo(x) find_by_order(x)
#define ook(x) order_of_key(x)
#define all(x) (x).begin(),(x).end()
#define sz(x) (I)((x).size())
#define clr(x) (x).clear()
#define U unsigned
#define I long long int
#define S string
#define C char
#define D long double
#define A auto
#define B bool
#define CM(x) complex<x>
#define V(x) vector<x>
#define P(x,y) pair<x,y>
#define OS(x) set<x>
#define US(x) unordered_set<x>
#define OMS(x) multiset<x>
#define UMS(x) unordered_multiset<x>
#define OM(x,y) map<x,y>
#define UM(x,y) unordered_map<x,y>
#define OMM(x,y) multimap<x,y>
#define UMM(x,y) unordered_multimap<x,y>
#define L(x) list<x>
#define Q(x) queue<x>
#define PBS(x) tree<x,null_type,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define PBM(x,y) tree<x,y,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define pi (D)acos(-1)
#define md 1000000007
#define rnd randGen(rng)
int main(){
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<I> randGen;
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
I t;
cin>>t;
while(t--){
I n;
cin>>n;
I a[n];
I mx=0;
OM(I,I) mpp;
B f=false;
asc(i,0,n){
cin>>a[i];
mx=max(mx,a[i]);
mpp[a[i]]++;
if(mpp[a[i]]>2){
f=true;;
}
}
if(f){
cout<<-1<<"\n";
}else{
if(mpp[mx]==2){
cout<<-1<<"\n";
}else{
V(I) x,y;
forw(it,mpp){
if((*it).se==2){
x.pb((*it).fi);
}
y.pb((*it).fi);
}
sort(all(x));
sort(all(y));
asc(i,0,sz(x)){
cout<<x[i]<<" ";
}
dsc(i,0,sz(y)){
cout<<y[i]<<" ";
}
cout<<"\n";
}
}
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class HILLSEQ{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni();
int[] A = new int[N];
for(int i = 0; i< N; i++)A[i] = ni();
Arrays.sort(A);
for(int i = 2; i< N; i++)if(A[i] == A[i-2]){
//A[i] appears more than twice
pn(-1);
return;
}
if(N > 1 && A[N-1] == A[N-2]){
//Maximum appears more than once
pn(-1);
return;
}
int[] list = new int[N];
int c = 0;
//Adding elements in list, which have two occurrences in increasing order
for(int i = 0; i+1< N; i++)if(A[i] == A[i+1])list[c++] = A[i];
//Adding all distinct elements in decreasing order
for(int i = N-1; i>= 0; i--)if(i+1 == N || A[i] != A[i+1])list[c++] = A[i];
for(int i = 0; i< N; i++)p(list[i]+" ");pn("");
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new HILLSEQ().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 
