Contest Duration: - (local time) (100 minutes) Back to Home
Official

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

Sample code (C++)

For reference, here is the submission that costs $$O(K!K(N+\max(x)))$$ time:

Sample code (C++)

posted:
last update: