I don’t know what happens but my wrong solution passed all test cases, What I did was first I taken all the even elements and then created 2 arrays, I included an element in first array if overall gcd of first array will be less after including this, otherwise it was in second array then I just checked if I get gcd of first array as 1 then answer is YES otherwise NO, but there are many tcs where my solution will fail, for example:
8 4 6
16 8 4 6
mu submission link: Bawal ho gaya ye to
Hello, can’t we do like if the number of even numbers are more than the ceiling value of (n/2) then if the GCD of any 2 even numbers is 2 then the GCD of subsequence array will also be 2???
Would be great if someone can correct me as on submitting code i m getting wrong answer…
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
Hey, I saw your code, can you please explain to me the solve function you wrote?
link to code
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.
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)
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.
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
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)?