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.
Since we care about all permutations. Harness the small n <= 30. meet in middle (split array A into two halves). Complete search (bit masking to generate all possible XOR values by taking XOR of subsets of elements of each half) so time complexity is O(n * 2^(n/2)) 30 * 2^15 Then, sort + binary search to check if there are pairs one from each half, when XORed produce x and by similar produce y. It adds a log factor so total time complexity of O(n * 2^(n/2) * log(2^(n/2)))
Tabulation(DP) to get it to O(n * max(Ai))
If you need further help to see the actual implementations of those ideas, mention it.
can you explain your solution more? the intended works in O(n * (max(Ai))^2). how to check for a pair in the first half if there is a matching that yields x and y?
Intended? So it seems either you were involved in the problem setting or contacted the problem setter. So ok give more details about the DP optimization. I am not so sure about it. Also, it wasn't my day so I just checked the post and helped with an idea I had upon reading the problem.
The constraints allow complete searching with meet in middle(Divide A into A1, A2) (Safer option). I think u misunderstood the pairs part One from each half (A1, A2). Here is the code so you can better relate my words : code If you've a better idea on the optimization via DP, I'd like to hear 😅
yes, I was involved in the problem setting. the idea seems to be incorrect as when you binary search for the matching xor there might be non-common elements between the subsets taken to get x and y and these elements will affect the prefix xor. assume our current xor from the first half is P and we find a matching xor I to get x and a matching xor J to get y from the second half and there is no intersection between the two subsets that formed I and J then when creating the prefix xor array either x or y will not appear. counter-example : n = 2, x = 2, y = 4, arr = {2, 4}
the intended solution is the one below that not_ahmed_hamed mentioned
So why I got a lot of downvotes :"D
We couldn't solve it too :( . But I guess we can use DP to solve it.
Prefix xor array will be like
a1,a2,a2,...,A ,a6,a7, B ,a9,......a30which mean that in the prefix xor array there should be prefix equals to A and B and XOR of elements between them equal to A^B.
We can divide the final prefix array into 3 segments
The first one contains elements their XOR value = A or B
The second one contains elements their XOR VALUE = A^B
The third contains useless elements (The elements we will skip in the dp function)
DP[31][2048][2048]This became a variation of subset xor problem. For each element, we can skip it or xor it with xorVal1 or xorVal2if
i==n+1check if xorVal1 = A or B and xorVal2 = A^BPlease correct me if this is wrong.