Official

E - Sliding Puzzle On Tree Editorial by evima

Hints: https://atcoder.jp/contests/agc066/editorial/9708

In this explanation, stones are denoted by letters such as \(a, b\), and vertices are denoted by letters such as \(u, v\).

[1] The range of existence for a single stone

First, let’s consider a fixed \(K\).

Let’s think about which vertices a single stone can move to. Let \(S(a)\) denote the set of all vertices where stone \(a\) can exist.

Investigating the range of existence for a single stone is possible with a suitable search algorithm in \(O(NK)\) states. The state should include information about which edge was swapped last and how many other stones are on each side of that edge.

Thinking about what this calculation entails, the following can be understood by focusing on vertices with degree \(3\) or higher:

  • Let \(u\) be is a vertex with degree \(3\) or higher. If \(S(a)\) includes more than two neighbors of \(u\), then \(S(a)\) includes all neighbors of \(u\). Hereafter, when this holds, we say that stone \(a\) can utilize vertex \(u\).
  • For stones \(a\) and \(b\) (\(a\neq b\)) that can both utilize the same vertex \(u\) with degree \(3\) or higher, \(S(a)=S(b)\) holds.
  • Conversely, for stones \(a\) and \(b\) (\(a\neq b\)), if \(S(a)=S(b)\), then they can utilize the same vertex \(u\) with degree \(3\) or higher.

The second property can be seen from the fact that the number of stones in each subtree around a vertex with degree \(3\) or higher can be freely adjusted. The third property is obvious if \(a\) or \(b\) can utilize a vertex with degree \(3\) or higher, and otherwise, it follows from the fact the number of stones in each direction from that stone remains constant.

[2] Calculating the answer (for a fixed \(K\))

The following holds: When \(S(a)=S(b)\) for stones \(a, b\), it is possible to swap just \(a\) and \(b\). In other words, it is possible to obtain a configuration where only the positions of \(a\) and \(b\) are swapped from any stone configuration.

Let us confirm this. When \(S(a)=S(b)\) holds, both \(a\) and \(b\) can utilize some vertex \(u\) with degree \(3\) or higher. Therefore, the goal can be achieved by the following steps:

  • (1) First, move stone \(a\) to a neighbor of \(u\), achieving a state where \(u\) and one of its neighbors have no stones. If necessary, move a few more times to ensure that \(a\) is in a different subtree from \(b\) when viewed from \(u\).

  • (2) Furthermore, since stone \(b\) can also utilize \(u\), from this state, move \(b\) to a neighbor of \(u\) so that there are two or more vertices without stones in the subtree on the \(u\) side when viewed from \(b\). During this process, it only mattered how many stones were on each side of the edge \(b\) was moved along, so it can be seen that this can be achieved without changing the position of stone \(a\).

  • (3) Now, there are no stones on \(u\) and one of its neighbors, and stones \(a\) and \(b\) are at neighbors of \(u\). From here, it is possible to swap just the positions of \(a\) and \(b\) by performing six operations appropriately.

  • (4) Perform the operations of (2) in reverse order.

  • (5) Perform the operations of (1) in reverse order.

Let us consider how many possible stone configurations there are when the set of vertices with stones is fixed. Taking two such configurations, if in one configuration stone \(a\) is on a certain vertex and in the other configuration stone \(b\) is on the same vertex, it is clear that \(S(a)=S(b)\). Conversely, two stones for which \(S(a)=S(b)\) holds can be freely swapped.

Therefore, when the set of vertices with stones is fixed, the answer can be found as follows:

  • Divide the stones into sets of stones with the same \(S(a)\). If they are divided into sets of sizes \(n_1, n_2, n_3, \ldots\), then there are \((n_1!)(n_2!)\cdots\) possible stone configurations.

Considering that the set of vertices with stones was fixed, multiplying this value by \(\binom{N}{K}\) gives the answer to the problem.

Let us classify the stones based on the relationship \(S(a)=S(b)\). Recalling that \(S(a)\) is determined by one of the vertices with degree \(3\) or higher that \(a\) can utilize, the problem can be reduced to the connected component decomposition of the following graph:

  • Prepare \(N\) vertices representing the tree’s vertices and \(K\) vertices representing the stones.
  • For stone \(a\), if there exists a vertex \(u\) with degree \(3\) or higher that \(a\) can utilize, choose one such \(u\) and span an edge between \(a\) and \(u\).
  • For vertices \(u\) and \(v\) with degrees \(3\) or higher, span an edge between \(u\) and \(v\) when a stone that can utilize \(u\) can also utilize \(v\).

For edges spun between stones and vertices with degrees \(3\) or higher, it is possible to limit the connection destination to at most two vertices nearest from the stone in a certain direction. For edges spun between vertices \(u\) and \(v\) with degrees \(3\) or higher, it is possible to connect only \(O(N)\) pairs where no other vertices with degree \(3\) or higher exist on the path connecting those two vertices. Therefore, it will be necessary to check whether an edge can be spun for \(O(N)\) pairs.

Whether an edge is drawn between a stone and a vertex can be determined by the number of empty squares in the direction toward some subtree from the stone and the distance between the stone and the vertex. Whether an edge is drawn between vertices with degrees \(3\) or higher can be determined by the distance between those two vertices.

With proper implementation, it is possible to calculate the answer for a fixed \(K\).

[3] Calculating the answer (for all \(K\))

Once it is possible to calculate the answer for individual \(K\), extending it to all \(K\) is not too difficult.

If we decide to calculate in the order \(K = N, N-1, \ldots, 1\), we have a type of calculation where we add edges to the graph consisting of stones and vertices while managing the connected components. Although it is necessary to reduce the number of stones, this can be done by changing the number of stones within a connected component without changing the connectivity of the graph, and all necessary calculations can be performed using the UnionFind data structure.

Since the initial configuration of stones can be freely chosen, placing them in descending preorder, for example, might simplify the implementation. Except for the part using UnionFind, all calculations can be done in \(O(N)\) time, allowing the problem to be solved in \(O(N\alpha(N))\) time.

posted:
last update: