Let \(a(x)\) be the number of indices \(i\) for which \(A_i = x\), and let \(b(x)\) be the number of indices \(i\) for which \(B_i = x\).

Necessary and Sufficient Condition for \(A_1 + B_1 = A_2 + B_2 = \dots = A_N + B_N = z\)

First, for a fixed integer \(z\), consider the necessary and sufficient condition for it to be possible to have \(A_1 + B_1 = A_2 + B_2 = \dots = A_N + B_N = z\). Eventually, all elements of \(A\) and \(B\) must be non-negative, so we need \(z \geq \max\{A_1,A_2,\dots,A_N,B_1,B_2,\dots,B_N\}\). From here on, assume this requirement is satisfied.

We may assume that among the three operations, the rearrangement of \(A\) is performed first. Once \(A\) has been rearranged, the necessary and sufficient condition for it to be possible to replace any \(-1\) in \(A\) or \(B\) with suitable non-negative integers so that \(A_1 + B_1 = \dots = A_N + B_N = z\) holds is:

• For each \(i\) \((1\leq i\leq N)\), if \(A_i \neq -1\) and \(B_i \neq -1\), then \(A_i + B_i = z\).

Let \(f(z)\) be the maximum possible number of positions \(i\) such that \(A_i \neq -1\), \(B_i \neq -1\), and \(A_i + B_i = z\) after rearranging \(A\). If the total number of \(-1\) in \(A\) and \(B\) combined is at least \(N - f(z)\), then and only then can we rearrange \(A\) in such a way that the above condition is satisfied.

Hence, for an integer \(z\), the necessary and sufficient condition to achieve \(A_1 + B_1 = \dots = A_N + B_N = z\) is:

• \(z \geq \max\{A_1,A_2,\dots,A_N,B_1,B_2,\dots,B_N\}\),
• \(f(z) \geq N - a(-1) - b(-1)\).

Moreover, \(f(z)\) can be written as

\[ f(z) = \sum_{x=0}^{z} \min\{\, a(x),\, b(z-x)\}. \]

Solution

There are at most \(N\) distinct non-negative integers \(x\) for which \(a(x)\geq 1\), and at most \(N\) distinct non-negative integers \(y\) for which \(b(y)\geq 1\). By enumerating all such pairs \((x,y)\), you can find all \(z\) for which \(f(z)\geq 1\). Using a map or similar data structure, the overall complexity will be \(\mathrm{O}(N^2)\) or \(\mathrm{O}(N^2 \log N)\).