Base XOR

Recursos

Introducción

Una base XOR (XOR basis) es un conjunto mínimo de vectores binarios linealmente independientes que puede representar cualquier vector de un conjunto dado mediante combinaciones XOR. En problemas computacionales, construir una base XOR consiste en agregar vectores de forma iterativa a la base asegurando que cada vector nuevo permanezca independiente reduciéndolo con los vectores de la base existentes. Esta base permite representar y manipular de forma eficiente espacios vectoriales binarios, habilitando la determinación rápida de independencia lineal y facilitando soluciones a varios problemas de optimización y combinatoria.

La base XOR involucra dos partes:

• Representar cada número dado en su forma en base 2, considerándolo como un vector en el espacio vectorial $${\mathbb{Z_2^d}}$$, donde $d$ es el número máximo posible de bits. La operación XOR sobre estos números es equivalente a la suma de los vectores correspondientes en el espacio vectorial $${\mathbb{Z_2^d}}$$.

• Relacionar las respuestas a las consultas del segundo tipo con la base de los vectores hallados en la Parte 1. Al construir una base XOR a partir del conjunto de vectores, podemos responder de forma eficiente varias consultas sobre independencia lineal, redundancia y otras propiedades relacionadas con las combinaciones XOR de los números dados. Esta base proporciona una representación compacta que permite cálculo y manipulación rápidos del espacio vectorial.

Términos importantes

Espacio vectorial $${\mathbb{Z_2^d}}$$

$${\mathbb{Z_2}}$$: $${\mathbb{Z_m}}$$ es el conjunto de restos al dividir por m. Por lo tanto, $${\mathbb{Z_2}}$$ es el conjunto de restos al dividir por 2. De ahí que $${\mathbb{Z_2}}$$ sea simplemente el conjunto $$\{0, 1\}$$.

$${\mathbb{Z_2^d}}$$: representa el conjunto de todos los vectores binarios de longitud $d$, donde cada componente del vector pertenece al cuerpo $${\mathbb{Z_2}}$$, que consiste en dos elementos: 0 y 1.

Envolvente lineal (span)

El span de un conjunto de vectores $${S = \{v_1, v_2,..., v_n \}}$$ en un espacio vectorial $V$ consiste en todos los vectores $x$ que se pueden representar como combinación lineal de los vectores de $S$. Matemáticamente, el span de $S$ se define como:

Esto significa que cualquier vector $x$ en $V$ se puede expresar como una combinación lineal de los vectores $$v_1, v_2,...,v_n$$ en $S$, donde cada coeficiente $c_i$ es 0 o 1. El span de $S$ representa el subespacio de $V$ generado por los vectores de $S$, abarcando todas las combinaciones posibles de esos vectores. Entender el span de un conjunto de vectores es crucial para determinar el alcance o la extensión de la influencia de los vectores dentro del espacio vectorial.

Base

Un conjunto de vectores $B = \{v_1, v_2,....,v_n\}$ se denomina base de un espacio vectorial $V$ si el span de $B$ cubre $V$ por completo y $B$ es linealmente independiente. En otras palabras, cualquier vector de $V$ se puede expresar como combinación lineal de los vectores de $B$, y ningún vector de $B$ se puede representar como combinación lineal de los demás. El número de vectores de $B$, denotado $n$, se define como la dimensión de $V$, representada por $dim(V)$. Entender la base y la dimensión de un espacio vectorial es crucial para analizar su estructura, resolver ecuaciones lineales y realizar transformaciones en varios contextos matemáticos y computacionales.

Ejemplo - Xor Closure

Se da un conjunto de $N$ valores enteros. Hay que hallar el número mínimo de valores que se necesitan agregar al conjunto de modo que se cumpla lo siguiente:

• Para cada par de enteros $A$ y $B$ del conjunto, su xor bit a bit $$A \oplus B$$ también está en el conjunto.

Solución

