(Opcional) Tablas hash

Hashing

El hashing consiste en asignar un código único a cada variable/objeto, lo que permite inserciones, borrados y búsquedas en tiempo $\mathcal{O}(1)$, aunque con un factor constante alto, ya que el hashing requiere un número constante grande de operaciones. Sin embargo, como el nombre indica, los elementos no están ordenados de ninguna forma significativa, así que los recorridos de un conjunto no ordenado devolverán los elementos en algún orden arbitrario.

Hashing personalizado

#include <bits/stdc++.h>
using namespace std;
 
typedef pair<int, int> pi;
#define f first
#define s second
 
struct hashPi {
	size_t operator()(const pi &p) const { return p.f ^ p.s; }
};
 
int main() { unordered_map<pi, int, hashPi> um; }

#include <bits/stdc++.h>
using namespace std;
 
typedef pair<int, int> pi;
#define f first
#define s second
 
namespace std {
template <> struct hash<pi> {
	size_t operator()(const pi &p) const { return p.f ^ p.s; }
};
}  // namespace std
 
int main() { unordered_map<pi, int> um; }

import java.io.*;
import java.util.*;
 
public class HashTest {
	public static void main(String[] args) {
		// uses custom hash function in class Pair
		Set<Pair> set = new HashSet<>();
	}
 
	static class Pair {
		public int first, second;
 
		public Pair(int first, int second) {
			this.first = first;
			this.second = second;
		}
 
		@Override
		public int hashCode() {
			return first ^ second;
		}
 
		@Override
		public boolean equals(Object o) {
			if (!(o instanceof Pair)) { return false; }
			Pair p = (Pair)o;
			return first == p.first && second == p.second;
		}
	}
}

Sin embargo, esta función de hash es bastante mala; si insertamos $(0,0), (1,1), (2,2) \ldots$ entonces todos se mapearán a la misma cubeta (así que se hackearía fácilmente en un contest de Codeforces).

import java.io.*;
import java.util.*;
 
public class HashTest {
	public static void main(String[] args) {
		// uses custom hash function in class Pair
		Set<Pair> set = new HashSet<>();
		for (int i = 0; i < 100000; ++i) {
			// Pair p = new Pair(i, 0); // ~0.2s on ide.usaco.guide
			Pair p = new Pair(i, -31 * i);  // >5s
			set.add(p);
		}
	}
 
	static class Pair {
		public int first, second;
 
		public Pair(int first, int second) {
			this.first = first;
			this.second = second;
		}
 
		@Override
		public int hashCode() {
			return Objects.hash(first, second);
		}
 
		@Override
		public boolean equals(Object o) {
			if (!(o instanceof Pair)) { return false; }
			Pair p = (Pair)o;
			return first == p.first && second == p.second;
		}
	}
}

Una mejor forma de hashear pares sería usar hashing polinómico con una base aleatorizada (como se describe en este módulo).

Tests anti-hash

El algoritmo de hashing nativo para enteros en C++ es vulnerable a tests patológicos, que provocan tiempos de ejecución anormalmente lentos. Describimos el problema abajo y cómo arreglarlo. Quienes usen Java no se ven afectados (ver este  comentario).

// source: https://codeforces.com/blog/entry/62393
#include <cassert>
#include <ctime>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
 
const int N = 2e5;
 
vector<int> gen_multiples(int x) {
	int cur = 1, rem = 1;
	vector<int> res;
	for (int i = 1; i <= N; i++) {
		assert(1 <= cur && cur <= 1e9);
		res.push_back(cur);
		cur += x;
		if (cur > 1e9) {
			++rem;
			cur = rem;
		}
	}
	return res;
}
 
double insert_numbers(vector<int> nums) {
	clock_t begin = clock();
	unordered_map<long long, int> m;
	for (int n : nums) m[n];
	return (double)(clock() - begin) / CLOCKS_PER_SEC;
}
 
int main() {
	const long prime_list[]{
	    107897ul, 116731ul, 126271ul, 136607ul, 147793ul, 159871ul, 172933ul,
	    187091ul, 202409ul, 218971ul, 236897ul, 256279ul, 277261ul, 299951ul,
	};  // https://github.com/gcc-mirror/gcc/blob/5bea0e90e58d971cf3e67f784a116d81a20b927a/libstdc%2B%2B-v3/src/shared/hashtable-aux.cc
	for (int prime : prime_list) {
		cerr << "testing " << prime << ": ";
		vector<int> multiples = gen_multiples(prime);
		double runtime = insert_numbers(multiples);
		cerr << runtime << "\n";
		if (runtime > 1) {
			// output hack case for https://cses.fi/problemset/task/1640/
			cout << N << " 1\n";
			for (int i = 0; i < N; ++i) {
				if (i) cout << " ";
				cout << multiples[i];
			}
			cout << "\n";
			exit(0);
		}
	}
}

Para que el unordered_map sea imposible de hackear, la función de hash $H$ que se elija debe tener la siguiente propiedad: es difícil hallar enteros $x$ e $y$ tales que $x\neq y$ pero $H(x)\equiv H(y) \pmod{P}$, donde $P$ es el módulo primo correspondiente al número de cubetas del unordered map. Nótese que:

