## Editorial for Yet Another Contest 4 P2 - Alchemy 2

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

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