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

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$ $b$ , by using integers from $1$ $1$ to $N$ $N$ such that the number of unique integers obtained from calculating the GCD of the element at the $i^{th}$ $i^{t h}$ position and the element at the $a_i^{th}$ $a_{i}^{t h}$ position of array $a$ $a$ is exactly $K$ $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

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

N - K + 1

, and the other covering positions from

N - K + 2

N

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

Time Complexity: $\mathcal{O}(N)$ $O (N)$

Comments

There are no comments at the moment.