EQDIS - Editorial

PROBLEM LINK:

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

Author: Soumyadeep Pal
Testers: Jeevan Jyot Singh, Hriday
Editorialist: Nishank Suresh

DIFFICULTY:

1288

PREREQUISITES:

None

PROBLEM:

Given an array A of length N, decide whether it can be partitioned into two arrays B and C that have an equal number of distinct elements.

EXPLANATION:

The answer is “No” if and only if N is odd and all the elements of A are distinct.

Proof

Let N be odd and all the elements of A be distinct. Then, no matter how the partition is done, B and C will have different sizes (and their number of distinct elements equals their size, so equality is impossible).

Now we have to prove that a suitable division always exists in the other case.

  • Suppose A has an even number of distinct elements — for convenience, let’s call them 1, 2, 3, \ldots, 2K. Then, put all occurrences of 1, 2, \ldots, K into B and all occurrences of K+1, K+2, \ldots, 2K into C. B and C now have K distinct elements each, as required.
  • Suppose A has an odd number of distinct elements — let them be 1, 2, \ldots, 2K+1. Note that, in particular, 2K+1 \lt N, so some element occurs greater than once — let one such element be x.
    Now, create B and C as in the even case by assigning all elements other than x. Finally, place one copy of x in B and the others in C. B and C both have K+1 distinct elements now.

This completes the proof.

Checking the above condition can easily be done with a frequency table in \mathcal{O}(N) since the array elements are \leq N.

TIME COMPLEXITY

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

CODE:

Setter's code (C++)
#include<bits/stdc++.h>
using namespace std;

int main() {
	int tt;
	cin >> tt;
	while (tt--) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (int i = 1; i <= n; i++) {
			int x;
			cin >> x;
			a[x - 1]++;
		}
		if (n % 2 == 1 && *max_element(a.begin(), a.end()) == 1) {
			cout << "NO\n";
		} else {
			cout << "YES\n";
		}
	}
	return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	distinct = len(set(a))
	print('yes' if (distinct%2 == 0 or distinct < n) else 'no')
3 Likes
  1. if distinct elements are even then no worries they will divide
  2. if odd only one element with frequency > 1 is needed to satisfy
void solve(){
	int n;
	cin>>n;
	vi arr(n);
	repi(0,n-1) cin>>arr[i];
	
	map<int,int> m;
	repi(0,n-1) m[arr[i]]++;
	
	if((int)m.size()==1){
		auto it = (*m.begin()).first;
		if(m[it] <= 1){
			cout<<"NO\n";
			return;
		}
	}else{
		int size = m.size();
		if(size%2 != 0){
			bool check = false;
			for(auto x : m){
				if(x.second > 1){
					check = true;
					break;
				}
			}
			if(!check){
				cout<<"NO\n";
				return;
			}
		}
	}
	cout<<"YES\n";
}

What if we take n=4
And array elements 1 1 1 3 ??

1 Like

one array will contain 3 the other will contain 111

Thanks now I got it
I thinks that we should divide the array into B and C with equal no of elements

1 Like

This is my code but it passes only one tc does any one have any edge cases where it fails?

edit: so basically if even it will some how form so even == yes
and if odd then also will form eg 2 3 1 1 1 = 1 2 and 3 1 and will form only exception if all the numbers are unique

#include

#include

#include

#include

#include

using namespace std;

#define ll long long int

int main(){

ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);      //this is fast I/O (inputput output) use header file <cstdio>

ll t;cin>>t;

while(t--){

    ll n; cin>>n;

    ll a[n];

    map<ll,ll>freq;

    for(int i=0; i<n; i++){

        cin>>a[i];

        freq[a[i]]++;

    }

    if(n%2!=0)

        cout<<"NO"<<endl;

    else{

        ll unique = 0, odd=0;

        for(auto it:freq){

            if(it.second==1)

                unique++;

            else if(it.second%2!=0)

                odd++;

        }

        if((unique+odd)%2==0)

            cout<<"YES"<<endl;

        else

            cout<<"NO"<<endl;

    }

}

return 0;

}

What you’re saying is correct, but that isn’t what your code is doing.

if (n%2 == 0) cout << "NO" << endl; is obviously wrong, even on the example you provided.

Try to simplify your code and implement exactly the things you said, and you will get AC:

  • If all the numbers are distinct and the array size is odd, the answer is no
  • Otherwise the answer is yes
1 Like


plz explain how 1 2 1 can be divide into two parts such that each part has same n.o of distinct elements…

b=11 = 1ele
c=2 = 1ele

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		while(tc-- > 0){
		    int n = sc.nextInt();
		    int []arr = new int[n];
		    Set<Integer> set = new HashSet<>();
		    int count = 1;
		    boolean flag = false;
		    HashMap<Integer, Integer> map = new HashMap<>();
		    for(int i=0; i<n; i++){
		        arr[i] = sc.nextInt();
		        set.add(arr[i]);
		        
		        if(map.containsKey(arr[i])){
		            map.put(arr[i], map.get(arr[i]  + 1));
		            if(!flag){
		            count++;
		            flag = true;
		            }
		        } else{
		            map.put(arr[i], 1);
		        }
		    }
		  
		  
		  // if there are Even Distinct Elements then they will divide
		    if(set.size()%2 == 0){
		        System.out.println("YES");
		    }else{
		    
		    // In Case of Odd Distinct Elements one Elements with freq > 1 is required  
		    if(count > 1){
		        System.out.println("YES");
		    }else{
		        System.out.println("NO");
		    }
		    }
		    
		}
	}
}

oh I thought order has to stay same…ok thanks anyway

1 Like