We can visualise each element as a node in a graph, with a directed edge being added between ~x~ and ~a_x~. Since using the machine corresponds to traversing an edge of the graph, ~b_i~ is equal to the reachability of node ~x~ (the number of nodes reachable from ~x~).

Subtask 1

In this subtask, it is always possible to construct sequence ~a~. For each node, if it has a reachability of ~1~, we add an edge from that node to itself. Otherwise, if this node has a reachability of ~z > 1~, we add an edge from this node to any node with a reachability of ~z-1~.

Time complexity: ~\mathcal{O}(N)~

Subtask 2

We can perform the same solution as before. When we process a node with a reachability of ~z~, it suffices to add an edge from this node to a node with a reachability of ~z-1~.

If no node with a reachability of ~z-1~ exists, then we find the number of nodes with a reachability of ~z~. If this number of nodes is divisible by ~z~, then we can arrange all of the nodes with a reachability of ~z~ into multiple cycles, each containing ~z~ 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 ~z-1~ exist, then the number of nodes with a reachability of ~z~ is a multiple of ~z~. 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 ~1~ greater than the reachability of its parent. Since no nodes with reachabilities of ~z-1~ exist, all nodes with a reachability of ~z~ must lie on a cycle with size ~z~, so the number of nodes with a reachability of ~z~ must be a multiple of ~z~. This completes the proof.

Time complexity: ~\mathcal{O}(N)~