Aleatoriedad

Recursos
Fuente	Recurso	Notas
CF	Randomized algorithms lecture, part 1 & 2
CF	Randomized Algorithms and Online Judges
Petr	Random problems

A veces podemos usar algoritmos aleatorizados para resolver tareas bastante difíciles para algoritmos deterministas.

Ejemplo - Ghd

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CF	★ Ghd	Normal	Random	en el módulo

Sea la respuesta $k$ . La observación clave de este problema es que un entero elegido al azar en $a$ tiene al menos probabilidad $\frac{1}{2}$ de ser divisible por $k$ .

Así, podemos repetir el siguiente procedimiento $S$ veces para hallar la respuesta óptima con probabilidad $1-\frac{1}{2^S}$ :

Sea $x$ un valor elegido al azar en $a$ .
Para cada divisor $d \mid x$ , determinar cuántos números de $a$ son divisibles por $d$ .
Tomar nuestra respuesta como el máximo de todos los $d$ tales que $\geq \frac{n}{2}$ números de $a$ son divisibles por $d$

Si tomamos $S = 15$ y estimamos el número de casos de prueba en Codeforces en $500$ , nuestra probabilidad de éxito es $(1-\frac{1}{2^{15}})^{500} \approx .984$ , que es aceptable.

Implementación

Nuestro enfoque tiene complejidad temporal

\mathcal{O}\left(S \cdot \left(N\log A + d(A)^2 + \sqrt{A}\right)\right)

, con el factor logarítmico por el cálculo de GCD, y la raíz por la factorización.


#include <bits/stdc++.h>
using namespace std;
 
const int MAX_N = 1e6 + 5;
const int S = 15;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long a[MAX_N], dv[MAX_N], cnt[MAX_N];
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
 
	long long ans = 0;
	for (int s = 0; s < S; s++) {
		long long x = a[rng() % n];
		int ind = 0;
		for (int d = 1; 1ll * d * d <= x; d++) {
			if (x % d == 0) {
				dv[ind++] = d;
				if (d * d != x) dv[ind++] = x / d;
			}
		}
 
		sort(dv, dv + ind);
		fill(cnt, cnt + ind, 0);
 
		for (int i = 0; i < n; i++) cnt[lower_bound(dv, dv + ind, gcd(a[i], x)) - dv]++;
 
		for (int i = 0; i < ind; i++)
			for (int j = 0; j < i; j++)
				if (dv[i] % dv[j] == 0) cnt[j] += cnt[i];
 
		for (int i = 0; i < ind; i++)
			if (cnt[i] + cnt[i] >= n) ans = max(ans, dv[i]);
	}
 
	cout << ans << '\n';
}

Ejemplo - Count on a Tree II Striking Back

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	QOJ	★ Count on a Tree II Striking Back	Difícil	Random	en el módulo

Intentar resolver este problema de forma directa — hallar explícitamente valores de $f(a,b)$ y $f(c,d)$ — es bastante difícil. Soportar consultas online de conteo de distintos en un rango junto con actualizaciones es bastante difícil de lograr en un arreglo con complejidad razonable, y el hecho de que este problema ocurre en un árbol, con una cota relativamente grande $n \leq 500$ $000$ deja claro que resolver el valor de $f$ no es lo intencionado.

En cambio, podemos intentar usar la propiedad dada en el enunciado de que o bien $f(a,b) \geq 2f(c,d)$ o $f(c,d) \geq 2f(a,b)$ . Esto inspira el siguiente pensamiento: si mapeamos cada color a un número aleatorio, el mínimo del camino a lo largo del camino con más colores distintos probablemente será un valor más chico.

Intentamos formalizar este enfoque y empujar la probabilidad a una cota aceptable. En particular, la probabilidad de fallo es demasiado alta cuando hacemos el proceso aleatorio mencionado una sola vez. Para remediarlo, procedemos así:

