Ibrahim-Elsayed's blog

How to solve this problem?
By Ibrahim-Elsayed, history, 10 months ago, In English

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.

  • Vote: I like it
  • +28
  • Vote: I do not like it

»
10 months ago, # |
← Rev. 3   Vote: I like it +17 Vote: I do not like it
Hint
Optimization

If you need further help to see the actual implementations of those ideas, mention it.

→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like 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?

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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 😅

      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
        ← Rev. 3   Vote: I like it +13 Vote: I do not like it

        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}

        → Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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,......a30

which 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 xorVal2

if i==n+1 check if xorVal1 = A or B and xorVal2 = A^B

Please correct me if this is wrong.

→ Reply