# DISTINCTNEIG - Editorial

Author: Satyam
Testers: Nishank Suresh, Satyam
Editorialist: Nishank Suresh

1997

Observation

# PROBLEM:

You are given an array A of length 2N. Let B be an empty array. Repeat the following N times:

• Pick two elements x and y of A. Delete them from A and append x-y to B.

Is it possible to perform moves so that B_i \neq B_{i+1} for each 1 \leq i \lt N?

# EXPLANATION:

Suppose we perform moves on A in some order to end up with B. Letās analyze the array we get.

• If B_i \neq B_{i+1} for any i, of course weāre happy.
• Otherwise, B_i = B_{i+1} for some index. There are two cases here:
• If B_i \neq 0, we can actually fix this error. Note that B_i = x - y for some x and y from A. Instead, we couldāve just chosen B_i = y - x instead: now B_i and B_{i+1} have different signs, so they obviously canāt be equal.
• If B_i = 0, once again we have two cases:
• Suppose B_i = x - x and B_{i+1} = y - y, where x \neq y. Then, we can replace them with x-y and y-x instead, which fixes the problem.
• However, if B_i = B_{i+1} = x - x, thereās nothing we can do.

This should give us the intuition that if there are too many occurrences of the same integer x in A, weāll always end up with some adjacent pair in B thatās both x - x, which canāt be fixed.
But, how many is too many?

Letās fix an integer x, and say it occurs k times in A. Then,

• If k \leq N, there exists a way to create B such that we never create zeros of the form x - x, since we can always pair an x with a non-x.
• Otherwise, there will always be some pairs of the form x - x.
• There are 2N - k non-x elements, allowing us to create at most 2N - k pairs of x with something else.
• This leaves a minimum of k - (2N - k) = 2k - 2N instances of x, which means B will contain at least k-N zeros of the form x-x.
• For these zeros to not adjacent in B, their number cannot exceed half the length of B (which is N). That is, k-N \leq \left\lceil \frac{N}{2}\right\rceil must hold (\left\lceil \ \ \right\rceil denotes the ceiling function).

Now notice that if this condition holds for some k, it will also hold for any lower k. So, itās enough to check this for the largest value of k. That is,

• Let k be the largest number of occurrences of some element in A.
• Then, the answer is āYesā if and only if k - N \leq \left\lceil \frac{N}{2}\right\rceil

# TIME COMPLEXITY

\mathcal{O}(N) per test case.

# CODE:

Setter's code (C++)
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
const ll INF_MUL=1e13;
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#ifndef ONLINE_JUDGE
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);
#endif
void _print(ll x){cerr<<x;}
void _print(char x){cerr<<x;}
void _print(string x){cerr<<x;}
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";}
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=1e9+7;
const ll MAX=1000100;
void solve(){
ll n; cin>>n;
vector<ll> freq(n+5,0);
ll till=n+(n+1)/2;
for(ll i=1;i<=2*n;i++){
ll x; cin>>x;
freq[x]++;
}
sort(all(freq));
if(freq.back()>till){
cout<<"NO\n";
}
else{
cout<<"YES\n";
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
mx = max(a.count(x) for x in a)
print('Yes' if (mx - n) <= (n+1)//2 else 'No')


Great editorial as always. I understood the given formula. During the contest, I came up with a different one, namely, the answer is yes if and only if \lfloor \frac{k}{3} \rfloor \le 2n - k, where k is the maximum number of times an element appears.

This is because I thought the worst case to be pairing something like (x, x), (x, y) many times, where y is any other element, to make the differences alternating between 0 and any other difference. This means for each group of 3 x's, we need another element (and there are 2n-k of them).

Any idea on how this is equivalent to the formula from the editorial? It doesnāt seem obvious to me.

Itās a good variant of a classic problem:given a multiset S of size 2N,you can do operation:choose x,y ā Sļ¼xā yļ¼,erase x,y.Judge if you can make S empty.

In fact, it can be solved in O (n).The construction of the scheme is also interesting,although this problem does not require output scheme.

The 4th line in editorialistās code is actually O(nĀ²)

Can you share the link of this classical problem? I canāt find this online.

Thereās a couple of ways to see that theyāre equivalent.

One way is logically: your method essentially pairs up the 2n-k non-x values with 2n-k copies of x, which leaves us with 2k - 2n values of x paired with each other, at which point you come to the same argument that Iāve mentioned in the editorial.

You can also see it algebraically, though itās a bit annoying working around the floors and ceilings.
Essentially, \frac{k}{3} \leq 2n - k \iff 4k \leq 6n \iff 2k \leq 3n.
Similarly, k-n \leq \frac{n}{2} \iff k \leq n + \frac{n}{2} \iff 2k \leq 3n.
Throwing in the floors and ceils probably leaves you with a bit of casework but it should work out nonetheless.

Correct, I chose to implement it that way because the constraints allowed for it and itās short
Itās obviously fairly easy to optimize it with sorting or maps or whatever.

2 Likes

my though process was like this let n(eg3) be odd then worst case senerio would be(array b) = x _ x, where x is the repeating element and 'ā is a different element, and for n (eg 4) be even then worst case would be = x_x or _x_x so, basically a has 2*n elements where for n=3(max repeating element would be (4 since 2xās)) and similarly for n=4(max repeating element would be(4 since 2xās)) , since x = Ax-Ay. but why my code is wrong

void solve(){
int n;cin>>n;
int l = 2*n;
vectorv(l);
map<ll,ll>freq;
for(int i=0; i<l; i++){
cin>>v[i];
freq[v[i]]++;
}

int flag = 0;
int count = 0, max_count = 0;
for(auto it:freq){
count = it.second;
max_count = max(count,max_count);
}
if(n%2==0){                 //if n is even
if(max_count>n) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
else{                       //if n is odd
if(max_count>n+1) cout<<"NO"<<endl;
else cout<<"YES"<<endl;

}


}