PROBLEM LINK:
Practice
Contest
Author: Anudeep Nekkanti
Tester: Gerald Agapov
Editorialist: Praveen Dhinwa
DIFFICULTY:
CAKEWALK
PREREQUISITES:
ADHOC
PROBLEM:
Given a circle, you can make cuts at positive integered angles intersecting at origin. You are given 3 type of questions to answer.
 Is it possible to make N equal pieces? You have to use the complete cake.
 Is it possible to make N pieces?
 Is it possible to make N pieces, such that no two of them are equal?
QUICK EXPLANATION
 Check if 360 % N = 0 or not.
 Check if N < = 360 or not.
 Check if (N * (N + 1)) / 2 < = 360 or not.
EXPLANATION

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 ?

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.

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:
Authorâ€™s solution
Testerâ€™s solution
Editorialistsâ€™s solution
10 Likes
I made the 3rd part <=25 instead of <=26. hence wrong ans
1 Like
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.
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.
1 Like
Ohhh, now I get it. Sorry, that was dumbâ€¦
I wish to know that why is prerequisite marked as adhoc for cakewalk questions.
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?
@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 1801=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 (902,901)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 (365,364,363,â€¦,361)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
add(5,4,.,1,.,5{0}(xcept zero) is zero for any case sorry still doesnt get it
@yash_15, The problem does not belong to any specific category, it needs some simple observations, So the most suitable category for it is adhoc.
@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â€™.
1 Like
@ashish424: I have edited the editorial accordingly.
add {365,364,363,â€¦,361,36+1,36+2,â€¦36+5)
continuing n=10(even) then angles will be (365,364,363,â€¦,361)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 365=31,364=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 â€¦
@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?
@lalit_horcrux lets take n=5(odd) then 360/5=72 then 722,721,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 {513,512,511,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 â€¦
@ashish424 did you get my explanation â€¦?
Can anyone help me which constraint i misleading?
My solution:
http://www.codechef.com/viewsolution/4119374
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?