Resources

Introduction

An XOR basis is a minimal set of linearly independent binary vectors that can represent any vector in a given set through XOR combinations. In computational problems, constructing an XOR basis involves iteratively adding vectors to the basis while ensuring each new vector remains independent by reducing it with existing basis vectors. This basis allows efficient representation and manipulation of binary vector spaces, enabling quick determination of linear independence and facilitating solutions to various optimization and combinatorial problems.

XOR basis involves two parts:

• Represent each given number in its base 2 form, considering it as a vector in the ${\mathbb{Z_2^d}}$ vector space, where $d$ is the maximum possible number of bits. The XOR operation on these numbers is equivalent to the addition of the corresponding vectors in the vector space ${\mathbb{Z_2^d}}$.

• Relate the answers to the queries of various types with the basis of the vectors found in Part 1.

Important terms

Vector Space ${\mathbb{Z_2^d}}$

${\mathbb{Z_2}}$: ${\mathbb{Z_m}}$ is the set of remainders upon division by $m$. Therefore, ${\mathbb{Z_2}}$ is the set of remainders upon division by $2$: $\{0, 1\}$.

${\mathbb{Z_2^d}}$: It represents the set of all binary vectors of length $d$, where each component of the vector belongs to the field ${\mathbb{Z_2}}$.

Linear Span

The span of a set of vectors ${S = \{v_1, v_2,\dots, v_n \}}$ in a vector space $V$ consists of all vectors $x$ that can be represented as linear combination of the vectors in $S$. Mathematically, the span of $S$ is defined as:

This mean that any vector $x$ in $V$ can be expressed as a linear combination of the vectors $v_1, v_2,\dots,v_n$ in $S$, where each coefficient $c_i$ is either 0 or 1. The span of $S$ represents the subspace of $V$ that is generated by the vectors in $S$, encompassing all possible combinations of those vectors. Understanding the span of a set of vectors is crucial for determining the reach or extent of the vector's influence within the vector space.

Basis

A set of vectors $B = \{v_1, v_2,\dots,v_n\}$ is termed the basis of a vector space $V$ if the span of $B$ covers $V$ entirely and $B$ is linearly independent. In other words, any vector in $V$ can be expressed as a linear combination of the vectors in $B$, and no vector in $B$ can be represented as a linear combination of the others. The number of vectors in $B$ , denoted as $n$, is defined as the dimension of $V$, represented by $\dim(V)$. Understanding the basis and dimension of a vector space is crucial for analyzing its structure, solving linear equations, and performing transformations in various mathematical and computational contexts.

Example - Xor Closure

You are given a set of $N$ integer values. You should find the minimum number of values that you need to add to the set such that the following will hold true:

• For every two integers $A$ and $B$ in the set, their bitwise xor $A \oplus B$ is also in the set.

Solution

The solution involves constructing an XOR basis from a set of binary vectors and computing a value based on this basis. Each vector is inserted into the XOR basis by attempting to minimize it through XOR-ing with existing basis vectors, ensuring that the vector remains linearly independent. If the vector cannot be fully reduced to zero, it is added to the basis. This ensures that the basis only contains the minimal set of vectors needed to represent the space spanned by the input vectors.

Once the basis is constructed, the final result is calculated as $2^{basis.size()}- n$. Here $2^{basis.size()}$ represents the total number of distinct vectors that can be formed using the basis, including the zero vector. We subtract $n$ to adjust for the number of vectors already in the set.

Copy
N = int(input())
numbers = list(map(int, input().split()))

# compute basis size
basis_size = 0
for i in range(N):
	if numbers[i]:
		basis_size += 1  # add numbers[i] to basis
		for j in range(i + 1, N):  # reduce remaining vectors
			numbers[j] = min(numbers[j], numbers[j] ^ numbers[i])

# print number of missing elements
print(2**basis_size - N)

You might be wondering why this method of reduction works. For instance, if the basis elements were currently $[1_2, 11_2]$ and you tried inserting $10_2$, you'd end up with a result of $1_2$. This is clearly wrong, since $10_2$ is not independent of the basis $[1_2, 11_2]$.

However, the catch is that every other basis element must be reduced via the same method. This means $[1_2, 11_2]$ is not actually a basis our algorithm can produce: properly reduced, it should be $[1_2, 10_2]$ instead.

More generally, this reduction guarantees that, if bit $x$ is the MSB of one basis element, it must be switched off in every basis element after it: this is why this method of reduction works without having to maintain the basis vectors in sorted order.

Example - Xor Cycle

Solution

Official Editorial

Problems

Some harder tasks: