×

# 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".

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

By Email:

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