Editorial for Yet Another Contest 4 P2 - Alchemy 2
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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
).
Subtask 1
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
.
Time complexity:
Subtask 2
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.
Time complexity:
Comments