Editorial - PARPERM (Unofficial)

editorial
1

The problem states we need to create 2 sets of numbers where any 2 numbers a, b that are not in the same set must have gcd(a, b) = 1
Clearly 2, 4, 6, 8, … must be in the same set. Because otherwise there will be a pair whose gcd is at least 2. Lets say, they are in set A. The other set will be called as B. Let us consider only n >= 4. For n < 4 answer is Yes.
Now
claim 1:
The numbers { 2, 3, 4, 5, 6, 7 … n/2} will be in set A.
Why? Because (n/2) * 2 will be an even number which must be in A. So if (n/2) is in B, gcd(n/2, n/2 * 2) will be at least n/2
So now we have only { n/2 + 1, n/2 + 2, n/2 + 3, … n } as our candidate for set B .
claim 2:
Any number > n/2 that is not prime will be in set A.
Because in that case it must a multiple of a number which is in set A. So if it is taken into set B, gcd will be greater than 1.

Conclusion:
We should take only the primes in range [n/2 + 1, n] in set B.
Notice we can also take 1 in set B. We can also erase any number from set B and insert it into set A. Because gcd will still remain 1 as they all are prime. But we can’t do same from A to B.
So, while B has an element and size of B is neither k nor n-k, we can erase an element from B and insert that into A. [I regret missing this resizing part in contest time :(( ]

Lastly we just need to check whether A.size == k or B.size == k. If both are false answer is No. Otherwise we print any of A and B which size equal to k and have our answer :))

Code: complexity : O(n * sqrt(n))

1 Like
2

bruh
let,
c1 : all primes > n/2 + 1
c2 : n - c1

if c1<k && c2>k
print (‘NO’)

else
if(c1>=k)
print the first k elements from c1
else
first print the c2 elements
then print the K-c2 elements if (K is still positive)

am I missing anything coz this is giving wa in a lot of tcs

thanks in advance

3

Your solution will give wrong answer when c1 < k && c2==k. Try this:
1
6 4
Output:
YES
1 2 3 4
Answer should be:
YES
2 3 4 6

Basically you are printing from 1 in that case, so last element 6 is going into set B. That’s where the mistake…
Your accepted code

4

thanks brother

1 Like