DISTINCTNEIG - Editorial

iceknight1093 · November 9, 2022, 6:33am

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

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

DIFFICULTY:

1997

PREREQUISITES:

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;
const ll INF_ADD=1e18;    
#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;}    
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());   
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')

lbm364dl · November 9, 2022, 8:07pm

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.

wuhudsm · November 9, 2022, 9:32pm

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.

notmotivated · November 10, 2022, 2:05am

The 4th line in editorialist’s code is actually O(n²)

imak24 · November 10, 2022, 4:21am

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

iceknight1093 · November 10, 2022, 6:14am

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.

neel_04 · November 11, 2022, 12:17pm

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;
    
}

}