ZIO05001 - Editorial

PROBLEM CODE:

ZIO05001

PROBLEM LINK:

Editorialist:

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

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.

1 Like