You are not logged in. Please login at www.codechef.com to post your questions!

×

AMMEAT2 - Editorial

7
1

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

This question is marked "community wiki".

asked 22 Apr '13, 00:02

pragrame's gravatar image

6★pragrame ♦♦
973568379
accept rate: 14%

edited 22 Apr '13, 10:45

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) sourcewizard2★

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

link

answered 22 Apr '13, 08:21

milhaus's gravatar image

2★milhaus
464
accept rate: 0%

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

link

answered 22 Apr '13, 00:18

tijoforyou's gravatar image

2★tijoforyou
4.2k52364
accept rate: 15%

1

nevermind, better luck next time. :(

(22 Apr '13, 00:19) bugkiller3★

Whats wrong with this?

link

answered 22 Apr '13, 00:06

bugkiller's gravatar image

3★bugkiller
8.7k194898
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) anton_lunyov ♦6★

I missed out the special case it seems

(22 Apr '13, 00:10) bugkiller3★

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) bugkiller3★

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

(22 Apr '13, 00:37) devanshug4★

@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) bugkiller3★

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) devanshug4★
showing 5 of 6 show all

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

link

answered 22 Apr '13, 00:47

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
accept rate: 11%

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

link

answered 22 Apr '13, 09:35

gaurav_pk's gravatar image

2★gaurav_pk
1511
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) demon_cross5★

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.

link

answered 19 Nov '13, 22:51

odule's gravatar image

6★odule
572
accept rate: 20%

edited 19 Nov '13, 22:56

Hate the special case, Cost me 2 wrong answer

link

answered 17 Jun '16, 16:52

mohd_aadil_058's gravatar image

4★mohd_aadil_058
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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