Editorial for Yet Another Contest 4 P2 - Alchemy 2
Submitting an official solution before solving the problem yourself is a bannable offence.
We can visualise each element as a node in a graph, with a directed edge being added between and . Since using the machine corresponds to traversing an edge of the graph, is equal to the reachability of node (the number of nodes reachable from ).
In this subtask, it is always possible to construct sequence . For each node, if it has a reachability of , we add an edge from that node to itself. Otherwise, if this node has a reachability of , we add an edge from this node to any node with a reachability of .
We can perform the same solution as before. When we process a node with a reachability of , it suffices to add an edge from this node to a node with a reachability of .
If no node with a reachability of exists, then we find the number of nodes with a reachability of . If this number of nodes is divisible by , then we can arrange all of the nodes with a reachability of into multiple cycles, each containing nodes. Otherwise, no solution exists.
In order to prove our construction works for all cases where a solution exists, we need to show that if no nodes with a reachability of exist, then the number of nodes with a reachability of is a multiple of . As each node in our graph has one outgoing edge, the graph is a functional graph (also known as a successor graph). It is well known that this type of graph contains multiple cycles, where each node in a cycle is also the root of directed tree. If a node is part of a cycle, then its reachability is equal to the length of the cycle. Otherwise, the node is part of a tree, so its reachability is greater than the reachability of its parent. Since no nodes with reachabilities of exist, all nodes with a reachability of must lie on a cycle with size , so the number of nodes with a reachability of must be a multiple of . This completes the proof.