try this case:
6
30 42 70 1 3 5
we required subsequence of length 3
gcd(30,42) = 6 & gcd(30,70) = 10 & gcd(42,70)=14
as you can see there is no pair with gcd=2
but if we take all three together then the gcd(30,42,70) =2
Hope it helps you
1 Like
Hey, I saw your code, can you please explain to me the solve function you wrote?
link to code
Explanation
Okk I will start from the beginning
In the main I am just checking a few trivial conditions first . Then , I am checking 50 random no. , And in the solve function I am just checking if this no. is one of ((n+1)/2) , if it is solution is yes else no . The probability of it giving a Wrong answer is 2^(-50) .
Now the solve function : First I am finding out all the factors of the randomly selected no. . Then from those factor I am inserting the prime no. in a set . Then I am checking that whether this(prime factor) divides each no. in given array or not . If for all prime no. there is atleast one no. each such that it (prime factor) doesn't divide it then the answer can be yes else it's false .
Now if (m+1)>=((n+1)/2) where m is no. of prime factor and n is size of array . Then I am trying to every time delete the no. which has maximum no. of prime factors not occuring it . Hence finding out no. of elements of array required for this no. to be in (N+1)/2 , if it exceed (n+1)/2 then NO else Yes.
3 Likes
how u can say that we need to check only for the first ceil(n/2)-1 elements? do you have any proof ?
Actually the solution is wrong , it passed because of weak test cases. 
Test case
1
5
30 30 30 42 70
Correct output
YES
(30,42,70)
1 Like
https://www.codechef.com/viewsolution/51354934
Can anyone tell me why it is failing ?
My approach :- for N<16 I am finding two numbers whose gcd is 2, if this is true then we can take K-2 other numbers otherwise NO. And for N>16 I am simply checking wheather the gcd is 2 or not. @amruth_kumar
Thanks for the explanation
It was not satisfactory, but I think I got a decent idea.
Seems like many incorrect solutions got accepted due to weak tests on this problem which is unfair to many participants. Is it possible to re-judge all the submissions for this problem with stronger tests just like Codeforces does? @admin @daanish_adm @ashishgup_adm
can someone explain why for k <= 9 we have to apply brute force? why can’t the general approach work here?
We had tried adding a lot of different types of cases, and a lot of solutions (even randomized) ones had failed
But yes, we notice that some of them passed - we’ll try to test more thoroughly in the future, but it would not be fair to rejudge the solutions because the participants moved on after solving the problem, if they got WA in contest, they could have corrected the code.
Even Codeforces does not rejudge solns after systest, there is uphacking which happens, but it does not affect the result of the contest - a very recent Div1+2 problem E had the same issue.
4 Likes
The answer is very simple why I take first ceil (N/2)-1 elements is because they are nearer to 2 than the rest cause I am finding them after applying sort. Moreover I leave one place of ceil (N/2)th element cause for it I can check the combination of first of them with the rest of them. Let me give an example suppose
A = {4,8,16,64,70} Let this be our array of even numbers after sorting. Now let us take the gcd of the first ceil(5/2)-1 = 2 elements. Thus gcd(4,8) = 4 but now the part comes. Now I need one more element to fill in the subsequence to complete the length of 3. If I would choose the next element = 16 only, then my answer would be wrong as gcd remains to be 4 but instead of taking 16 as my only choice I can consider the other elements left in the array as a potential choice cause even if a single number I find that has gcd with present gcd of 4 = 2 then my work is done so I simply have gcd of first ceil(N/2)-1 elements. Now I simply take a for loop and check if any of the rest of the numbers give a gcd of 2 with combination of the rest of the elements. One more thing is that if I am able to find that gcd of first ceil(N/2)-1 elements of the sorted array is 2 then you do not need to check further. You can simply print yes in that case and also in he case when 2 is present itself in the array.
I am attaching my code link : CodeChef: Practical coding for everyone
1 Like
So some time ago someone asked why taking the first ceil(N/2)-1 elements. So I thought all over again and found that the choice of the ceil(N/2)-1 elements is independent. It is not necessary to take the first, you can also take last ceil(N/2)-1 or middle or any random ceil(N/2)-1 elements in the first go. The important part is that you have to leave a place for the last element of subsequence to fill so that you could take all combinations. At the end the only important thing is to find a single number that gives gcd with rest of the numbers as 2 so there is no restriction on choice. It is only that taking the first ceil(N/2)-1 elements in the first go is more systematic and that’s all. You can choose any of the elements in the first go and leave one place for last element so as to check if you can get gcd = 2. Just don’t take the same elements that you had taken earlier and that’s all.
General approach will also work. Moreover I think that general approach of O(N) is much better.
one reason is because of the global variable val. You are not initializing it every time.
Notice the example that I mentioned( [210,462,330,770] ). The numbers were generated with different combinations of primes. In that array, the GCD of N numbers is 2 but for any K numbers, GCD is not 2 right.
So, if we try to create such kind of array with N=20, by different combinations of primes, values will exceed 10^9. This implies if GCD is of N numbers is 2( N > 16), we can choose at least one subsequence of size K with gcd 2.
Can anyone prove this statement or give insights(if not proof)?
Thanks for replying, I corrected the error, but it is still giving WA which is obvious. I’m looking for any test case for N<16 for which it is failing. It would be great if you can help.
Let’s say n = 6 and you have to find the subset of size 5.
Let’s say all the numbers in set B are made of p1, p2… p6 prime numbers only (if there are more than the chances of getting gcd 1 increases).
So an example where gcd of whole array is 1, and still you cannot choose such a set
{
p1.p2.p3.p4.p5,
p2.p3.p4.p5.p6,
p3.p4.p5.p6.p1,
p4.p5.p6.p1.p2,
p5.p6.p1.p2.p3,
p6.p1.p2.p3.p4,
}
here, the gcd of this set is 1, but set of 5 numbers with gcd 1.
Usually when the size of this set is greater than 8, this type of set cannot be made such that every element can be <= 10^9.
Actually this is an example, which i used to contradict the logic that i can make a set of size, N < 8 where gcd is 1, so there would exist a proper subset with gcd 1.
2 Likes
Let, n = 5
5 4 6 24 48
Check these case there is 4 even number and I have to take 3 numbers for my required subsequence.
If We take the last 2 number (24,48) as u said, and then take another from the rest it will give me a NO.but if we take the first 2 number first then It gives me a YES.
1 Like
Actually this is just a counter case… There surely can be many cases where you can make a subset with gcd 1 when n is smaller than 9, but it’s not always true for that case… But it is always true for n greater than 9 if the gcd of the whole set is 1