[1] Dynamic programming

Let’s rephrase the problem to make it easier to understand. For each integer \(i=1,2,\ldots,N\), let \(d_i\) be the number of occurrences of \(i\) in \(B\). Then, the two conditions can be written as follows:

• \(d_i \leq A_i\)
• At the \(i\)-th position of \(B\), we can place an integer \(j\) such that \(d_j\leq A_i\).

From the above conditions, we can see that the smaller \(d_i\) is, the more different integers we can place and the more positions we can place them in. Based on this observation, a dynamic programming approach that determines the placement in descending order of \(d_i\) is considered effective.

Let \(\mathrm{dp}[i][j][k]\) be the number of ways to determine the positions of integers with more than \(i\) occurrences in \(B\) so that the number of different determined integers is \(j\) and the number of determined integers is \(k\). Also, let \(C_j\) be the number of \(i\) such that \(A_i \geq j\).

Let’s consider the transition from \(\mathrm{dp}[i][j][k]\). Suppose there are \(l\) different integers that occur \(i\) times.

Then, there are \(\binom{C_i - j}{l}\) ways to choose integers that appear \(i\) times. Next, the number of ways to choose the positions for these integers is the multinomial coefficient \(\binom{C_i-k}{\underbrace{i,\ldots, i}_{l\text{ times}}, C_i-k-il}\).

In the end, for each \((i,j,k,l)\), we need to perform the following update:

• add \(\displaystyle \mathrm{dp}[i][j][k] \ \binom{C_i - j}{l} \binom{C_i-k}{\underbrace{i,\ldots, i}_{l\text{ times}}, C_i-k-il} \) to \(\mathrm{dp}[i-1][j+l][k+il]\).

[2] Complexity analysis

Let’s analyze the complexity. At first glance, the state may seem to be \(\mathrm{O}(N^3)\) and the transition may seem to be \(\mathrm{O}(N)\) for each state, resulting in a total of \(\mathrm{O}(N^4)\). In fact, however, considering \((i,j,k,l)\) only for the valid range, it works in \(\mathrm{O}(N^3)\).

Proof: For a given \(i\), the range of \(j\) for which \(\mathrm{dp}[i][j][*][*]\) can take non-zero values is \(0\leq j \leq \lfloor \frac{N}{i+1}\rfloor\). Furthermore, the valid range of \(l\) is also \(0\leq j \leq \lfloor \frac{N}{i}\rfloor\). Even if we look at the entire range of \(i,k\), the number of transitions is \(\sum_{i=1}^N N(\big\lfloor \frac{N}{i+1}\big\rfloor+1)(\big\lfloor \frac{N}{i}\big\rfloor+1)\), and by expanding and looking at the most significant part, we can evaluate it as

\[\sum_{i=1}^N N\Big\lfloor \frac{N}{i+1}\Big\rfloor\Big\lfloor \frac{N}{i}\Big\rfloor \leq N^3 \sum_{i=1}^N \frac{1}{i(i+1)}=\frac{N^4}{N+1}.\]

Thus, we have found that the number of transitions is \(\mathrm{O}(N^3)\).

In conclusion, by considering only the valid range of \(j,l\) and performing the dynamic programming in [1], we can solve this problem in \(\mathrm{O}(N^3)\).

(Above is a modification of a translation by GPT-4.)