Editorial for SAC '22 Code Challenge 4 Junior P4 - Obligatory Permutation Problem


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: maxcruickshanks

Subtask 1

Initialize an array A with the values from P and NXT, where NXTi is the position of i after applying the operation once (i.e., NXTPi=i).

Next, for each of the K rounds, set Ai to NXTAi for every index i (1iN).

Finally, output A.

Time Complexity: O(KN)

Subtask 2

Redefine NXTi,k as the position of i after applying the operation 2k1 times.

Build NXTi,k for 1iN and 1k61 (since 10182611) by knowing that NXTi,k=NXTNXTi,k1,k1.

If the kth bit is toggled in the binary representation of K, set Ai to NXTAi,k.

Finally, output A.

Time Complexity: O(NlogK)

Alternative Solution

Note that binary lifting is not the only solution to this problem.

Observe that A will repeat after at most N rounds since the maximum cycle length is N.

It suffices to determine the cycles and shift each by K modulo the length of the cycle.

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

Time Complexity: O(N)


Comments

There are no comments at the moment.