Editorial for DMOPC '22 Contest 2 P3 - Good Permutations


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

Hint 1

Consider solving this problem if the target permutation is an identity permutation.

Hint 2

Consider the relative ordering of elements in the final answer.

Hint 3

Graph Theory

Hint 4

Topological Sorting

Solution Idea

Consider which types of elements can't be swapped, and what that means for the final permutation. If two elements at positions (i,j, i < j) have \gcd (\text{T}[i], \text{T}[j]) > 1, their relative ordering will be fixed in the final answer. This is because no matter the order of swaps you conduct, they will never be able to swap past each other. This means that in the final answer, we must have \text{T}[i] appear before \text{T}[j]. Using this fact, we can begin to construct our solution.

Subtask 1

For this subtask, iterate through all possible pairs of elements (\text{T}[i], \text{T}[j], i < j). If \gcd (\text{T}[i], \text{T}[j]) > 1, draw a directed edge pointing from \text{T}[i] to \text{T}[j], indicating that we need to place element \text{T}[i] before element \text{T}[j] in our final answer. From here, we can do a greedy topological sort on the graph, prioritizing elements with maximal values first to construct our final answer.

Time Complexity: \mathcal{O}(N^2)
Hint 1 for Full Solution

How can we reduce the number of edges?

Hint 2 for Full Solution

Consider the factors of each element.

Full Solution

For the full solution, we need a way to reduce the number of edges in the graph. The key insight is that not all edges are necessary. Consider three indices (i < j < k), where:

\gcd (\text{T}[i], \text{T}[j]) > 1, \gcd (\text{T}[j], \text{T}[k]) > 1, and \gcd (\text{T}[i], \text{T}[k]) > 1.

Using our subtask 1 solution, we would draw edges i \rightarrow j, j \rightarrow k and i  \rightarrow k. However, the final edge, i \rightarrow k can be shown to be redundant in our topological sorting. We can ignore these redundant edges by changing the ideology in which we draw our edges.

Consider iterating through all elements from left to right. For each prime factor F of \text{T}[i], store the index i in a vector \text{P}[F], where \text{P}[K] stores all the indices that have K as a prime factor. Since the \gcd of any two elements in the same vector will be greater than 1, we can add edges between all adjacent elements in these vectors to construct the graph. Finally, proceed with the greedy topological sort on the graph as before, prioritizing maximal values first.

Time Complexity: \mathcal{O}(N \log N)
Note from the author

Originally, the problem was just the identity permutation as the target. Credits to Maillew for suggesting the current version of this problem.


Comments

There are no comments at the moment.