# 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.