Problem Link:Difficulty:SIMPLE Prerequisites:Adhoc 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: Setter's Solution:Can be found here Tester's Solution:Can be found here
This question is marked "community wiki".
asked 22 Apr '13, 00:02

I hate the special case !!! Took me so long time to figure out LOL answered 22 Apr '13, 08:21

Multiples of two!! Aww maann... Why in the world was I stuck with powers of two??? :'( answered 22 Apr '13, 00:18

Whats wrong with this? answered 22 Apr '13, 00:06
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

Very nice problem, I spent a lot of time on that one without a reason :D answered 22 Apr '13, 00:47

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

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 .