Editorial for Mock CCC '24 Contest 1 S2 - Owen the Toucan

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: weewoo14

For this problem, we must construct a permutation b, by using integers from 1 to N such that the number of unique integers obtained from calculating the GCD of the element at the i^{th} position and the element at the a_i^{th} position of array a is exactly K.

There are many different strategies to construct such an array, and one of the possible solutions will be discussed in this editorial.

Subtask 1 If K = 1, we can create an array a by set a_i = i + 1 for all i where 1 \leq i \leq N - 1, and a_N = 1.
If K = N, we can create an array a by set a_i = i for all i where 1 \leq i \leq N.
Subtask 2 We can split the creation of the array into two separate loops, one covering positions from 1 to N-K+1, and the other covering positions from N-K+2 to N.

The implementation details are left as an exercise for the reader.

Time Complexity: \mathcal{O}(N)


There are no comments at the moment.