AMMEAT2 - Editorial

Problem Link:

Practice

Contest

Difficulty:

SIMPLE

Pre-requisites:

Ad-hoc

Problem:

Given integers N and K, pick K integers in 1…N, such that no two chosen integers are relatively prime.

Explanation:

Let us try to construct a set of K integers such that no two are coprime. If we choose a number x (>1), and pick all multiples of x, then clearly no two of them will be coprime (all the numbers are divisible by x)! Thus, we can pick a set of size floor(N/x) having such a property. Thus, it is in our interest to have x small.

Indeed, if we pick x = 2, then for any K <= floor(N/2), we can just output the set 2, 4, 6, …, 2K. Hence, we have the sufficient condition when K <= floor(N/2).

It turns out that this sufficient condition is also necessary (almost). The fact is, when K > N/2, any set of size K will have some 2 consecutive elements. These consecutive elements will then be coprime.

The only special case is where (N, K) = (1, 1). In this case, since K = 1, we can output plate 1 and we’re done.

Formally, we can prove the necessity as follows:

If K = 1, we output 1 and we are done.

If K > 1, then we can can never have 1 in our set.

Then, from (2i, 2i+1), we can pick only one of the two. That is, we can pick only one from (2, 3), (4, 5), …, which gives us the bound of floor(N/2).

Setter’s Solution:

Can be found here

Tester’s Solution:

Can be found here

6 Likes

Whats wrong with this?

You should try to look at the editorial at least briefly. If anybody will simply ask for help without reading, there is no sense in publishing them :frowning:

2 Likes

I missed out the special case it seems

feeling like banging my head on the wall! missed out the special case. so stupid of me. totally disappointed. that pulled my confidence down and I was unable to approach other problems positively. :frowning:

Multiples of two!! Aww maann… Why in the world was I stuck with powers of two??? :’(

1 Like

nevermind, better luck next time. :frowning:

1 Like

quite simple and tricked me . I was thinking in tune of multiples of two but missed the second fact that after K > N/2 numbers can’t remain non consecutive .
good problem by all standards .

2 Likes

It took half hour and 2 penalties to get to that corner case…

Very nice problem, I spent a lot of time on that one without a reason :smiley:

@devanshug >> I wish I could have concentrated more on that special case. Power cuts were so frequent during the entire contest due to bad weather here, I know how I managed to code this with candle beside me. :frowning: But very sad with this.

I hate the special case !!! Took me so long time to figure out LOL

2 Likes

dont miss k=1, cost me a wrong answer :stuck_out_tongue:

no probs dude… atleast you maintained a coders spirit… and thats all is needed and what makes you different from others… Be happy and keep coding… :slight_smile: (y)

The question asks us to find a set of k numbers such that every pair is relatively prime.Right?
Then why are we trying to find a set of non co-prime numbers? My question may be silly, but I’m just not getting it.

This special case is very stupidly given in official tests since task statement say:

“On this occasion, he wants to choose the K plates by a strange way: if both ith and jth plates are chosen, then i and j must not be relative prime, for all 1 ≤ i < j ≤ N.”

if You look here, must be i < j. Your proof is nice, (almost). Try to prove from here

“1 ≤ i < j ≤ N” that N can be 1.

Don’t answer me that not both plate are chosen.

Hate the special case, Cost me 2 wrong answer