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

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$ $A$ with the values from $P$ $P$ and $NXT$ $N X T$ , where $NXT_i$ $N X T_{i}$ is the position of $i$ $i$ after applying the operation once (i.e., $NXT_{P_i} = i$ $N X T_{P_{i}} = i$ ).

Next, for each of the $K$ $K$ rounds, set $A_i$ $A_{i}$ to $NXT_{A_i}$ $N X T_{A_{i}}$ for every index $i$ $i$ ( $1 \le i \le N$ $1 \leq i \leq N$ ).

Finally, output $A$ $A$ .

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

Subtask 2

Redefine $NXT_{i, k}$ $N X T_{i, k}$ as the position of $i$ $i$ after applying the operation $2^{k-1}$ $2^{k - 1}$ times.

Build $NXT_{i, k}$ $N X T_{i, k}$ for $1 \le i \le N$ $1 \leq i \leq N$ and $1 \le k \le 61$ $1 \leq k \leq 61$ (since $10^{18} \le 2^{61-1}$ $10^{18} \leq 2^{61 - 1}$ ) by knowing that $NXT_{i, k} = NXT_{NXT_{i, k-1}, k-1}$ $N X T_{i, k} = N X T_{N X T_{i, k - 1}, k - 1}$ .

If the $k^\text{th}$ $k^{th}$ bit is toggled in the binary representation of $K$ $K$ , set $A_i$ $A_{i}$ to $NXT_{A_i, k}$ $N X T_{A_{i}, k}$ .

Finally, output $A$ $A$ .

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

Alternative Solution

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

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

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

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

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

Comments

There are no comments at the moment.