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

×

# ANUDTC - Editorial

Author: Anudeep Nekkanti
Tester: Gerald Agapov
Editorialist: Praveen Dhinwa

CAKEWALK

# PROBLEM:

Given a circle, you can make cuts at positive integered angles intersecting at origin. You are given 3 type of questions to answer.

1. Is it possible to make N equal pieces? You have to use the complete cake.
2. Is it possible to make N pieces?
3. Is it possible to make N pieces, such that no two of them are equal?

# QUICK EXPLANATION

1. Check if 360 % N = 0 or not.
2. Check if N < = 360 or not.
3. Check if (N * (N + 1)) / 2 < = 360 or not.

# EXPLANATION

1. Note that we are going to make a cut only of positive integered angle. For piceces to be of equal sizes, all the angles of the cuts should be equal. As we know that angle subtended at the centre of the circle is 360'. If we want to partition 360' into N equal parts, then 360 should be divisible by N. Hence we just have to check the condition whether 360 % N = 0 or not ?

2. Maximum number of pieces we can make are 360 (chose the angle = 1). So if we need to find whether we can make N pieces, we just need to check whether N is less or equal to 360 or not. If yes, then we can make N pieces otherwise we can not.

3. If want to make N pieces, such that no two of them are equal. Then we can make them in order 1, 2, 3, 4, , N. Sum of the sequence upto N terms will be (N * (N + 1)) / 2. Hence if sum of the sequence is going to be less or equal to 360, then we are surely going to make N distinct pieces. (pieces will have angles 1, 2, upto N). Otherwise we can not.

Strategy of making distinct angles:
Assume that you are able to make n distinct pieces i.e. n * (n + 1) / 2 <= 360. Here is the actual strategy of making the cuts. You can make angles starting from 1, 2, 3 like this. If you have to make n pieces and you have already made n - 1 cuts, the remaining angle itself will be greater than n - 1.

Complexity: O(1). All we need to do is constant number of multiplications and divisions. Hence time complexity is constant or O(1).

# AUTHOR'S, TESTER'S AND EDITORIALIST's SOLUTIONS:

This question is marked "community wiki".

asked 19 May '14, 00:23 2.5k53137170
accept rate: 20%

1

I made the 3rd part <=25 instead of <=26. hence wrong ans

(19 May '14, 00:40)

I wish to know that why is prerequisite marked as ad-hoc for cakewalk questions.

(19 May '14, 01:00) 5★

@yash_15, The problem does not belong to any specific category, it needs some simple observations, So the most suitable category for it is ad-hoc.

(19 May '14, 07:19)

For n=2 If we divide,the cake in 2 pieces then in the third part compulsory both the angles will not be 180 degree?

(20 Jun '14, 18:43) 2★

The Ac solution gives y y y for n == 1 but for n = 1 that is for no cuts, we can't get either equal or unequal piece. Will someone explains what I am missing.

(16 Feb, 15:59)

 0 Well, that was frustrating... The statements: "Is it possible to make exactly N pieces from the whole cake?" "Is it possible to make exactly N pieces from the whole cake, in such a way that no two of them are equal?" Are ambiguous. It gives the idea you should use the WHOLE cake. The examples worked when thinking that way. answered 19 May '14, 00:48 3★caioaao 111●2●6 accept rate: 0% 1 Yes. The whole cake has to be used. (Why waste it?) For N=3, you are thinking of taking sectors 90, 90, 90 and throw the remaining 90. But this will result into cutting into 4 pieces. (19 May '14, 00:56) yash_155★ Ohhh, now I get it. Sorry, that was dumb... (19 May '14, 01:00) caioaao3★ n*(n+1)/2?you have written that the pieces will have angles 1,2,3,..n. for example to cut in 4 pieces with the third condition,angles should be 88,89,91,92 and not 1,2,3,4 as they do not cover the whole cake? (19 May '14, 01:20) @ashish424 you need to think carefuly let for example n=2(even)then angles will be 179 and 181 as 360/2=180 and 2/2=1 so 180-1=179,180+1=181 for n=3 (odd)will be 119,120,121 as 360/3=120 and so u have 3's 120 so add 1 to one 120 and subtract from other for n=4 (even) n=2(even) then angles will be 179 and 181 as 360/4=90 and 4/2=2 so (90-2,90-1)and (90+1,90+2).try to do for n=5,6,7.. you will get it now suppose for n=10(even) then angles will be (36-5,36-4,36-3,..,36-1)and (36+1,36+2,..36+5)here 360/10=36 and 10/2=5 so add (-5,-4,.,1,.,5-{0}(xcept zero)go on try for n=26 and 27 u will get it (19 May '14, 01:49) sanzzzay2★ add(-5,-4,.,1,.,5-{0}(xcept zero) is zero for any case sorry still doesnt get it (19 May '14, 02:18) 1 @ashish424: You can make angles starting from 1, 2, 3 like this. If you have to make n pieces and you have already made n - 1 cuts, the remaining angle itself will be greater than n - 1. Hence in this way all the angles will be distinct if n * (n + 1) / 2 <= 360'. (19 May '14, 07:23) @ashish424: I have edited the editorial accordingly. (19 May '14, 07:26) add {36-5,36-4,36-3,..,36-1,36+1,36+2,..36+5) (19 May '14, 08:50) continuing n=10(even) then angles will be (36-5,36-4,36-3,..,36-1)and (36+1,36+2,..36+5)here 360/10=36 and 10/2=5 so add (-5,-4,..,1,2,...,5-{0} to (360/10=36 )(xcept zero)u will get angles like 36-5=31,36-4=32,...,31 and then 36+1=37,36+2=38,...,36+5=41... and try for doing n=26 and n=27 ... you will get the extreme cases for which the question "Is it possible to make N pieces, such that no two of them are equal?" satisfied ... still not understood .. feel free to ask .. (19 May '14, 11:32) sanzzzay2★ got it Thanks! (19 May '14, 16:43) @sanzzzay you have explained the division of n cuts of n which divides 360.What if n doesn't divide 360 ?How will you make the division then? (19 May '14, 17:29) @lalit_horcrux lets take n=5(odd) then 360/5=72 then 72-2,72-1,72,72+1,72+2 taking 72 as mean.. then n=7 ok then (360/7=51.42 )and let take 51.42 as 51 then {51-3,51-2,51-1,51,51+1,51+2,51+3} adding these makes 357 so takes the last one 57 ... the above explanation is just the another approach to solve the "Is it possible to make exactly N pieces from the whole cake, in such a way that no two of them are equal?" you can say it is hit and trial method ... try doing n=26 and n=27 you will get the answer .. (19 May '14, 22:22) sanzzzay2★ @ashish424 did you get my explanation ...? (19 May '14, 22:23) sanzzzay2★ showing 5 of 13 show all
 0 Can anyone help me which constraint i misleading? My solution: http://www.codechef.com/viewsolution/4119374 answered 20 Jun '14, 18:33 2★tech_boy 1.2k●4●19●31 accept rate: 7% if(n!=2 || n>26) { printf("y\n"); } else { printf("n\n"); Hi @tech_boy please can you explain why you give the above condition thankx (20 Jul '14, 19:32)
 0 Just a quick illustration: if you want to make 26 different slices you would go from 1, 2 ... 25 which equals 325 and the last slice would be 35. You could also try 27, but 1, 2, .. 26 equals 351 - and the last slice would have to be 9 (repeating itself). So 26 is the limit. answered 27 Jul '17, 12:27 0★azazello 3●2 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

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,852
×1,688
×968
×14

question asked: 19 May '14, 00:23

question was seen: 7,138 times

last updated: 16 Feb, 15:59