Official

E - Sort and Match Editorial by evima


Prepare \(N\) vertices and draw edges \(y_i \to x_i\). In this graph, the out-degree and in-degree of each vertex are equal. Also, for each vertex, the outgoing edges have a determined order.

Consider the operation of starting at vertex \(1\) and traversing edges. Each time we reach a vertex, we need to choose the next edge to traverse, where we’ll use the order determined for each vertex.

This operation will eventually end at vertex \(1\). At this point, all edges touching vertex \(1\) have been used up. If we repeat the same operation starting at vertices \(2, 3, \cdots, N\), we will eventually use up all the edges.

By counting the ways of this movement, we can solve the original problem. For each starting vertex \(1, 2, \cdots, N\), we can solve a DP: \(dp[i][j] =\) the number of ways when we are at vertex \(i\) and have traversed \(j\) edges.

\(x_1\) is the destination of the first edge traversed. If we try all \(N\) possible choices, we need to solve the same problem \(N\) times. By looking at the movement in reverse order, we can combine the computations into one (but even without this optimization, it is fast enough).

The computational complexity is \(O(N^3 M)\).

Sample Solution (C++)

posted:
last update: