HFSEQ - EDITORIAL

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

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

2 Likes

Why I am getting TLE I implemented same thing? Here 's my code