×

SIMPLE

# 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

This question is marked "community wiki".

973568379
accept rate: 14%

2

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 .

(22 Apr '13, 00:24)

 3 I hate the special case !!! Took me so long time to figure out LOL answered 22 Apr '13, 08:21 2★milhaus 46●4 accept rate: 0%
 1 Multiples of two!! Aww maann... Why in the world was I stuck with powers of two??? :'( answered 22 Apr '13, 00:18 4.2k●5●23●64 accept rate: 15% 1 nevermind, better luck next time. :( (22 Apr '13, 00:19)
 0 Whats wrong with this? answered 22 Apr '13, 00:06 8.7k●19●48●98 accept rate: 9% 2 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 :( (22 Apr '13, 00:08) I missed out the special case it seems (22 Apr '13, 00:10) 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. :( (22 Apr '13, 00:13) It took half hour and 2 penalties to get to that corner case.... (22 Apr '13, 00:37) @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. :( But very sad with this. (22 Apr '13, 00:55) 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... :) (y) (22 Apr '13, 15:29) showing 5 of 6 show all
 0 Very nice problem, I spent a lot of time on that one without a reason :-D answered 22 Apr '13, 00:47 16.9k●49●115●225 accept rate: 11%
 0 dont miss k=1, cost me a wrong answer :P answered 22 Apr '13, 09:35 15●1●1 accept rate: 0% 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. (05 Jul '13, 21:12)
 0 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. answered 19 Nov '13, 22:51 6★odule 57●2 accept rate: 20%
 0 Hate the special case, Cost me 2 wrong answer answered 17 Jun '16, 16:52 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,680
×1,173
×950
×14
×1

question asked: 22 Apr '13, 00:02

question was seen: 7,012 times

last updated: 17 Jun '16, 16:52