(Opcional) Bitsets

Tutorial

tl;dr algunas operaciones son unas 32-64 veces más rápidas que un arreglo booleano. Ver la referencia de C++ para las operaciones que se pueden hacer.

Recursos
Fuente	Recurso	Notas
CPH	Bit Optimizations	acelerar la distancia de Hamming
CF	Errichto - Bitwise Operations Pt 2

Mochila (knapsack)

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	School Excursion	Fácil	Knapsack, Bitset	en el módulo

Por supuesto, el primer paso es generar los tamaños de cada componente conexa.

C++Python


#include <bits/stdc++.h>
using namespace std;
 
// BeginCodeSnip{DSU}
struct DSU {
	vector<int> e;
	void init(int N) { e = vector<int>(N, -1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
	bool sameSet(int a, int b) { return get(a) == get(b); }
	int size(int x) { return -e[get(x)]; }
	bool unite(int x, int y) {  // union by size
		x = get(x), y = get(y);
		if (x == y) return 0;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y];
		e[y] = x;
		return 1;
	}
};
// EndCodeSnip
 
DSU D;
int n, m;
vector<int> comps;
 
void init() {
	cin >> n >> m;
	D.init(n);
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		D.unite(a - 1, b - 1);
	}
	for (int i = 0; i < n; ++i)
		if (D.get(i) == i) comps.push_back(D.size(i));
}


# BeginCodeSnip{DSU}
class DisjointSet:
	parent = {}
	sz = []
 
	def __init__(self, sz: int) -> int:  # Construir el DSU
		self.sz.append(1)
		for i in range(1, sz + 1):
			self.parent[i] = i
			self.sz.append(1)
 
	def find(self, k: int) -> int:  # Hallar la raíz de la componente de k
		if self.parent[k] == k:
			return k
		return self.find(self.parent[k])
 
	def find_size(self, x: int) -> int:  # Hallar el tamaño de la componente de x
		return self.sz[self.find(x)]
 
	def union(self, a: int, b: int) -> int:  # Combinar dos componentes en una
		x = self.find(a)
		y = self.find(b)
		self.sz[y] += self.sz[x]
		self.parent[x] = y
 
 
# EndCodeSnip
 
 
n, m = map(int, input().split(" "))
 
ds = DisjointSet(n)
 
for i in range(m):
	x, y = map(int, input().split(" "))
	ds.union(x, y)
 
sizes = []
for i in range(1, n + 1):
	if ds.find(i) == i:
		sizes.append(ds.find_size(i))

Una solución naive de mochila sería la siguiente. Para cada $0\le i\le \texttt{comps.size()}$ , sea $\texttt{dp}[i][j]=1$ si existe un subconjunto de las primeras $i$ componentes cuyos tamaños suman $j$ . Entonces la respuesta quedará guardada en $\texttt{dp}[i]$ . Esto corre en $\mathcal{O}(N^2)$ y es demasiado lento si se implementa de forma naive, ¡pero podemos usar bitset para acelerarlo!

Nota: no se pueden guardar los $N$ bitsets en memoria al mismo tiempo (más sobre eso abajo).

Solución completa - School Excursion

PythonC++


# BeginCodeSnip{DSU}
 
 
class DisjointSet:
	parent = {}
	sz = []
 
	def __init__(self, sz: int) -> int:
		self.sz.append(1)
		for i in range(1, sz + 1):
			self.parent[i] = i
			self.sz.append(1)
 
	def find(self, k: int) -> int:
		if self.parent[k] == k:
			return k
		return self.find(self.parent[k])
 
	def find_size(self, x: int) -> int:
		return self.sz[self.find(x)]
 
	def union(self, a: int, b: int) -> int:
		x = self.find(a)
		y = self.find(b)
		self.sz[y] += self.sz[x]
		self.parent[x] = y
 
 
# EndCodeSnip
 
 
n, m = map(int, input().split(" "))
 
ds = DisjointSet()
ds.make_set(n)
 
for i in range(m):
	x, y = map(int, input().split(" "))
	ds.union(x, y)
 
sizes = []
for i in range(1, n + 1):
	if ds.find(i) == i:
		sizes.append(ds.find_size(i))
 
num = 1
for i in sizes:
	num = num | num << i
 
string = str(bin(num))
print(string[3 : len(string)])


#include <bits/stdc++.h>
using namespace std;
 
