H - Random Robots Editorial by en_translator
There is a formula called “LGV lemma” (Lindström–Gessel–Viennot lemma), which is useful for solving this problem.
The special form of LGV lemma which is used for this problem
Given is a DAG (Directed Acyclic Graph). $n$ vertices $a_1,a_2,\ldots,a_n$ is marked as sources and $n$ vertices $b_1,b_2,\ldots,b_n$ is marked as sinks.
If for every tuple of integers $(i,j,k,l)\ (1 \leq i,j,k,l \leq n)$ it holds that "if $i \lt j$ and $k \lt l$, then a path from $a_i$ to $b_l$ and another path from $a_j$ to $b_k$ always share a vertex," then the following fact holds.
-
The number of $n$-tuples of paths, the $i$-th of which is from $a_i$ to $b_i$, such that no two paths share a vertex, is equal to the determinant of $n \times n$ matrix $X$ defined by:
- For every pairs of integers $(i,j)\ (1 \leq i,j \leq n)$, $X_{i,j}$ is equal to the number of paths from $a_i$ to $b_j$
Let \(y_1,y_2,\ldots,y_K\ (y_1 \lt y_2 \lt \cdots \lt y_K)\) be the coordinates of Robots \(1,2,\ldots,K\) after \(N\) operations. Then, the move of each path can be regarded as a path on a DAG whose vertices are \((\)cumulative number of moves, coordinate\()\). Since \(y_1 \lt y_2 \lt \cdots \lt y_K\), for every tuple of integers \((i,j,k,l)\ (1 \leq i,j,k,l \leq K)\) it is satisfied that “if \(i \lt j\) and \(k \lt l\), then a path from \((0,a_i)\) to \((N,b_l)\) and another path from \((0,a_j)\) to \((N,b_k)\) always shares a vertex”. What we want to find is the number of moves of \(K\) robots in which no two robots are at the same coordinate at the same time, that is, the number of \(K\)-tuples of paths, the \(i\)-th of which is from \((0,x_i)\) to \((0,y_i)\), such that no two paths share a vertex. The emphasized two phrases are clearly the conditions we can apply LGV lemma.
Therefore, for some fixed final coordinates \(y_1,y_2,\ldots,y_K\) of \(K\) robots, the following property holds.
Define a \(K \times K\) matrix \(X\) by the rule below. Then, the number of moves of \(K\) robots such that there are never two or more robots at the same coordinate is equal to the determinant of \(X\).
- \(X_{i,j}=(\)the number of possible moves of the \(i\)-th robot such that the final coordinate after \(N\) vertices is \(y_j)=\binom{N}{y_j-x_i}\)
Thus, it is sufficient to find for each sequence \(y\) such that \(y_1 \lt y_2 \lt \cdots \lt y_K\) the matrix \(X\) and its determinant, then find their sum.
However, the domain of \(y_i\) is \(\min(x)\) through \(\max(x)+N\); the number of integer sequences \(y\) is huge. So, instead of fixing \(y\), we decompose the determinant of \(X\) and, fixing a permutation \((p_1,p_2,\ldots,p_K)\) of \((1,2,\ldots,K)\) (there are \(K!\) of them), consider \(\sum_{y_1 \lt y_2 \lt \cdots \lt y_K} \prod_{j=1}^{K} \binom{N}{y_j-x_{p_j}}\).
This can be computed in an \(O(K(N+\max(x)))\) time for each permutation by the following DP (Dynamic Programming) (where \(\text{dp}[K][N+\max(x)]\) is the desired value). Note that in the recurrence relation below we assume that \(\min(x)\); actually \(\min(x)\) can be zero, so we should properly shift the values.
\[ dp[i][j]=\begin{cases} 1\ (i=j=0)\\ 0\ (0 \lt i,j=0)\\ dp[i][j-1]\ (i=0,0 \lt j)\\ dp[i][j-1]+dp[i-1][j-1] \times \binom{N}{j-x_{p_i}}\ (0 \lt i,j) \end{cases} \]
Still, the total time complexity is \(O(K!K(N+\max(x)))\), which is too large for the execution time limit. Instead, consider a Bit DP in which the process of determining the permutation is stored as bit information. This will reduce the complexity to \(O(2^KK(N+\max(x)))\), which is fast enough:
For reference, here is the submission that costs \(O(K!K(N+\max(x)))\) time:
posted:
last update: