2
$\begingroup$

Problem

We are given 2 arrays a and b both of length n. We build a third array c by rearranging the values in b. The goal is to find the optimal c that maximizes

result = (a[0] ^ c[0]) & (a[1] ^ c[1]) & ... & (a[n - 1] ^ c[n - 1])

where ^ is XOR and & is AND.

Is it possible to do this efficiently? It's straightforward to iterate through all possible permutations of b, but this is infeasible for large n.

More details

  • The order of the values in a is fixed.
  • The order of the values in b may be rearranged to form c. That is, starting with b = [1, 2, 3], it may be that the maximum result is obtained when the values are rearranged to c = [2, 1, 3].
  • b may be rearranged in-place if needed.
  • Since the optimal c is not necessarily unique, any optimal c may be returned.
  • Assume all values are 32-bit unsigned integers.
  • 1 <= n <= 10,000.

Test cases

Input:
a = [3, 4, 5]
b = [6, 7, 8]
Output:
c = [8, 7, 6] (result = 3)
Input:
a = [1, 11, 7, 4, 10, 11]
b = [6, 20, 8, 9, 10, 7]
Output:
c = [8, 6, 10, 9, 7, 20] (result = 9)
Input:
a = [0, 1, 2, 4, 8, 16]
b = [512, 256, 128, 64, 32, 16]
Output:
c = [16, 32, 64, 128, 256, 512] (result = 0)
$\endgroup$
2
  • 3
    $\begingroup$ Can you please provide a link to where you've encountered this problem? (I'm asking in case it's e.g. from an ongoing programming contest) $\endgroup$ – user114966 Apr 19 at 14:08
  • $\begingroup$ codeforces.com/group/swEqtABRxe/contest/324151/problem/C but it's not public. You have to enter a group to view it $\endgroup$ – Kolya Ivanov Apr 19 at 16:21
1
$\begingroup$

For bit #k to be set in the output, you need to arrange the numbers so that bit #k is either set in a[i] and cleared in c[i] or the other way round. Therefore bit #k must be set in exactly n of your 2n inputs. If that is not the case then bit #k cannot be set in the output. So first you determine all k such that bit #k is set in exactly n of the 2n inputs, and ignore all other ks.

Let k be the highest of these bit positions. Split the elements of b into those where bit #k is set and those where it is cleared, and pick c[i] from the correct one of these sets. That's always possible.

Let j be the second highest of these bit positions. Split the elements of b into four sets, where bit #k and #j are both set, bit #k is set and bit #j is cleared, etc. Depending on which bits in a[i] are set, you know from which subset of b you need to pick c[i]. This only works if the sets have the right sizes! If it doesn't work, ignore bit j and take the next highest bit. If it works you can set bit #k and #j in the result and proceed with the next higher bit.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.