We choose \(X_i\) to be \(B_i\) or \(C_i\), which is equivalent to be \(0\) or \(\max\{B_i,C_i\} - \min\{B_i,C_i\}\) in considering the sum \(\sum_{i=1}^{N} X_i\). For \(B_i\) and \(C_i\) that satisfy \(B_i+C_i=A_i\), the possible integer values for \(\max\{B_i,C_i\} - \min\{B_i,C_i\}\) are those at most \(A_i\) and have the same parity as \(A_i\). Therefore, the problem can be rephrased as follows:

Is there a sequence $D=(D_1,D_2\dots,D_N)$ satisfying $0\leq D_i \leq A_i$ and $D_i \equiv A_i\ (\bmod\ 2)$ for $i=1,2,\dots,N$ such that there is no way to choose some of $D_1,D_2,\dots,D_N$ so that they total $\frac{1}{2} \sum_{i=1}^{N}D_i$?

To state the conclusion, the necessary and sufficient condition for the existence of such \(D\) is:

• There is an integer \(i\) such that the number of odd integers less than \(A_i\) among \(A_1,A_2,\dots, A_N\) is less than \(A_i-1\).

Whether it holds or not can easily be determined in \(O(N\log N)\) time by sorting \(A\). Below, we prove this under the assumption that \(A_1 \leq A_2 \leq \dots \leq A_N\).

[1] Necessity

It suffices to show that if the number of odd integers less than \(A_i\) among \(A_1,A_2,\dots, A_N\) is at least \(A_i-1\) for every \(A_i\), then for every possible \(D\), there is a way to choose some \(D_i\) so that they total \(\frac{1}{2} \sum_{i=1}^{N}D_i\). Here, we show a stronger fact that for \(i=1,2,\dots,N\), the following holds:

• For \(S=0,1,2,\dots,\sum_{j=1}^{i}D_j\), there is a way to choose some of \(D_1,D_2,\dots,D_i\) so that they total \(S\).

We will show that if this holds for \(i=k\), it also holds for \(i=k+1\). If it holds for \(i=k\), then the sums that can be created by choosing from \(D_1,D_2,\dots,D_{k+1}\) are \(0,1,2,\dots, \sum_{j=1}^{k}D_j\) and \(D_{k+1},D_{k+1}+1,D_{k+1}+2,\dots, \sum_{j=1}^{k+1}D_j\). Therefore, it suffices to show that \(D_{k+1} \leq \sum_{j=1}^{k}D_j+1\). Since \(D_j \equiv A_j\ (\bmod\ 2)\), the minimum value of the right side is the number of odd integers among \(A_1,A_2,\dots,A_k\) plus \(1\), and the maximum value of the left side is clearly \(A_{k+1}\). Thus, we need to show that \(A_{k+1} \leq\) (the number of odd integers among \(A_1,A_2,\dots,A_k\) plus \(1\)), which is the same as the necessary and sufficient condition stated initially.

This shows the necessity.

[2] Sufficiency

We show sufficiency by actually constructing a \(D\) that satisfies the condition. Let \(a\) be the smallest \(A_i\) for which the number of odd integers less than \(A_i\) among \(A_1,A_2,\dots,A_N\) is less than \(A_i-1\).

[2-1] If \(a\) is odd

When \(A_i\) is even, set \(D_i=0\). When \(A_i\) is odd and less than \(a\), set \(D_i=1\). For all other cases, set \(D_i=a\). However, if this would result in the number of indices \(i\) satisfying \(D_i=1\) being even, then set \(D_i=1\) for only one \(i\) that satisfies \(D_i=a\). For example, for \(A=(3,3,3,3)\), set \(D=(1,3,3,3)\) instead of \(D=(3,3,3,3)\).

We confirm that the constructed \(D\) satisfies the condition. The numbers of \(1\) and \(a\) in \(D\) are both odd; let us call these numbers \(2n+1\) and \(2m+1\) \((2n+1 < a-1)\), respectively, and it suffices to show that \(\frac{2n+1+a}{2}+am\) cannot be created.

For the sum made from choosing some \(D_i\), the remainder when divided by \(a\) is at most \(2n+1\) since \(2n+1 < a-1\). On the other hand, the target sum \(\frac{2n+1+a}{2}+am\) when divided by \(a\) has a remainder of \(\frac{2n+1+a}{2}\), which is greater than \(2n+1\). Thus, it is impossible to create \(\frac{1}{2} \sum_{i=1}^N D_i\), so \(D\) satisfies the condition.

[2-2] If \(a\) is even

If there is an odd integer greater than \(a\) among \(A_i\), we can construct \(D\) using the method in [2-1] by choosing the smallest such odd integer. Otherwise, set \(D_i=1\) when \(A_i\) is odd, \(D_i=0\) when \(A_i\) is an even number not equal to \(a\), and for \(i\) such that \(A_i=a\), set \(D_i=a\) for only one and \(D_i=0\) for the others. Using the same argument as in [2-1], we can show that \(D\) satisfies the condition.