• La función de hash por defecto, $H(x)=x$, obviamente no satisface esta propiedad, porque se puede elegir simplemente $x=0$ e $y=P$.
• Si se permite el hacking abierto, entonces cualquier función de hash determinista no satisface esta propiedad, porque un hacker podría generar un caso de prueba específicamente para romper la solución. Hay que introducir aleatoriedad para asegurar que la función de hash cambie de una ejecución a otra.

Aquí hay un reemplazo directo de unordered_map que parece funcionar bien en la práctica:

struct chash {
	// any random-ish large odd number will do
	const uint64_t C = uint64_t(2e18 * PI) + 71;
	// random 32-bit number
	const uint32_t RANDOM = chrono::steady_clock::now().time_since_epoch().count();
	size_t operator()(uint64_t x) const {
		// see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
		return __builtin_bswap64((x ^ RANDOM) * C);
	}
};
template <class K, class V> using cmap = unordered_map<K, V, chash>;
// example usage: cmap<int, int>

Una tabla hash más rápida en C++

En C++, suele ser más rápido usar gp_hash_table<K, V> en lugar de unordered_map<K, V>. Las lecturas / escrituras son mucho más rápidas que con unordered_map. La documentación es bastante confusa, así que resumiré aquí las funciones más útiles. Si se necesita un reemplazo de unordered_set<K>, usar gp_hash_table<K, null_type>.

Hashing personalizado

Al igual que unordered_map, gp_hash_table es vulnerable a colisiones de hash si no se usa una función de hash personalizada. Recomendamos usar la misma función de hash personalizada que usamos arriba para unordered map:

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
 
gp_hash_table<int, int, chash> table;

Redimensionado

Unordered map tiene reserve. Llamar a esta función antes de insertar cualquier elemento puede resultar en una aceleración de factor constante.

Podemos modificar la declaración de gp_hash_table para que soporte la función resize, que opera de forma similar.

template <class K, class V>
using ht =
    gp_hash_table<K, V, hash<K>, equal_to<K>, direct_mask_range_hashing<>,
                  linear_probe_fn<>,
                  hash_standard_resize_policy<hash_exponential_size_policy<>,
                                              hash_load_check_resize_trigger<>, true>>;

Estos son los mismos argumentos de plantilla que el gp_hash_table por defecto, excepto que false se cambió a true. Esta modificación nos permite cambiar el tamaño real de la tabla hash.

int main() {
	ht<int, null_type> g;
	g.resize(5);
	cout << g.get_actual_size() << "\n";  // 8
	cout << g.size() << "\n";             // 0
}

Al llamar g.resize(x), x se redondea hacia arriba a la potencia de 2 más cercana. Luego el tamaño real de g se cambia para que sea igual a x (a menos que x < g.size(), en cuyo caso se lanza un error).

Además, si construimos g con los siguientes argumentos:

ht<int, null_type> g({}, {}, {}, {}, {1 << 16});

entonces el tamaño real de g es siempre al menos 1<<16 (independientemente de las llamadas a resize). El último argumento debe ser una potencia de 2 (o se lanzarán errores).

Resolviendo 3SUM

Como todos los valores son bastante pequeños, se puede usar un arreglo en lugar de una tabla hash. ¡Pero si no se leyeron las restricciones con suficiente cuidado, hay suerte!

#include <bits/stdc++.h>  // see C++ Tips & Tricks
using namespace std;
 
using ll = long long;
 
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
 
using pi = pair<int, int>;
#define f first
#define s second
#define mp make_pair
 
void setIO(string name = "") {  // name is nonempty for USACO file I/O
	ios_base::sync_with_stdio(0);
	cin.tie(0);  // see Fast Input & Output
	// alternatively, cin.tie(0)->sync_with_stdio(0);
	if (sz(name)) {
		freopen((name + ".in").c_str(), "r", stdin);  // see Input & Output
		freopen((name + ".out").c_str(), "w", stdout);
	}
}
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
 
int N, Q;
long long ans[5000][5000];
vector<int> A;
 
int main() {
	setIO("threesum");
	cin >> N >> Q;
	A.resize(N);
	for (int i = 0; i < N; ++i) cin >> A[i];
	for (int i = 0; i < N; ++i) {
		gp_hash_table<int, int> g({}, {}, {}, {}, {1 << 13});
		// initialize with certain capacity, must be power of 2
		for (int j = i + 1; j < N; ++j) {
			int res = -A[i] - A[j];
			auto it = g.find(res);
			if (it != end(g)) ans[i][j] = it->second;
			g[A[j]]++;
		}
	}
	for (int i = N - 1; i >= 0; --i)
		for (int j = i + 1; j < N; ++j)
			ans[i][j] += ans[i + 1][j] + ans[i][j - 1] - ans[i + 1][j - 1];
	for (int i = 0; i < Q; ++i) {
		int a, b;
		cin >> a >> b;
		cout << ans[a - 1][b - 1] << "\n";
	}
}

Problemas