How to solve this problem?

Revision en1, by Ibrahim-Elsayed, 2023-08-15 05:34:48

Given an array $$$A$$$ of $$$N$$$ non-negative integers, and two different integers $$$x$$$ and $$$y$$$, could you permute the array $$$A$$$ into a new array $$$B$$$ in such a way that after creating the $$$XOR$$$ prefix of the array $$$B$$$, both $$$x$$$ and $$$y$$$ would appear in it?

the $$$XOR$$$ of an empty prefix equals $$$0$$$.

Input: $$$n$$$, $$$x$$$ and $$$y$$$ ($$$2 <= n <= 30$$$), ($$$0 <= x,y < 2^{10}, x \ne y$$$)

then we are given an array $$$A$$$ with length $$$n$$$ $$$a_1, a_2, ..., a_n$$$ ($$$0 <= a_i < 2^{10}$$$)

test cases:

Input: $$$n=5$$$, $$$x=1$$$, $$$y=7$$$, $$$A = [1, 2, 3, 4, 5]$$$

Output: YES

Input: $$$n=3$$$, $$$x=8$$$, $$$y=9$$$, $$$A = [1, 2, 3]$$$

Output: NO

This was a problem in a national contest, we couldn't solve it. I would appreciate your help, thanks in advance.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Ibrahim-Elsayed 2023-08-15 05:34:48 775 Initial revision (published)