// BeginCodeSnip{DSU}
struct DSU {
	vector<int> e;
	void init(int N) { e = vector<int>(N, -1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
	bool sameSet(int a, int b) { return get(a) == get(b); }
	int size(int x) { return -e[get(x)]; }
	bool unite(int x, int y) {  // union by size
		x = get(x), y = get(y);
		if (x == y) return 0;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y];
		e[y] = x;
		return 1;
	}
};
 
DSU D;
int n, m;
vector<int> comps;
 
void init() {
	cin >> n >> m;
	D.init(n);
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		D.unite(a - 1, b - 1);
	}
	for (int i = 0; i < n; ++i)
		if (D.get(i) == i) comps.push_back(D.size(i));
}
// EndCodeSnip
 
int main() {
	init();
	bitset<100001> posi;
	posi[0] = 1;
	for (int t : comps) posi |= posi << t;
	for (int i = 1; i <= n; ++i) cout << posi[i];
	cout << "\n";
}

Desafío: esta solución corre en $\approx 0.3\text{s}$ cuando $N=10^5$ y no hay aristas. Hallar una solución más rápida que también se pueda acelerar con bitset (mi solución corre en 0.03s).

Cowpatibility (Oro)

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	Gold	Cowpatibility	Normal	PIE, Bitset	Solución

Etiquetar las vacas de $0\ldots N-1$ . Para dos vacas $x$ e $y$ poner adj[x][y]=1 si comparten un sabor en común. Entonces la cantidad de pares de vacas compatibles (contando dos veces cada par donde $x$ e $y$ son distintos) es igual a la suma de adj[x].count() sobre todo $x$ . Queda calcular adj[x] para todo $x$ .

Lamentablemente, guardar $N$ bitsets de $N$ bits cada uno ocupa $\frac{50000^2}{32}\cdot 4=312.5\cdot 10^6$ bytes de memoria, que es mayor que el límite de $256$ megabytes de USACO. Podemos reducir el uso de memoria a la mitad a cambio de un leve aumento de tiempo calculando primero los bitsets de adyacencia para todo $x\in [0,N/2)$ , y después para todo $x\in [N/2,N)$ .

Primero, leemos todos los sabores.

C++


#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef bitset<50000> B;
const int HALF = 25000;
 
int N;
B adj[HALF];
vector<int> flav[1000001];
ll ans;
 
void input() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	freopen("cowpatibility.in", "r", stdin);
	freopen("cowpatibility.out", "w", stdout);
	cin >> N;
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < 5; ++j) {
			int x;
			cin >> x;
			flav[x].push_back(i);
		}
}

Después, para cada sabor, podemos mirar todos los pares de vacas que comparten ese sabor y actualizar las listas de adyacencia para esos $x\in [0,HALF)$ .

C++


int main() {
	input();
	for (int i = 1; i <= 1000000; ++i)
		for (int x : flav[i])
			if (x < HALF)
				for (int y : flav[i]) adj[x][y] = 1;
	for (int i = 0; i < HALF; ++i) ans += adj[i].count();
}

adj[i].count() corre lo bastante rápido porque su tiempo de ejecución se divide por la constante del bitset. Sin embargo, recorrer todas las vacas de flav[i] es demasiado lento si, por ejemplo, flav[i] contiene a todas las vacas. Entonces el bucle anidado podría tardar tiempo $\Theta(N^2)$ . Por supuesto, en su lugar podemos escribir el bucle anidado de una forma que aproveche de nuevo las operaciones rápidas de bitset.

C++


for (int i = 1; i <= 1000000; ++i)
	if (flav[i].size() > 0) {
		B b;
		for (int x : flav[i]) b[x] = 1;
		for (int x : flav[i])
			if (x < HALF) adj[x] |= b;
	}

La función main completa es la siguiente:

C++


int main() {
	input();
	for (int i = 1; i <= 1000000; ++i)
		if (flav[i].size() > 0) {
			B b;
			for (int x : flav[i]) b[x] = 1;
			for (int x : flav[i])
				if (x < HALF) adj[x] |= b;
		}
	for (int i = 0; i < HALF; ++i) ans += adj[i].count();
	for (int i = 0; i < HALF; ++i) adj[i].reset();
	for (int i = 1; i <= 1000000; ++i)
		if (flav[i].size() > 0) {
			B b;
			for (int x : flav[i]) b[x] = 1;
			for (int x : flav[i])
				if (x >= HALF) adj[x - HALF] |= b;
		}
	for (int i = 0; i < HALF; ++i) ans += adj[i].count();
	cout << ((ll)N * N - ans) / 2 << "\n";
}

