ZIO05001 - Editorial

[buzz_95]

PROBLEM CODE:

ZIO05001

PROBLEM LINK:

zio2005-qpaper.pdf

Editorialist:

Darshan Bari (buzz_95 | CodeChef User Profile for Darshan Bari | CodeChef)

DIFFICULTY:

SIMPLE

PREREQUISITES:

Math

PROBLEM:

Given N, break it into some m integers P_1,P_2,…,P_M such that the LCM of these m integers is maximized. Answer for three values of N: {9,12,15}.

QUICK EXPLANATION:

Since the values of N are small, one can brute with optimizations such as avoiding repeated values and keeping the sequence increasing. For more explanation, read below.

EXPLANATION:

1. Since there are N circles and N arrows are supposed to be drawn between them such that for each circle, exactly one arrow begins at a circle and exactly one arrow ends at that circle. So
   the problem breaks down to breaking the given number N into m integers P_1, P_2,…, P_m such that
   P_1 + P_2 + … + P_m equals N. This means we are creating m loops of sizes P1, P2,…,
   Pm.

2. Also, because of “No arrow can both begin and end at the same circle.”, any loop cannot be
   of size 1.(P_i \neq 1).

3. The dance ends when all the monkeys have simultaneously returned to the circles where
   they initially started. Hence a monkey from loop 1 will return to its initial position after
   every P_1 steps, a monkey from loop 2 will return to its initial position after every P_2 steps,
   and so on. Generalizing a monkey from loop i will return to its initial position after every P_i
   steps. Hence the first instant when every monkey will return to its initial position will be the
   LCM of P_1, P_2,…, P_m.
   Hence we have to maximize lcm of P_1, P_2, P_3,…, P_m.

4. One way to do this is to break the given N into m distinct integers considering that the lcm is
   to be maximized. For this, it is greedy to consider m integers such that each pair is a
   coprime integers that add up to N. Also, to minimize the number of duplicate sequences
   keep the next term of the sequence greater than the current term.

5. For example, consider N = 15. Start with 15 = 2 + 3 + 5 + 5, but since this yields the answer
   as 30 and 5 is repeated, we try for another such sequence P (15 = 3 + 4 + 8), the answer is

6. Next sequence can be
   3 4 8
   3 5 7
   3 12
   4 5 6
   4 11
   5 10
   6 9
   7 8
   15

7. For example: if N (Number of circles) = 5, it is profitable to make two loops of sizes 2 and

8. Because of this, after 6 steps all the monkeys return back to their initial positions
   simultaneously.
   Simulation:
   Initial Positions: 1 2 , 3 4 5
   Step 1: 2 1 , 5 3 4
   Step 2: 1 2 , 4 5 3
   Step 3: 2 1 , 3 4 5
   Step 4: 1 2 , 5 3 4
   Step 5: 2 1 , 4 5 3
   Step 6: 1 2 , 3 4 5

For 9, breaking 9 into 4 and 5 gives 20 as the maximum number of steps.
For 12, breaking 12 into 3, 4 and 5 gives 60 as the maximum number of steps.
For 15, breaking 15 into 3, 5 and 7 gives 105 as the maximum number of steps.

[sudheerays123]

I have a slightly different explanation :

1. If we include 5 circles in one loop ( i.e first circle --> second circle , second circle --> third circle , third circle --> fourth circle , fourth circle --> fifth circle , fifth circle --> first circle ) then we can see that ALL the monkeys in these 5 circles WILL come back to their original circle ( position ) after 5 whistles

and lets say we have another loop consisting of 4 circles ( first circle --> second circle , second circle --> third circle , third circle --> fourth circle , fourth circle --> first circle ) then ALL these 4 monkeys in these four circles WILL come back to their original circle ( position ) after 4 whistles

Ok this being done , we have to find the answer for this :

All the monkeys in the first 5 circles will come back to their position after 5 whistles
All the monkeys in the next 4 circles will come back to their position after 4 whistles

But the show ends when all the monkeys come back to their circle simultaneously , so we find that after 20 ( lcm of 5,4 ) all the monkeys will come back to their original circle or position simultaneously when the show ends

2. How to do this

We see that each circle should be part of one and only one loop

Let L1 be the length ( number of circles in that loop ) of the first loop .
Let L2 be the length ( number of circles in that loop ) of the second loop.
.
.
.
.
.
Let Lm be the length ( number of circles in that loop ) of the last loop.

As each circle should be part of one group we get - L1 + L2 + … Lm = N

And answer for loops with length L1,L2 … is equal to LCM(L1,L2,…,Lm)

So we should decide the lengths of each loop now such that Sum of Li’s = N and LCM(L1,L2,…Lm) is maximum ( we also make sure Li is not equal to 1 as restricted in the problem )

Thanks for the nice editorial

[trisanu]

I don’t understand what do you mean by loops. please explain.