Editorial for DMOPC '22 Contest 2 P3 - Good Permutations
Submitting an official solution before solving the problem yourself is a bannable offence.
Consider solving this problem if the target permutation is an identity permutation.
Consider the relative ordering of elements in the final answer.
Consider which types of elements can't be swapped, and what that means for the final permutation. If two elements at positions have , , 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 appear before . Using this fact, we can begin to construct our solution.
For this subtask, iterate through all possible pairs of elements . If , draw a directed edge pointing from to , indicating that we need to place element before element 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:
Hint 1 for Full Solution
How can we reduce the number of edges?
Hint 2 for Full Solution
Consider the factors of each element.
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 , where:
, , and .
Using our subtask 1 solution, we would draw edges , and . However, the final edge, 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 of , store the index in a vector , where stores all the indices that have as a prime factor. Since the of any two elements in the same vector will be greater than , 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.
Note from the author
Originally, the problem was just the identity permutation as the target. Credits tofor suggesting the current version of this problem.