String version of even-odd partition problem
It is possible to reduce from the "unshuffling a string" problem: given a string $w \in \Sigma^*$, decide whether $w$ is a shuffle square, i.e. $w$ is in the shuffle product of two identical strings. This problem is proved to be NP-complete for alphabet of size at least nine, see this question for references and discussion. 

Here, for two strings $u$ and $v$  the shuffle product is defined as the set of all $w = u_1 v_1 \ldots u_i v_i$ for each representation $u = u_1 \ldots u_k$ and $v = v_1 \ldots v_k$ with $u_i, v_i \in \Sigma^*$ (i.e. $u_i$ and $v_i$ are strings, not letters).

The reduction is easy: given $w = a_1 \ldots a_n$, $a_i \in \Sigma$, take $x_{i, 0} = a_i$ and $x_{i, 1} = \epsilon$, where $\epsilon$ is the empty string. Then the answer in your problem (with alphabet of size nine) is YES if and only if $w$ is a shuffle square.

Finally, use an arbitrary prefix-free binary encoding of $\Sigma$, thus getting a reduction for the binary case.