Aparentemente ningún caso de prueba contiene más de $25000$ colores distintos, así que en realidad no hace falta partir el cálculo en dos mitades.

Lots of Triangles

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	Platinum	Lots of Triangles	Normal	Geometry, Bitset	—

Primero, leemos la entrada. cross(a,b,c) es positivo sii c queda a la izquierda de la recta de a a b.

C++


#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> P;
 
#define f first
#define s second
 
ll cross(P a, P b, P c) {
	b.f -= a.f, b.s -= a.s;
	c.f -= a.f, c.s -= a.s;
	return b.f * c.s - b.s * c.f;
}
 
vector<P> v;
int N;
 
void input() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	freopen("triangles.in", "r", stdin);
	freopen("triangles.out", "w", stdout);
	cin >> N;
	v.resize(N);
	for (P &p : v) cin >> p.f >> p.s;
}

Hay $\mathcal{O}(N^3)$ lotes posibles. Probar todos los lotes posibles y contar la cantidad de árboles que quedan dentro de cada uno en $\mathcal{O}(N)$ para una complejidad temporal total de $\mathcal{O}(N^4)$ debería resolver entre 2 y 5 casos de prueba. Dado un triángulo t[0], t[1], t[2] de área positiva, el árbol x queda dentro sii x está a la izquierda de cada uno de los lados (t[0],t[1]),(t[1],t[2]) y (t[2],t[0]).

C++


int main() {
	input();
	vector<int> res(N - 2);
	for (int i = 0; i < N; ++i)
		for (int j = i + 1; j < N; ++j)
			for (int k = j + 1; k < N; ++k) {
				vector<int> t = {i, j, k};
				if (cross(v[t[0]], v[t[1]], v[t[2]]) < 0) swap(t[1], t[2]);
				int cnt = 0;
				for (int x = 0; x < N; ++x) {
					if (cross(v[t[0]], v[t[1]], v[x]) <= 0) continue;
					if (cross(v[t[1]], v[t[2]], v[x]) <= 0) continue;
					if (cross(v[t[2]], v[t[0]], v[x]) <= 0) continue;
					cnt++;
				}
				res[cnt]++;
			}
	for (int i = 0; i < N - 2; ++i) cout << res[i] << "\n";
}

El análisis describe cómo contar la cantidad de árboles dentro de un lote en $\mathcal{O}(1)$ , lo que alcanza para resolver el problema. Sin embargo, $\mathcal{O}(N)$ en realidad alcanza siempre que dividamos por la constante del bitset. Sea b[i][j][k]=1 si k queda a la izquierda del lado (i,j). Entonces x queda dentro del triángulo (t[0],t[1],t[2]) siempre que b[t[0]][t[1]][x]=b[t[1]][t[2]][x]=b[t[2]][t[0]][x]=1. Podemos contar la cantidad de x para los que esto vale tomando el AND bit a bit de los bitsets de los tres lados y después contando la cantidad de bits del resultado.

Solución rápida


bitset<300> b[300][300];
 
int main() {
	input();
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			if (j != i)
				for (int k = 0; k < N; ++k)
					if (cross(v[i], v[j], v[k]) > 0) b[i][j][k] = 1;
	vector<int> res(N - 2);
	for (int i = 0; i < N; ++i)
		for (int j = i + 1; j < N; ++j)
			for (int k = j + 1; k < N; ++k) {
				vector<int> t = {i, j, k};
				if (cross(v[t[0]], v[t[1]], v[t[2]]) < 0) swap(t[1], t[2]);
				auto z = b[t[0]][t[1]] & b[t[1]][t[2]] & b[t[2]][t[0]];
				res[z.count()]++;
			}
	for (int i = 0; i < N - 2; ++i) cout << res[i] << "\n";
}

Mochila otra vez

(GP of Bytedance 2020 F)

Dados $n$ ( $n\le 2\cdot 10^4$ ) enteros positivos $a_1,\ldots,a_n$ ( $a_i\le 2\cdot 10^4$ ), hallar la suma máxima posible de un subconjunto de $a_1,\ldots,a_n$ cuya suma no exceda $c$ .

Considerar el caso cuando $\sum a_i\ge c$ . La solución intencionada corre en $\mathcal{O}(n\cdot \max(a_i))$ ; ver acá para más información. Sin embargo, lo resolveremos con bitset.