La solución consiste en construir una base XOR a partir de un conjunto de vectores binarios y calcular un valor basado en esta base. Cada vector se inserta en la base XOR intentando minimizarlo mediante XOR con los vectores de la base existentes, asegurando que el vector permanezca linealmente independiente. Si el vector no se puede reducir por completo a cero, se agrega a la base. Esto asegura que la base solo contenga el conjunto mínimo de vectores necesario para representar el espacio generado por los vectores de entrada.

Una vez construida la base, el resultado final se calcula como $$2^{basis.size()}- n$$. Aquí $$2^{basis.size()}$$ representa el número total de vectores distintos que se pueden formar usando la base, incluyendo el vector cero. Al restar $n$, el número de vectores de entrada, ajustamos por el número real de vectores, dando información sobre su independencia lineal y redundancia. El valor calculado se imprime como salida, reflejando la diferencia entre el total de combinaciones posibles y el número de vectores dados.

#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]);
	}
 
	if (x != 0) { basis.push_back(x); }
}
 
int main() {
	int n;
	cin >> n;
	vector<i23> arr(n);
	for (auto &x : arr) {
		cin >> x;
		add(x);
	}
 
	i23 res = (1LL << (int)basis.size()) - n;
	cout << res << '\n';
 
	return 0;
}

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)

Puede que uno se pregunte por qué funciona este método de reducción. Por ejemplo, si los elementos de la base fueran actualmente $[1_2, 11_2]$ y se intentara insertar $10_2$, se terminaría con un resultado de $1_2$. Esto es claramente incorrecto, ya que $10_2$ no es independiente de la base $[1_2, 11_2]$.

Sin embargo, el truco es que todos los demás elementos de la base deben reducirse con el mismo método. Esto significa que $[1_2, 11_2]$ no es realmente una base válida: reducida correctamente, debería ser $[1_2, 10_2]$.

Más en general, esta reducción garantiza que, si el bit $x$ es el MSB de un elemento de la base, debe estar apagado en todos los elementos de la base posteriores: por eso este método de reducción funciona sin tener que mantener los vectores de la base en orden.

Ejemplo - Trees and XOR Queries Again

Se da un árbol que consiste en $n$ vértices. Hay un entero escrito en cada vértice; el $i$-ésimo vértice tiene el entero $$a_i$$ escrito en él. Hay que procesar $q$ consultas. La $i$-ésima consulta consiste en tres enteros $$x_i$$, $$y_i$$ y $$k_i$$. Para esta consulta, hay que responder si es posible elegir un conjunto de vértices $v_1,v_2,…,v_m$ (posiblemente vacío) tal que:

• cada vértice $$v_j$$ está en el camino simple entre $$x_i$$ e $$y_i$$ (los extremos también se pueden usar);
• $$a_{v_1} \oplus a_{v_2} \oplus \dots \oplus a_{v_m} = k_i$$, donde $\oplus$ denota el operador XOR bit a bit.

Solución

Para calcular de forma eficiente bases XOR sobre caminos en un árbol, usamos un método que involucra enraizar el árbol, el ancestro común más bajo (LCA) y propiedades de las bases XOR. El proceso empieza enraizando el árbol y usando LCA para partir cualquier camino en dos caminos verticales. Para cada vértice $$v$$, mantenemos una lista de vértices “interesantes” que influyen de forma significativa en la base XOR al recorrer de $$v$$ a la raíz. Por las propiedades de las bases XOR, estas listas son chicas, con un tamaño máximo de 20.

La idea central es construir estas listas para todos los vértices de forma eficiente. Para un vértice $$v$$, su lista se deriva de la lista de su padre. Si $$v$$ agrega un elemento nuevo a la base XOR de la lista de su padre, $$v$$ se agrega a su lista; en caso contrario, se reemplaza un elemento de la lista del padre. Esta propagación asegura que el tamaño de cada lista permanezca manejable y permite construir estas listas de forma eficiente en $\mathcal{O}(nB^2)$, donde $$B$$ es el tamaño de la base XOR, típicamente 20.

