Editorial for SAC '22 Code Challenge 4 Junior P4 - Obligatory Permutation Problem
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1
Initialize an array with the values from
and
, where
is the position of
after applying the operation once (i.e.,
).
Next, for each of the rounds, set
to
for every index
(
).
Finally, output .
Time Complexity:
Subtask 2
Redefine as the position of
after applying the operation
times.
Build for
and
(since
) by knowing that
.
If the bit is toggled in the binary representation of
, set
to
.
Finally, output .
Time Complexity:
Alternative Solution
Note that binary lifting is not the only solution to this problem.
Observe that will repeat after at most
rounds since the maximum cycle length is
.
It suffices to determine the cycles and shift each by modulo the length of the cycle.
The implementation details are left as an exercise to the reader.
Time Complexity:
Comments