Como en el primer problema de este módulo, sea $\texttt{dp}[i][j]=1$ si existe un subconjunto de las primeras $i$ componentes numéricas que suma $j$ . Esta solución corre en tiempo $\mathcal{O}(n\cdot \sum a_i)$ , que es demasiado lento incluso si usamos bitset.

Tomando inspiración de este blog de CF, primero barajamos los enteros al azar y hacemos la DP con la siguiente modificación:

Si $\left|\frac{ci}{n}-j\right| \ge X$ para algún $X$ que elijamos, entonces poner $\texttt{dp}[i][j]=0$ .

Como solo hay que llevar el registro de $2X+1$ valores para cada $i$ , esta solución corre en tiempo $\mathcal{O}(nX)$ , que es lo bastante rápido con $X=5\cdot 10^5$ usando bitset.

Resulta que $X\approx \max a_i\cdot \sqrt n$ (salvo una constante) alcanza para la corrección con alta probabilidad (se menciona de forma breve acá ). No estoy del todo seguro de los detalles, pero de forma intuitiva, el barajado aleatorio reduce el subconjunto óptimo a alguna distribución con varianza a lo sumo $(\max a_i)^2\cdot n$ . En el caso especial en que cada $a_i$ es $0$ o $\max a_i$ , podemos acotar la probabilidad de fallo usando los números de Catalan. Creo que es algo como $e^{-\frac{m^2}{n}}$ si dejamos que el bitset tenga tamaño $m\cdot \max a_i$ .

Solución

C++


#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int n, c;
const int Z = 1000000;
mt19937 rng;
 
int solve() {
	cin >> n >> c;
	vector<int> a(n);
	int sum = 0;
	for (int &x : a) {
		cin >> x;
		sum += x;
	}
	if (sum <= c) return sum;
	shuffle(begin(a), end(a), rng);
	bitset<Z> B;
	B[Z / 2] = 1;
	ll lst = 0;
	for (int i = 0; i < n; ++i) {
		ll cur = (ll)(i + 1) * c / n;
		int dif = cur - lst;
		lst = cur;
		auto tmp = B >> dif;
		ll wut = a[i] - dif;
		if (wut >= 0) B = tmp | (B << wut);
		else B = tmp | (B >> (-wut));
	}
	for (int i = Z / 2; i >= 0; --i)
		if (B[i] == 1) return c - (Z / 2 - i);
	return 0;
}
 
int main() {
	int T;
	cin >> T;
	for (int i = 0; i < T; ++i) cout << solve() << "\n";
}

Otras aplicaciones

Usar para acelerar lo siguiente:

Eliminación gaussiana en $\mathcal{O}(N^3)$
Matching bipartito en $\mathcal{O}(N^3)$ (grafo denso con $N$ vértices de cada lado)
- Aunque $\mathcal{O}(NM)$ el algoritmo de Kuhn probablemente sea lo bastante rápido …
BFS sobre un grafo denso en $\mathcal{O}(N^2)$
~~En general, pasar soluciones con un factor adicional de $N$ .~~

Operaciones como _Find_first() y _Find_next() mencionadas en el blog de Errichto pueden ser útiles.

Recursos
Fuente	Recurso	Notas
GFG	_Find_next() function in C++ bitset	el único recurso que pude encontrar :P

Un comentario respecto de las últimas dos aplicaciones:

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSA	Substring Restrictions	Difícil	DSU	—

En USACO Camp apareció un problema similar con $N\le 10^5$ y un límite de tiempo de $6$ segundos (presumiblemente para dejar pasar soluciones $\mathcal{O}(N\log ^2N)$ ). Ya había hecho este problema pero ~~olvidé cómo lo había resuelto~~ decidí probar algo nuevo. ¡Intentar adivinar qué hice!

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
AC	Triangle	Fácil	Bitset	—
CSES	Reachable Nodes	Fácil	Bitset, TopoSort	Solución
AC	Balancing Network (T=1)	Fácil	Bitset	—
TOKI	Tzaph & Number Line	Fácil	Bitset	—
Baltic OI	2019 - Nautilus	Normal	Bitset	—
Baltic OI	2010 - Candies	Normal	Knapsack, Bitset	Solución
COCI	2015 - Uzastopni	Normal	Bitset	Solución
Platinum	Equilateral Triangles	Difícil	Bitset, Sliding Window	—
IZhO	2017 - Bootfall	Difícil	Knapsack, Bitset	Solución
Baltic OI	2015 - Tug of War	Difícil	Knapsack, Bitset	Solución
CF	Rectangular Polyline	Difícil		—