Primero fijamos $S$ como el número de “simulaciones” que corremos.
Luego, para cada color posible $1 \leq c \leq n$ , definimos $v_{cj}$ como un valor aleatorio independiente en $[0,1]$ , para cada $1 \leq j \leq S$ .
Entonces, construimos $S$ árboles $T_i$ , de la misma estructura que el árbol inicial, pero con $v_{c_u i}$ marcado en un nodo $u$ .
Para cada consulta que compara $a,b,c,d$ , emitimos $\texttt{Yes}$ si

\sum_{i\leq S} \text{PathMin}(T_i,a,b) < \sum_{i\leq S} \text{PathMin}(T_i,c,d)

y $\texttt{No}$ en caso contrario.

Este enfoque debería “combinar” las probabilidades de modo que el evento más probable (el camino con más valores distintos logrando un valor más chico) sea exponencialmente más probable. Para alguna intuición sobre esto, si tiramos una moneda sesgada con probabilidad $\frac{2}{3}$ de cara una vez, hay probabilidad $\frac{1}{3}$ de que salga cruz más que cara. Sin embargo, si la tiramos $99$ veces, la probabilidad de que salga más cruz que cara se vuelve

\sum_{k=50}^{99} \binom{99}{k} \left(\frac{1}{3}\right)^k \left(\frac{2}{3}\right)^{99-k} \approx .000309

Calcular la probabilidad exacta de que nuestro enfoque funcione es más difícil que el ejemplo de la moneda, pero sigue el mismo principio de que el fallo se vuelve exponencialmente más improbable a lo largo de varios ensayos. Podemos usar algunas suposiciones (en particular el teorema central del límite) para calcular una aproximación burda de la probabilidad de éxito. Aquí hay una gráfica de la probabilidad de pasar el problema dado un cierto valor de $S$ . Observar que la probabilidad de éxito se mantiene en gran medida igual a través de distintos conteos de colores distintos a lo largo del camino.

Graph

La gráfica se generó para la probabilidad de responder $4\cdot10^4$ consultas correctamente seguidas. Esta suposición es razonable porque los datos de prueba consisten en un solo caso de prueba grande.

El código Python usado para generar las estimaciones se muestra abajo:


import math
from scipy.stats import norm
 
 
def clt_probability(k, S):
	"""
	Computes the probability that the sum of S minima from 2k random draws
	is less than the sum of S minima from k random draws, as approximated by the CLT.
 
	The CLT approximation is given by:
 
	   P(B<A) ≈ Φ(  (sqrt(S) * [k/((k+1)(2k+1)]) ) / sqrt( k/((k+1)^2(k+2)) + 2k/((2k+1)^2(2k+2)) ) )
 
	:param k: The number of draws for each minimum:
			- The first group uses k draws.
	            	- The second group uses 2k draws.
	:param S: The number of independent trials (sums over S minima).
	:return: The approximated probability that the sum of the minima
		 from 2k draws is less than that from k draws.
	"""
	numerator = math.sqrt(S) * k / ((k + 1) * (2 * k + 1))
 
	var_X = k / (((k + 1) ** 2) * (k + 2))
	var_Y = 2 * k / (((2 * k + 1) ** 2) * (2 * k + 2))
 
	denominator = math.sqrt(var_X + var_Y)
 
	z_score = numerator / denominator
 
	probability = norm.cdf(z_score)
 
	return probability

Implementación

Soportando consultas de camino con HLD, podemos resolver este problema en $\mathcal{O}(S\cdot(n + m\log^2n))$ .


#include "bits/stdc++.h"
using namespace std;
 
using us = unsigned short;
 
const int MAX_N = 5e5 + 1;
const int S = 150;
const us INF = 65535;
 
us va[MAX_N][S];
int n, m, c[MAX_N];
 
namespace SGT {
const int L = 1 << 19;
us seg[2 * L][S];
 
void build() {
	for (int i = L - 1; i; i--) {
		for (int j = 0; j < S; j++) {
			seg[i][j] = min(seg[2 * i][j], seg[2 * i + 1][j]);
		}
	}
}
 
void point_update(int idx, int v) {
	int pos = L + idx;
	for (int j = 0; j < S; j++) { seg[pos][j] = va[v][j]; }
	pos /= 2;
	while (pos) {
		int left = pos * 2, right = left + 1;
		for (int j = 0; j < S; j++) { seg[pos][j] = min(seg[left][j], seg[right][j]); }
		pos /= 2;
	}
}
 
inline us range_min(int l, int r, int j) {
	us res = INF;
	for (l += L, r += L + 1; l < r; l /= 2, r /= 2) {
		if (l & 1) res = min(res, seg[l++][j]);
		if (r & 1) res = min(res, seg[--r][j]);
	}
	return res;
}
}  // namespace SGT
 
