HFSEQ - EDITORIAL

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. :slight_smile:

11 Likes

What should be the output for this test case:
6
8 16 24 26 28 30
Can somebody please tell this…
gcd of 26,28,30 is 2 and it is of size 3 = [6/2] , so should it print “YES”?

1 Like

Yes that’s correct.

1 Like

I just ran an AC solution submitted by someone , which gives NO as output for this test case, and is accepted…

1 Like

Which one can you provide the link please?

1 Like

That solution is incorrect then. Sometimes wrong solutions get accepted due to weak test cases.

1 Like

https://www.codechef.com/viewsolution/51338207

2 Likes

Just because you asked , here are a few codes and few test cases .

1 Like

There are many solutions giving NO as answer for the following test:
1
4
4 8 18 20
'Cause they are sorting the sequence and just checking the first (n+1)/2 even elements.

2 Likes

hmmmm, if that’s the case i get your frustration , we always make sure to make things right , apology for weak cases , though hope you can learn something out of the problem :slight_smile:

6 Likes

Actually I leaned a lot , one of the things look for simple solution , I oversolved the problem ( I used randomisation to check for random 50 numbers ) luckily got AC within Time. :slight_smile:

2 Likes

Glad for that!

2 Likes

Look even my stupid solution got accepted.

1 Like

Observe that any single number <=10^9 can be made up of at most 9 distinct prime numbers. Can anyone please give the proof of that? Why is it so?

Observe that the product of the first 9 odd primes is 3,23,48,46,615 already greater than 1e9.

3 Likes

thnx for clarification

can anyone explain a little more why 9?

1 Like

First 9 odd primes?
Shouldn’t they be 3,5,7,11, … so on?

1 Like

let’s see this example: N=4, A=[ 210,462,330,770]. Here K=2. GCD of all 4 numbers is 2, but for any 2 number GCD is not 2. similarly, when k \le9 we cannot simply guess the answer by finding GCD of the whole array and we need brute force.

If N=20, K would be 10. suppose if the gcd of 20 elements is 2, we can choose at least one subsequence of size 10 with gcd 2. Because every number( \le10^9) can be made up atmost 9 distinct primes.

1 Like

There is no need to see the number of digits a number has. A simple solution is that I had done is that we know that you cannot take odd numbers for getting gcd = 2 thus you can straightaway reject them. Next store all the even numbers. Since subsequence has to be of length of ceil of N/2 thus we can check if length of even numbers array is less than ceil of N/2.If it is true then we cannot make a subsequence of length ceil(N/2). If the size of even numbers array is greater than or equal to ceil(N/2) then sort the array. If the first number is 2 then no further checking 2 is itself the smallest even number (natural).You can always make a subsequence of the above requirement if 2 is present. If 2 is not present then thinking part comes in. Take the gcd of first ceil(N/2)-1 numbers from this array. If its gcd is 2 then answer is yes else now you can take the gcd and start for rest of element taking one at a time if the gcd of first ceil(N/2)-1 numbers and the present number is 2. If at any point its possible then answer is yes else the answer is a BIG NO

5 Likes