P10043 [CCPC 2023 Beijing Municipal Contest] Broadcast

Xiao I is learning to use Pytorch. It is a very popular Python library for machine learning training. Xiao I noticed that Pytorch has a mechanism for tensor operations called "broadcast". You can think of a tensor as a high-dimensional array. For a $k$-dimensional tensor $A$, we use a sequence of length $k$, $(a_1,a_2,\cdots,a_k)$, to represent the size of each dimension. That is, $A$ is a tensor of shape $a_1 \times a_2 \times \cdots \times a_k$. For two tensors $A$ and $B$, suppose their dimensions are $(a_1,a_2,\cdots,a_m)$ and $(b_1,b_2,\cdots,b_n)$ respectively. We say $A$ and $B$ are **broadcastable** if and only if the following property holds: - For any integer $0 \le i \le \min(n,m) - 1$, either $a_{m-i} = b_{n-i}$, or at least one of $a_{m-i}$ and $b_{n-i}$ is $1$. Now Xiao I has two tensors with dimensions $(p_1,p_2,\cdots,p_m)$ and $(q_1,q_2,\cdots,q_n)$. They are not necessarily broadcastable. So, Xiao I can use Pytorch built-in functions to perform some operations (possibly none). In each operation, he modifies sequence $p$ or $q$ as follows: - Choose $p$ or $q$, and insert a $1$ at any position in the chosen sequence. Xiao I wants to know the minimum number of operations needed to make the two tensors broadcastable.

The first line contains two integers $m,n(1 \le m,n \le 2000)$, representing the number of dimensions of the two tensors. The second line contains $m$ integers $p_1,p_2,\cdots,p_m (1 \le p_i \le 2000)$, describing the length of each dimension of the first tensor. The third line contains $n$ integers $q_1,q_2,\cdots,q_n (1 \le q_i \le 2000)$, describing the length of each dimension of the second tensor.

Output one integer in a single line, representing the minimum number of inserted $1$'s needed to make the two tensors broadcastable.

Insert a $1$ before the second position of sequence $q$ (getting `4 1 2`), and then the two tensors will become broadcastable. Translated by ChatGPT 5