Al responder una consulta, la base XOR de cualquier camino se obtiene combinando las listas de los dos caminos verticales derivados del LCA. Esta fusión y cálculo se puede hacer en $\mathcal{O}(B^2 + \log n)$ por consulta, proporcionando una solución eficiente para el problema.

#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
	for (int i = K - 1; i >= 0; i--) {
		if (x & (1 << i)) {  // check if the ith bit is set
			x ^= b[i];
		}
	}
	return x;
}
 
bool add(array<int, K> &b, int x) {
	x = reduce(b, x);  // reduce x using current basis
	if (x != 0) {
		for (int i = K - 1; i >= 0; i--) {
			if (x & (1 << i)) {
				b[i] = x;  // add x to the basis if it is independent
				return true;
			}
		}
	}
	return false;
}
 
bool check(array<int, K> &b, int x) {
	return (reduce(b, x) ==
	        0);  // if x reduces to 0, it can be represented by the basis
}
 
vector<int> rebuild_path(const vector<int> &path, int v) {
	array<int, K> b{0};
	vector<int> res;
	if (add(b, arr[v])) {
		res.push_back(v);  // add v to the result if it is independent
	}
	for (auto x : path) {
		if (add(b, arr[x])) {
			res.push_back(x);  // add x to the result if it is independent
		}
	}
	return res;
}
 
// Depth First Search to set up LCA and basis paths
void dfs(int v, int u) {
	tin[v] = T++;  // set in-time for the current node
	if (u == v) {
		up[v] = rebuild_path(vector<int>(0), v);  // root node case
	} else {
		up[v] = rebuild_path(up[u], v);  // rebuild path for the current node
	}
 
	p[v][0] = u;  // set direct path in ancestor table
	for (int i = 1; i < K; i++) {
		p[v][i] = p[p[v][i - 1]][i - 1];  // fill ancestor table for LCA
	}
 
	for (int i = 0; i < (int)adj[v].size(); i++) {
		if (adj[v][i] != u) {
			dfs(adj[v][i], v);  // recursively call dfs for children
		}
	}
	tout[v] = T++;  // set out-time for the current node
}
 
bool is_ancestor(int u, int v) {
	return (tin[u] <= tin[v] && tout[u] >= tout[v]);  // check if u is an ancestor of v
}
 
int LCA(int x, int y) {
	if (is_ancestor(x, y)) {
		return x;  // return x if it is an ancestor of y
	}
	for (int i = K - 1; i >= 0; i--) {
		if (!is_ancestor(p[x][i], y)) {
			x = p[x][i];  // move x up in the tree
		}
	}
	return p[x][0];  // return the parent of x as the LCA
}
 
bool query(int x, int y, int k) {
	array<int, K> b{0};
	int lca = LCA(x, y);
	for (auto v : up[x]) {
		if (!is_ancestor(v, y)) {
			add(b, arr[v]);  // add vector to basis if not an ancestor of y
		}
	}
 
	for (auto v : up[y]) {
		if (!is_ancestor(v, x)) {
			add(b, arr[v]);  // Add vector to basis if not an ancestor of x
		}
	}
 
	add(b, arr[lca]);    // add LCA's value to basis
	return check(b, k);  // // check if k can be represented by the basis
}
 
int main() {
	int n, q;
	cin >> n;
	for (int i = 0; i < n; i++) { cin >> arr[i]; }
 
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
 
	dfs(0, 0);
	cin >> q;
	for (int i = 0; i < q; i++) {
		int x, y, k;
		cin >> x >> y >> k;
		x--, y--;
		cout << (query(x, y, k) ? "YES" : "NO") << '\n';
	}
 
	return 0;
}

Problemas

Algunas tareas más difíciles: