PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: SHUBHAM KHANDELWAL
Tester: Trung Nguyen
Editorialist: Taranpreet Singh
DIFFICULTY
Medium-Hard
PREREQUISITES
Greedy, Order statistic data structues (or segment tree) and Observations.
PROBLEM
A sequence F of N elements is generated from another sequence A of length N containing only positive integers by the formula F_i = \sum_{j = 1}^j (-1)^{j+1}*A_j. Given a sequence B, can it be reordered to form a valid sequence F such that a valid A corresponding to generated F exists?
Among all such orderings of B, you are required to find the lexicographically smallest ordering of B which satisfies above criteria.
QUICK EXPLANATION
- The validity condition can be written as 0 < F_1 > F_2 < F_3 > F_4 \ldots. So we need to reorder the sequence into a zigzag sequence.
- A valid sequence exist, if at least one element is positive and either of following is true,
- The frequency of most frequent element \leq \lfloor \frac{N}{2} \rfloor
- The most frequent element is the maximum element and frequency of maximum element = \lceil \frac{N}{2} \rceil
- Let’s pick two elements at a time. Assuming prev is the element at previous position (prev = 0 for first position), min = minimum among the remaining elements and nxt = smallest element strictly greater than maximum of prev and min, try to push elements nxt and min in this order into sequence, and check if answer exists.
- If, at any point, we get answer doesn’t exist, it can be because any element having greater than \lfloor N/2 \rfloor frequency, or maximum element having more than \lceil N/2 \rceil frequency after removal of min and nxt.
- In either case, the most frequent element shall be included in two elements. The other element would be either min or nxt depending upon its comparison with nxt
- This solution works because it always tries to place minimum possible element at second position, and element just greater than adjacent two elements.
EXPLANATION
Let’s assume F_0 = 0. Expanding the expression F_i = \sum_{j = 1}^i (-1)^{j+1}*A_j, we can rewrite it as F_i = F_{i-1} + (-1)^{i+1}*A_i. So, for odd i, we have $F_i = F_{i-1} + A_i and for even i, F_i = F_{i-1}-A_i. We also have A_i > 0.
The above inqualities lead to following property of sequence F
0 < F_1 > F_2 < F_3 > F_4 \ldots
Since F_1 > 0, if all elements are \leq 0, it’s impossible to choose F_1, hence answer is impossible.
Let’s ignore F_1 > 0 condition and lexicographically smallest condition. One way to make a zigzag sequence is to place larger \lceil N/2 \rceil into odd positions and \lfloor N/2 \rfloor. Now, the answer is possible if we have F_i \neq F_{i+1} for any position i.
We can be sure to find a permutation of F, if all elements appear at most \lfloor N/2 \rfloor times, or the element is maximum in array and appears exactly \lceil N/2 \rceil times. We can see that if any of above condition is violated, the conflicting element would be the median of array (Be sure to work out some cases before trusting editorial 
)
So, let us add all elements into a data structure which supports following operations
- Add an element
- Remove an element
- Get minimum element
- Get maximum element
- Get median element
- Get most frequent element
- Find frequency of an element
- Determines whether it’s possible to form a zigzag sequence excluding constraint on first element
So, now we have condition for determining whether a set can result in a good sequence or not, excluding the lower limit on first element.
Now, it is tempting to try out greedy of selecting one element, working out even and odd cases, while ensuring the answer remains possible with remaining set of elements. And it may work, but you’d need to handle cases like odd and even indices almost separately and many cases within, which are easy to miss and hard to debug.
In this problem, we need to select a zigzag sequence such that first element is greater than some value (say prev). Let’s select two elements min and nxt such that min is minimum among remaining values and nxt > max(prev, min). We want to check if we can place nxt and min at current and next position. We have prev < nxt > min, and if it’s possible for remaining set to form a valid sequence, it’s best to put these two elements in sequence, since
- b is the smallest possible choice for current position.
- After adding b and a into sequence, min becomes the value of prev for remaining sequence. Since a is minimum among remaining possible, it gives us best possible shot of making lexicographically smallest sequence.
If, at any point there’s no valid nxt, it’s impossible to form a sequence. (It’ll happen only because of prev constraint).
Now, only thing that can go wrong is that, after removing min and nxt from our data structure, our data structure reports impossible, but reports possible before removing min and nxt, it means that removal has caused the frequency of median to exceed \lfloor N/2 \rfloor or median is maximum and its frequency exceed \lceil N/2 \rceil after removal. (N denote number of remaining elements here).
In this case, the median element has to be placed in either of the two current positions. Now, if we have
- nxt > median, we’ll have prev >= median, so we cannot push median immediately. In this case, we need to add nxt and median in this order to answer and remove them from our data structure.
- nxt < median, we can place median in current position and min in next position. So we push median and min and remove them from our data structure.
In the end, we might be left off with one element, which we simply add to sequence if it’s greater than previous element.
In order to implement above mentioned data structure, we may compress B and maintain frequency of each element and answer median queries via tree descent, and most frequent element query by maintaining argmax (Position of maximum frequency) for each node.
Managing above queries is explained here
TIME COMPLEXITY
The time complexity is O(N*log(N)) per test case.
SOLUTIONS
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); --i)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int) 1e9 + 23111992;
const ll LINF = (ll) 1e18 + 23111992;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ull isqrt(ull k) {ull r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int mrand() {return abs((int) mt());}
inline int mrand(int k) {return abs((int) mt()) % k;}
#define db(x) cerr << "[" << #x << ": " << (x) << "] ";
#define endln cerr << "\n";
void chemthan() {
int test; cin >> test;
assert(1 <= test && test <= 1e4);
int sumd = 0;
while (test--) {
int d; cin >> d;
sumd += d;
assert(1 <= d && d <= 1e5);
assert(1 <= sumd && sumd <= 1e6);
vi a(d);
FOR(i, 0, d) cin >> a[i];
auto solve = [&] () {
vi dc;
FOR(i, 0, d) dc.pb(a[i]);
sort(all(dc)), uni(dc);
FOR(i, 0, d) a[i] = lower_bound(all(dc), a[i]) - dc.begin();
vi f(d);
multiset<int> st;
set<pi> fre;
FOR(i, 0, d) {
st.insert(a[i]);
f[a[i]]++;
}
FOR(i, 0, d) {
if (f[i]) {
fre.insert({f[i], i});
}
}
auto rem = [&] (int u) {
st.erase(st.find(u));
fre.erase({f[u], u});
if (--f[u]) {
fre.insert({f[u], u});
}
};
auto add = [&] (int u) {
st.insert(u);
if (f[u]) {
fre.erase({f[u], u});
}
f[u]++;
fre.insert({f[u], u});
};
auto next = [&] () {
if (sz(st) + 1 < fre.rbegin()->fi * 2) {
return INF;
}
if (fre.rbegin()->fi * 2 == sz(st) + 1) {
return fre.rbegin()->se;
}
if (fre.rbegin()->fi * 2 == sz(st) &&
*st.begin() < fre.rbegin()->se &&
fre.rbegin()->se < *st.rbegin()) {
return fre.rbegin()->se;
}
return *st.begin();
};
vi res;
int it = 1;
int last = 0;
while (it++ && sz(st)) {
if (sz(st) == 1) {
res.pb(*st.begin());
break;
}
if (it & 1) {
int u = next();
if (u == INF) {
cout << "NO\n";
return;
}
res.pb(u);
rem(u);
last = dc[u];
}
else {
if (sz(fre) <= 3) {
vi vals;
for (auto e : fre) {
if (last < dc[e.se]) {
vals.pb(e.se);
}
}
sort(all(vals));
int found = 0;
for (int u : vals) {
rem(u);
if (next() < u) {
res.pb(u);
found = 1;
break;
}
else {
add(u);
}
}
if (!found) {
cout << "NO\n";
return;
}
continue;
}
int k = upper_bound(all(dc), last) - dc.begin();
if (k == sz(dc)) {
cout << "NO\n";
return;
}
if (!(sz(st) & 1)) {
if (fre.rbegin()->fi * 2 == sz(st) && fre.rbegin()->se != *st.begin()) {
int u = fre.rbegin()->se;
res.pb(u);
rem(u);
continue;
}
else {
chkmax(k, *st.begin() + 1);
auto it = st.lower_bound(k);
if (it == st.end()) {
cout << "NO\n";
return;
}
res.pb(*it);
rem(*it);
}
}
else {
if (fre.rbegin()->fi * 2 == sz(st) + 1) {
int u = fre.rbegin()->se;
res.pb(u);
rem(u);
}
else if (fre.rbegin()->fi * 2 < sz(st) - 1 ||
fre.rbegin()->se == *st.rbegin()
) {
chkmax(k, *st.begin() + 1);
auto it = st.lower_bound(k);
if (it == st.end()) {
cout << "NO\n";
return;
}
res.pb(*it);
rem(*it);
}
else {
chkmax(k, *st.begin() + 1);
chkmax(k, fre.rbegin()->se);
auto it = st.lower_bound(k);
if (it == st.end()) {
cout << "NO\n";
return;
}
res.pb(*it);
rem(*it);
}
}
}
}
if (sz(res) != d) {
cout << "NO\n";
return;
}
if (dc[res[0]] <= 0) {
cout << "NO\n";
return;
}
FOR(i, 0, d - 1) {
if (!(i & 1)) {
if (res[i] <= res[i + 1]) {
cout << "NO\n";
return;
}
}
else {
if (res[i + 1] <= res[i]) {
cout << "NO\n";
return;
}
}
}
cout << "YES\n";
FOR(i, 0, d) cout << dc[res[i]] << " \n"[i == d - 1];
};
solve();
}
}
int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(0), cin.tie(0);
if (argc > 1) {
assert(freopen(argv[1], "r", stdin));
}
if (argc > 2) {
assert(freopen(argv[2], "wb", stdout));
}
chemthan();
cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class RESTCH{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni();
int[] B = new int[N];int highestValue = 0;
for(int i = 0; i< N; i++){
B[i] = ni();
highestValue = Math.max(highestValue, B[i]);
}
DS t = new DS(B);
if(!t.possible() || highestValue <= 0){
pn("NO");
return;
}
int remaining = N;
int[] F = new int[1+N];
for(int i = 1; i<= N; i+=2, remaining -= 2){
if(remaining == 1){
//If odd N, last element
Integer nxt = t.higher(F[i-1]);
if(nxt == null){
pn("NO");
return;
}
F[i] = nxt;
break;
}
//Selecting two values a, b such that we have a > max(b, F[i-1]). b is min here, a is nxt
Integer min = t.min();
t.remove(min);
Integer nxt = t.higher(Math.max(F[i-1], min)+1);
if(nxt == null){
pn("NO");
return;
}
t.remove(nxt);
if(t.possible()){
F[i] = nxt;
F[i+1] = min;
}else{
//the median value is causing conflict
t.add(min);t.add(nxt);
int mod = t.mod(), max = t.max();
int modF = t.modfreq();
if(N%2 == 1 && mod == max && modF*2 == remaining+1){
//Fill remaining array like M1M2M3M where M is maximum
hold(mod > F[i-1]);//Otherwise we failed somewhere in previous step
F[i] = mod;
F[i+1] = min;
t.remove(min);
t.remove(mod);
}else{
//Some element has frequency remaining/2
//mod will never be same as min or nxt, otherwise it'd have given possible true
if(mod > nxt){//Can mod appear in ith position, and, is it favourable to us?
t.remove(mod);
t.remove(min);
F[i] = mod;
F[i+1] = min;
}else{
t.remove(nxt);
t.remove(mod);
F[i] = nxt;
F[i+1] = mod;
}
}
}
}
pn("YES");
for(int i = 1; i<= N; i++)p(F[i]+" ");pn("");
}
class DS{
SegTree t;
int size = 0;
int[][] uniq;
TreeMap<Integer, Integer> compress;
public DS(int[] v){
uniq = getUnique(v);
t = new SegTree(uniq.length);
size = v.length;
for(int i = 0; i< uniq.length; i++)t.u(i, uniq[i][1]);
compress = new TreeMap<>();
for(int i = 0; i< uniq.length; i++)compress.put(uniq[i][0], i);
}
void add(int x){
size++;
int ind = compress.get(x);
t.u(ind, 1);
uniq[ind][1]++;
}
void remove(int x){
size--;
int ind = compress.get(x);
t.u(ind, -1);
uniq[ind][1]--;
}
int min(){return uniq[t.min()][0];}
int max(){return uniq[t.max()][0];}
int mod(){return uniq[t.argmaxfreq()][0];}
int modfreq(){return t.count[t.argmaxfreq()];}
int median(){
return uniq[t.kth(size/2+1)][0];//Returns upper median for even size array
}
Integer higher(int x){
Map.Entry<Integer, Integer> e = compress.ceilingEntry(x);
if(e == null)return null;
int nxt = t.ceiling(e.getValue());
if(nxt == -1)return null;
return uniq[nxt][0];
}
boolean possible(){
int med = t.kth(size/2+1), max = t.max();
int fmed = t.freq(med);
if(size%2 == 1 && med == max && fmed*2 == size+1)return true;
if(fmed*2 <= size)return true;
return false;
}
}
int[][] getUnique(int[] v){
int[][] a = new int[v.length][];
int c = 0;
Arrays.sort(v);
for(int i = 0, j = 0; i< v.length; i = j){
while(j < v.length && v[i] == v[j])j++;
a[c++] = new int[]{v[i], j-i};
}
return Arrays.copyOf(a, c);
}
class SegTree{
int m = 1;
int[] count,argmax;
public SegTree(int n){
while(m<n)m<<=1;
count = new int[m<<1];
argmax = new int[m<<1];
for(int i = m; i< m<<1; i++)argmax[i] = i;
for(int i = m-1; i> 0; i--)argmax[i] = count[argmax[i<<1]] >= count[argmax[i<<1|1]]?argmax[i<<1]:argmax[i<<1|1];
}
void u(int i, int d){
count[i+=m] += d;
for(i>>=1; i>0; i>>=1){
count[i] = count[i<<1]+count[i<<1|1];
argmax[i] = count[argmax[i<<1]] >= count[argmax[i<<1|1]]?argmax[i<<1]:argmax[i<<1|1];
}
}
int count(int le, int ri){
int ans = 1;
for(le += m, ri += m+1; le < ri; le>>=1, ri >>= 1){
if((le&1)==1)ans += count[le++];
if((ri&1)==1)ans += count[--ri];
}
return ans;
}
int min(){
int node = 1;
while(node < m){
if(count[node<<1] == 0)node = node<<1|1;
else node = node<<1;
}
return node-m;
}
int max(){
int node = 1;
while(node < m){
if(count[node<<1|1] == 0)node = node<<1;
else node = node<<1|1;
}
return node-m;
}
int freq(int val){return count[val+m];}
int argmaxfreq(){return argmax[1]-m;}//Returns minimum element from all elements with maximum frequency
int ceiling(int val){//First value > val
int node = val+m;
if(count[node] > 0)return node-m;
while(node > 0){
if((node&1) == 0 && count[node^1] > 0){
node ^= 1;
break;
}else node>>=1;
}
if(node == 0)return -1;
while(node < m){
if(count[node<<1] > 0)node = node<<1;
else node = node<<1|1;
}
return node-m;
}
int kth(int k){
k--;
int node = 1;
while(node < m){
if(count[node<<1]<= k){
k -= count[node<<1];
node= node<<1|1;
}else node = node<<1;
}
if(k < count[node])return node-m;
return -1;
}
}
//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 RESTCH().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. 