PROBLEM LINK:
Contest Div 1
Contest Div 2
Contest Div 3
Practice
Setter: Amruth Kumar
Tester: Anshu Garg
Editorialist: Keyur Jain
DIFFICULTY
Easy-Medium
PREREQUISITES
Greatest Common Divisor, Subsequence Generation
PROBLEM
Chef has an array A of size N. Chef wants to choose any subsequence of size exactly \lceil \frac{N}{2} \rceil from the array such that GCD of all the elements in that sequence must be 2. Chef names such a kind of sequence as a half-sequence.
Help Chef to find whether he would be able to select any half-sequence in the given array.
As a reminder,
- A subsequence of an array is a sequence that can be derived from the given array by deleting zero or more elements without changing the order of the remaining elements.
- GCD stands for Greatest Common Divisor. The greatest common divisor of a subsequence is the largest integer d such that all the numbers in sequence are divisible by d. For more information, refer to here.
- \lceil x \rceil is the ceiling (round up) operation: \lceil 3.5 \rceil = 4 ,\lceil 2 \rceil = 2 .
QUICK EXPLANATION
- For N <= 18, the problem can be brute forced
- For N > 18 (practically, even 16), remove all odd numbers from the input. If we have atleast (N+1)/2 elements remaining and if their GCD is 1 then we have a solution.
EXPLANATION
Let K = (N + 1) / 2 be the length of subsequence we wish to create.
Odd numbers are of no use to us, since including any odd number will make it impossible for our subsequence to have a GCD of 2. So we discard all of them. Let’s call the list of remaining numbers the array B.
It is easy to see that the answer is not possible when B.size() < K.
Moving on, our goal is to find a sequence of length K using elements from B that has GCD = 2. We can divide every number in B by 2 (since they are all even), and the goal now is to find a sequence of length K that has GCD = 1.
Observe that any single number \leq 10^9 can be made up of atmost 9 distinct prime numbers. This means that if GCD([B_0, B_1, \dots , B_N]) = 1, then there must exist atleast one subset of length at most 9 whose elements have GCD = 1. (Proof left as an exercise)
We can choose all of these elements, and fill the remaining K - 9 elements in any way to build a sequence of length K with GCD = 1.
Howevere, what about when K \leq 9 ? For such cases we can use brute force. Simply generate all possible subsequences and check if any of them are valid.
TIME COMPLEXITY
The time complexity is O(N * 2^N) when N <= 18 and O(N) otherwise.
SOLUTIONS
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
vector<vector<int> > ssets;
void combination(vector<int> arr, int n, int r, int index, int data[], int i)
{
if (index == r)
{
vector<int> temp;
for (int j = 0; j < r; j++)
temp.push_back(data[j]);
ssets.push_back(temp);
return;
}
if (i >= n)
return;
data[index] = arr[i];
combination(arr, n, r, index + 1, data, i + 1);
combination(arr, n, r, index, data, i + 1);
}
void brute(int n,vector<int> a, int half)
{
ssets.clear();
int data[half];
combination(a,n,half,0,data,0);
for(int i=0;i<ssets.size();i++)
{
int gcd=ssets[i][0];
for(int j=1;j<ssets[i].size();j++)
{
gcd=__gcd(gcd,ssets[i][j]);
}
if(gcd==2)
{
cout << "yes" << endl;
return;
}
}
cout << "no" << endl;
}
void solve()
{
int n;
cin >> n;
int half=n/2+n%2;
vector<int> a;
for(int i=0;i<n;i++)
{
int p;
cin >> p;
if(p%2==0)
a.push_back(p);
}
if(a.size()<half)
{
cout << "no" << endl;
return;
}
if(a.size()<=16)
{
// cout << "brute" << endl;
brute(a.size(),a,half); //checking all possible subsets of size half
return;
}
int g=a[0];
for(int i=1;i<a.size();i++)
g=__gcd(g,a[i]);
if(g!=2)
{
cout << "no" << endl;
return;
}
cout << "yes" << endl;
}
int main()
{
int t;
cin >> t;
while(t--)
solve();
}
Tester's Solution
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
const int N = 1e5 + 5;
int n;
int a[N];
int32_t main()
{
IOS;
int t;
cin >> t;
while(t--)
{
cin >> n;
int g = 0, ct = 0;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
if(a[i] % 2 == 0)
ct++, g = __gcd(g, a[i]);
}
if(ct < (n + 1) / 2)
{
cout << "No" << endl;
continue;
}
if(n > 16)
{
if(g == 2)
cout << "Yes" << endl;
else
cout << "No" << endl;
continue;
}
vector<int> v;
for(int i = 1; i <= n; i++)
if(a[i] % 2 == 0)
v.push_back(a[i]);
int sz = v.size(), reqd = (n + 1) / 2;
int flag = 0;
for(long long i = 0; i < (1LL << sz); i++)
{
if(__builtin_popcount(i) != reqd)
continue;
int g = 0;
for(int j = 0; j < sz; j++)
{
if(i >> j & 1)
g = __gcd(g, v[j]);
}
if(g == 2) {
flag = 1;
// break;
}
}
if(flag)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}
Editorialist's Solution
public class HalfSequence {
public void solve(int testNumber, InputReader in, OutputWriter out) {
int n = in.readInt();
int k = (n + 1) >> 1;
int[] arr = in.readIntArray(n);
IntList even = new IntList();
int _gcd = 0;
for (int i : arr) {
if (i % 2 == 0) {
i = (i >> 1);
even.add(i);
_gcd = gcd(_gcd, i);
}
}
if (even.size() < k) {
out.printLine("NO");
} else {
if (k <= 10) {
out.printLine(solveBrute(even, k));
} else {
if (_gcd > 1) {
out.printLine("NO");
} else {
out.printLine("YES");
}
}
}
}
static int gcd(int a,int b) {
if(a%b==0)
return b;
else
return gcd(b,a%b);
}
static String solveBrute(IntList nums, int k) {
int n = nums.size();
for (int mask = 0; mask < (1 << n); mask++) {
if (getNumSetBits(mask) == k) {
int _gcd = 0;
for (int i = 0; i < n; i++) {
if (((mask >> i) & 1) == 1) {
_gcd = gcd(_gcd, nums.get(i));
}
}
if (_gcd == 1) {
return "YES";
}
}
}
return "NO";
}
static int getNumSetBits(int x) {
int ans = 0;
while (x > 0) {
ans++;
x -= (x & (-x));
}
return ans;
}
}
Feel free to share your approach. Suggestions are welcomed as always. 
