Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Utsavcc's blog

Stuck on an XOR Question
By Utsavcc, 2 hours ago, In English

Given an array of elements Ai (<=1e9) of length N (<=1e5), and another array named 'operands' of size K (<=4), You can do the following operations as many times as desired: Select any element in original array and XOR it with any element in 'operands' array. Minimize the Maximum difference between any pairs of the array.

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

»
112 minutes ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

it's a little "sus" on your avatar

→ Reply
»
91 minute(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't understand what does K do here?

→ Reply
  • »
    »
    80 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Updated the statement, let me know if the problem is intuitive.

    → Reply
»
75 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

One idea I could think of immediately:

Pivot $$$A_1$$$. Perform $$$16$$$ different cases, with each case having $$$A_1$$$ xor-ing with every element in a subset of operand array (empty subset means keeping $$$A_1$$$ as-is), we'll call the new value $$$A_1'$$$.

For each case, try to make other elements as close to $$$A_1'$$$ as possible. As one can guess, any other element also has $$$16$$$ possibilities each.

This solution has $$$\mathcal{O}(n \cdot 4^k)$$$ complexity.

→ Reply
  • »
    »
    61 minute(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Considering whatever you explained, consider this: How about for every subset of operands, we XOR the subset XOR value with each element of the array, sort those 16 possibilities and store it in a matrix[N][16]. Now the problem statement just changed to selecting one element from each row and maintaining minimum difference between the maximum chosen and the minimum chosen value. Isn't this a famous question we've seen somewhere?

    → Reply
    • »
      »
      »
      32 minutes ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, here we can enumerate the minimum and then use O(2^k·n) to solve. When an element no longer qualifies for the minimum value, we replace it with an element in the array that is just larger than it.

      → Reply
  • »
    »
    45 minutes ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Making each element as close to a1 as possible doesn't guarantee the greatest gap is the least, right? ​

    For example, a2 = (a1-1 or a1+5). a3 = (a1+5 or a1+7).

    ​ You would choose "a1-1" versus "a1+5" with a difference of 6.

    ​ The correct choice is "a1+5" and "a1+5", the difference is 5.

    And you can't handle the case if you have two closest values at the same time.

    → Reply
»
10 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice pic bro

→ Reply