Rare
 0/13

XOR Basis

Authors: Benjamin Qi, Rameez Parwez

Edit This Page

Resources

Resources
CF

inspiration for below

Benq

used at USACO Camp

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 Z2d{\mathbb{Z_2^d}} vector space, where dd 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 Z2d{\mathbb{Z_2^d}}.

  • Relate the answers to the queries of the second type with the basis of the vectors found in Part 1.

By constructing an XOR basis from the set of vectors, we can efficiently answer various queries about linear independence, redundancy, and other properties related to the XOR combinations of the given numbers. This basis provides a compact representation that allows for quick computation and manipulation of the vector space.

Important terms

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

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

Z2d{\mathbb{Z_2^d}}: It represents the set of all binary vectors of length dd, where each component of the vector belongs to the field Z2{\mathbb{Z_2}}, which consists of two elements: 0 and 1.

Linear Span

The span of a set of vectors S={v1,v2,...,vn}{S = \{v_1, v_2,..., v_n \}} in a vector space VV consists of all vectors xx that can be represented as linear combination of the vectors in SS. Mathematically, the span of SS is defined as:

span(s)={i=1nciviviS,ci{0,1}}\begin{align*} span(s) = \bigg\{\sum_{i=1}^{n} c_i v_i \bigg| v_i \in S, c_i \in \{0, 1\} \bigg\} \end{align*}

This mean that any vector xx in VV can be expressed as a liner combination fo the vectors v1,v2,...,vnv_1, v_2,...,v_n in SS, where each coefficient cic_i is either 0 or 1. The span of SS represents the subspace of VV that is generated by the vectors in SS, 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={v1,v2,....,vn}B = \{v_1, v_2,....,v_n\} is termed the basis of a vector space VV if the span of BB covers VV entirely and BB is linearly independent. In other words, any vector in VV can be expressed as a linear combination of the vectors in BB, and no vector in BB can be represented as a linear combination of the others. The number of vectors in BB , denoted as nn, is defined as the dimension of VV, represented by dim(V)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

Focus Problem – try your best to solve this problem before continuing!

You are given a set of NN 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 AA and BB in the set, their bitwise xor ABA \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 2basis.size()n2^{basis.size()}- n. Here 2basis.size()2^{basis.size()} represents the total number of distinct vectors that can be formed using the basis, including the zero vector. By subtracting nn, the number of input vectors, we adjust for the actual number of vectors, providing insight into their linear independence and redundancy. The computed value is then printed as the output, reflecting the difference between the total possible combinations and the number of given vectors.

C++

#include <bits/stdc++.h>
using namespace std;
#define i23 long long
vector<i23> basis;
void add(i23 x) {
for (int i = 0; i < (int)basis.size();
i++) { // reduce x using the current basis vectors
x = min(x, x ^ basis[i]);

Example - Trees and XOR Queries Again

Focus Problem – try your best to solve this problem before continuing!

You are given a tree consisting of nn vertices. There is an integer written on each vertex; the ii-th vertex has integer aia_i written on it. You have to process qq queries. The ii-th query consists of three integers xix_i, yiy_i and kik_i. For this query, you have to answer if it is possible to choose a set of vertices v1,v2,,vmv_1,v_2,…,v_m (possibly empty) such that:

  • every vertex vjv_j is on the simple path between xix_i and yiy_i (endpoints can be used as well);
  • av1av2avm=kia_{v_1} \oplus a_{v_2} \oplus \dots \oplus a_{v_m} = k_i, where \oplus denotes the bitwise XOR operator.

Solution

To efficiently compute XOR bases on paths in a tree, we use a method involving tree rooting, Lowest Common Ancestor (LCA), and properties of XOR bases. The process begins by rooting the tree and using LCA to split any path into two vertical paths. For each vertex vv, we maintain a list of "interesting" vertices that significantly influence the XOR base when traversing from vv to the root. Due to the properties of XOR bases, these lists are small, with a maximum size of 20.

The core idea is to build these lists for all vertices efficiently. For a vertex vv, its list is derived from its parent's list. If vv adds a new element to the XOR base of its parent's list, vv is added to its list; otherwise, one element in the parent's list is replaced. This propagation ensures that the size of each list remains manageable and enables efficient construction of these lists in O(nB2)\mathcal{O}(nB^2) time, where BB is the size of the XOR base, typically 20.

When answering a query, the XOR base for any path is obtained by combining the lists from the two vertical paths derived from the LCA. This merging and computation can be done in O(B2+logn)\mathcal{O}(B^2 + \log n) time per query, providing an efficient solution for the problem.

C++

#include <bits/stdc++.h>
using namespace std;
const int N = 200001, K = 20;
vector<int> arr(N), tin(N, 0), tout(N, 0), up[N];
vector<int> adj[N];
vector<vector<int>> p(N, vector<int>(K, 0));
int T = 0;
int reduce(array<int, K> &b, int x) { // reducing x using basis vectors b

Problems

Resources
Benq

8 related tasks

Some harder tasks:

StatusSourceProblem NameDifficultyTags
ACNormal
ACNormal
CFNormal
CFNormal
CFNormal
CFNormal
CFHard
CFVery Hard
CFVery Hard
ACVery Hard
TCInsane

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!