namespace HLD {
const int MAX_N = 5e5 + 1;
int f[MAX_N], depth[MAX_N], heavy[MAX_N], head[MAX_N], pos[MAX_N], cp = 0;
vector<int> adj[MAX_N];
 
void clear(int n) {
	for (int i = 0; i < n; i++) { adj[i].clear(); }
	cp = 0;
}
 
void add_edge(int u, int v) {
	adj[u].push_back(v);
	adj[v].push_back(u);
}
 
int dfs(int v) {
	int sz = 1, msz = 0;
	for (int nxt : adj[v]) {
		if (nxt != f[v]) {
			f[nxt] = v;
			depth[nxt] = depth[v] + 1;
 
			int csz = dfs(nxt);
			sz += csz;
			if (csz > msz) {
				msz = csz;
				heavy[v] = nxt;
			}
		}
	}
 
	return sz;
}
 
void decompose(int v, int h) {
	head[v] = h;
	pos[v] = cp++;
	for (int j = 0; j < S; j++) SGT::seg[SGT::L + pos[v]][j] = va[c[v]][j];
	if (heavy[v] != -1) decompose(heavy[v], h);
	for (int nxt : adj[v]) {
		if (nxt == f[v] || nxt == heavy[v]) continue;
		decompose(nxt, nxt);
	}
}
 
inline void init() {
	memset(heavy, -1, sizeof(heavy));
	dfs(0);
	decompose(0, 0);
}
 
us path_min(int a, int b, int j) {
	us res = INF;
	while (head[a] != head[b]) {
		if (depth[head[a]] > depth[head[b]]) swap(a, b);
		res = min(res, SGT::range_min(pos[head[b]], pos[b], j));
		b = f[head[b]];
	}
 
	if (depth[a] > depth[b]) swap(a, b);
	res = min(res, SGT::range_min(pos[a], pos[b], j));
	return res;
}
}  // namespace HLD
 
void solve() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> c[i];
	HLD::clear(n);
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		HLD::add_edge(u, v);
	}
 
	HLD::init();
	SGT::build();
 
	int cnt = 0;
	for (int i = 0; i < m; i++) {
		int tp;
		cin >> tp;
		if (tp == 1) {
			int x, y;
			cin >> x >> y;
			x ^= cnt;
			y ^= cnt;
			SGT::point_update(HLD::pos[x - 1], y);
		} else {
			int a, b, cc, d;
			cin >> a >> b >> cc >> d;
			a ^= cnt, b ^= cnt, cc ^= cnt, d ^= cnt;
			a--, b--, cc--, d--;
 
			long long c1 = 0, c2 = 0;
			for (int j = 0; j < S; j++) {
				c1 += HLD::path_min(a, b, j);
				c2 += HLD::path_min(cc, d, j);
			}
 
			if (c1 < c2) {
				cnt++;
				cout << "Yes\n";
			} else {
				cout << "No\n";
			}
		}
	}
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	mt19937 rng(1434);
	for (int i = 1; i < MAX_N; i++) {
		for (int j = 0; j < S; j++) { va[i][j] = rng() % (INF + 1); }
	}
 
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) { solve(); }
}

Problemas

Algunos de los problemas listados no requieren algoritmos aleatorios como solución, pero se pueden hacer significativamente más fáciles usando algoritmos aleatorios.

Fuente	Nombre	Dificultad	Tags	Solución
MHC	Fall in Line	Fácil	Random	—
CF	Destiny	Normal	Random	—
CF	DZY Loves FFT	Normal	Random	—
CF	Gena and Second Distance	Normal	Random	—