 ZIO05001

# Editorialist:

Darshan Bari (https://www.codechef.com/users/buzz_95)

SIMPLE

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.

1 Like