ANUDTC - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

CAKEWALK

PREREQUISITES:

AD-HOC

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:

Author’s solution
Tester’s solution
Editorialists’s solution

10 Likes
2

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

1 Like
3

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.

4

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
5

Ohhh, now I get it. Sorry, that was dumb…

6

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

7

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?

8

@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

9

add(-5,-4,.,1,.,5-{0}(xcept zero) is zero for any case sorry still doesnt get it

10

@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.

11

@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
12

@ashish424: I have edited the editorial accordingly.

13

add {36-5,36-4,36-3,…,36-1,36+1,36+2,…36+5)

14

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 …

15

got it Thanks!

16

@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?

17

@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 …

18

@ashish424 did you get my explanation …?

19

Can anyone help me which constraint i misleading?
My solution:
http://www.codechef.com/viewsolution/4119374

20

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?