XOR Inverse (Codeforces 1417E)
Tags: Others, divide and conquer

You are given an array $$$a$$$ consisting of $$$n$$$ non-negative integers. You have to choose a non-negative integer $$$x$$$ and form a new array $$$b$$$ of size $$$n$$$ according to the following rule: for all $$$i$$$ from $$$1$$$ to $$$n$$$, $$$b_i = a_i \oplus x$$$ ($$$\oplus$$$ denotes the operation bitwise XOR).An inversion in the $$$b$$$ array is a pair of integers $$$i$$$ and $$$j$$$ such that $$$1 \le i < j \le n$$$ and $$$b_i > b_j$$$.You should choose $$$x$$$ in such a way that the number of inversions in $$$b$$$ is minimized. If there are several options for $$$x$$$ — output the smallest one.

Input: First line contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of elements in $$$a$$$.Second line contains $$$n$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 \le a_i \le 10^9$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

Output: Output two integers: the minimum possible number of inversions in $$$b$$$, and the minimum possible value of $$$x$$$, which achieves those number of inversions.

Note: In the first sample it is optimal to leave the array as it is by choosing $$$x = 0$$$.In the second sample the selection of $$$x = 14$$$ results in $$$b$$$: $$$[4, 9, 7, 4, 9, 11, 11, 13, 11]$$$. It has $$$4$$$ inversions:  $$$i = 2$$$, $$$j = 3$$$;  $$$i = 2$$$, $$$j = 4$$$;  $$$i = 3$$$, $$$j = 4$$$;  $$$i = 8$$$, $$$j = 9$$$. In the third sample the selection of $$$x = 8$$$ results in $$$b$$$: $$$[0, 2, 11]$$$. It has no inversions.

Sample Inputs:
4
0 1 3 2

9
10 7 9 10 7 5 5 3 5

3
8 10 3

Sample Outputs:
1 0

4 14

0 8

Solution (Python):
from bisect import *
from collections import *
from math import *
from heapq import *
from typing import List
from itertools import *
from operator import *
from functools import *
import sys
''
''
n = int(input())
ans = x = 0
arr = [list(map(int, input().split()))]
for k in range(29, -1, -1):
    (a, b) = (0, 0)
    mask = 1 << k
    tmp = []
    for ar in arr:
        one = zero = 0
        tmp1 = []
        tmp2 = []
        for ai in ar:
            cur = ai & mask
            if cur == 0:
                b += one
                zero += 1
                tmp1.append(ai)
            else:
                a += zero
                one += 1
                tmp2.append(ai)
        if len(tmp1) > 1:
            tmp.append(tmp1)
        if len(tmp2) > 1:
            tmp.append(tmp2)
    if b > a:
        x |= mask
        ans += a
    else:
        ans += b
    arr = tmp
print(ans, x)

Solution (Python):
dp = [[0, 0] for _ in range(34)]

def solve(arr, bit):
    if bit < 0 or len(arr) == 0:
        return
    (inv1, inv0, o, z, x) = (0, 0, 0, 0, 1 << bit)
    (O, Z) = ([], [])
    for el in arr:
        if el & x:
            o += 1
            O.append(el)
            inv1 += z
        else:
            z += 1
            Z.append(el)
            inv0 += o
    dp[bit][0] += inv0
    dp[bit][1] += inv1
    solve(Z, bit - 1)
    solve(O, bit - 1)
n = int(input())
arr = [int(x) for x in input().split()]
solve(arr, 30)
(invCnt, ans) = (0, 0)
for b in range(30, -1, -1):
    if dp[b][1] < dp[b][0]:
        ans += 1 << b
    invCnt += min(dp[b][1], dp[b][0])
print(invCnt, ans, sep=' ')

Solution (Python):
import sys
import random
from collections import defaultdict
from itertools import combinations
import math

def getunique(v):
    return list(set(v))
rng = random.SystemRandom()

def usaco(filename):
    sys.stdin = open(f'{filename}.in', 'r')
    sys.stdout = open(f'{filename}.out', 'w')
pi = math.pi
(n, m, k, q, l, r, x, y, z) = (0, 0, 0, 0, 0, 0, 0, 0, 0)
template_array_size = 1000000.0 + 1600
a = [0] * int(template_array_size)
b = [0] * int(template_array_size)
c = [0] * int(template_array_size)
s = t = ''
ans = 0
cnt = [[0 for _ in range(2)] for _ in range(55)]

def rec(a, b):
    if not a or b < 0:
        return
    c = [0, 0]
    v = [[], []]
    for x in a:
        bv = bool(x & 1 << b)
        if bv == 0:
            cnt[b][0] += c[1]
        else:
            cnt[b][1] += c[0]
        c[bv] += 1
        v[bv].append(x)
    rec(v[0], b - 1)
    rec(v[1], b - 1)

def solve(tc=0):
    global cnt
    n = int(input())
    a = [int(x) for x in input().split()]
    cnt = [[0 for _ in range(2)] for _ in range(55)]
    rec(a, 30)
    x = inv = 0
    for i in range(30, -1, -1):
        inv += min(cnt[i][0], cnt[i][1])
        if cnt[i][0] > cnt[i][1]:
            x += 1 << i
    print(inv, x)
if __name__ == '__main__':
    tc = 1
    for t in range(tc):
        solve(t)