PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Akshit Monga
Tester: Abhinav Sharma
Editorialist: Kanhaiya Mohan
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
Chef has a sequence of integers A of length N. He creates another sequence B of length 2 \cdot N using sequence A. Initially, B is empty. Chef performs the following process.
For each element A_i (1 \le i \le N) of A:
-
Choose any arbitrary integer k (Note that the value of k can be different for different elements).
-
Add A_i-k and A_i+k to B.
Chef then shuffles the sequence B randomly after this process.
You’re provided with a sequence B of size 2 \cdot N. You are required to tell if the provided sequence can be achieved from any sequence A of size N using the given process or not.
QUICK EXPLANATION:
- The answer is
YESonly if the sum of elements of B is even.
EXPLANATION:
Observation
Let us suppose we have two integers X and Y. We need to check if there exists an integer Z such that X = Z - k and Y = Z + k.
Assuming X = Z - k and Y = Z + k, the value of X+Y would be 2 \cdot Z. Thus, Z = \frac{X+Y}{2}.
In conclusion, if the value X+Y is even, there exists an integer Z such that X = Z - k and Y = Z + k.
Based on above observation, for an array A (of size N) to exist, we need to divide array B (of size 2 \cdot N) into N pairs such that:
- Each element of B is present in exactly one pair.
- The sum of each pair is even.
If we are able to achieve this, then, we have a possible array A. The elements of array A would be equal to the mean of the pairs formed by elements of array B.
Claim: There exists a possible array A if the sum of the elements of B is even.
Proof: Let X denote the count of odd elements in B and Y denote the count of even elements in B.
- Since the sum of all elements of B is even, X (count of odd elements) must be even.
- Total count of elements in B is 2 \cdot N (which is even) and the count of odd elements is also even. Thus, the count of even elements, Y = (2\cdot N-X) is even.
For the Y even elements, we can divide them into \frac{Y}{2} pairs. Each pair contains 2 even elements. Thus, each of these pairs has an even sum and is a valid pair.
For the X odd elements, we can divide them into \frac{X}{2} pairs. Each pair contains 2 odd elements. Thus, each of these pairs has an even sum and is a valid pair.
Hence proved that we can construct an array A from B if the sum of the elements of B is even.
In conclusion, we only need to check the sum of the elements of B. If the sum of elements is even, the answer is YES, else it is NO.
TIME COMPLEXITY:
The time complexity is O(N) per test case.
SOLUTION:
Setter's Solution
for _ in range(int(input())):
n=int(input())
print("NO" if sum(map(int,input().split()))%2 else "YES")
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define el "\n"
#define ld long double
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T=1;
cin >> T;
while(T--){
int n;
cin>>n;
n*=2;
ll sum = 0;
rep(i,n){
int x;
cin>>x;
sum+=x;
}
cout<<((sum%2==0)?"Yes":"No")<<el;
}
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
return 0;
}
Editorialist's Solution
#include <iostream>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int sum = 0;
for(int i = 0; i<2*n; i++){
int x;
cin>>x;
sum += x;
}
if(sum % 2){
cout<<"No";
}
else{
cout<<"Yes";
}
cout<<endl;
}
return 0;
}