Búsqueda por fractura

Esquema general

Problema

Supongamos que tenemos un árbol enraizado donde cada vértice $i$ tiene un valor $v_i$. También, si $i$ no es la raíz entonces $i$ tiene un padre $p_i$ que cumple $v_{p_i} \le v_i$. Dado que cada vértice tiene a lo sumo $D$ hijos, hallar los $K$ valores más pequeños del árbol.

Enfoques

Enfoque 1: Usar una cola de prioridad que inicialmente contiene solo la raíz. En cada paso, extraer el vértice con valor más pequeño de la cola de prioridad e insertar todos sus hijos en la cola. Como insertamos $\mathcal{O}(KD)$ vértices en la cola de prioridad, esto corre en $\mathcal{O}(KD\log (KD))$. Se puede pensar en esto como Dijkstra sobre un árbol.

Enfoque 2: Supongamos que sabemos que el $K$-ésimo valor más pequeño es un entero en el rango $[0,A]$. Entonces para cualquier $x\in [0,A]$ podemos comprobar si hay menos de $K$ valores en el árbol menores o iguales que $x$ en $\mathcal{O}(KD)$ con un DFS simple que se corta una vez que se encuentran $K$ valores. Este enfoque corre en $\mathcal{O}(KD\log A)$.

Nos enfocaremos en el primer enfoque.

Generalizar

Supongamos que queremos hallar los $K$ objetos con los valores más pequeños en algún espacio de búsqueda (potencialmente muy grande).

• Primero, necesitamos imponer una estructura de árbol que cumpla las propiedades mencionadas arriba. Decimos que $b$ está en el subárbol de $a$ si $a$ está por encima de (o es igual a) $b$ en el árbol.
• Sea la “raíz” el objeto de valor más pequeño. Todo objeto debe estar en el subárbol de la raíz.
• Los hijos de la raíz deberían particionar todo el espacio de búsqueda (salvo la raíz) en un número acotado de subespacios disjuntos.
• Por supuesto, cada hijo también debería tener el valor más pequeño de su subárbol.

Esencialmente, empezamos con todo el espacio de búsqueda y luego lo fracturamos en subespacios según los hijos de la raíz. Luego podemos terminar con cualquiera de los dos enfoques.

$K$-ésimo árbol de expansión más pequeño (USACO Camp 2018)

Veamos un ejemplo.

Problema

Dado un grafo con $N\le 50$ vértices y a lo sumo $\binom{N}{2}$ aristas, hallar el $K$-ésimo ($K\le 10^4$) árbol de expansión más pequeño.

Solución

Video (de tehqin) 

Para este problema, los objetos son árboles de expansión. La raíz es el árbol de expansión mínima (que se puede calcular con el algoritmo de Kruskal), y contiene todos los objetos en su subárbol.

La idea es designar un número pequeño de hijos de la raíz, cada uno de los cuales debería formarse modificando la raíz ligeramente. Si de alguna forma podemos asegurar que cada objeto tiene a lo sumo $N$ “hijos” entonces solo necesitamos considerar $\mathcal{O}(NK)$ árboles de expansión para hallar el $K$-ésimo más pequeño.

El primer paso es considerar el problema más fácil de hallar el segundo MST. Para hacer esto, podemos elegir excluir una arista del MST y luego hallar el reemplazo más pequeño posible para ella. Sean las aristas del MST etiquetadas $1\ldots N-1$. Entonces una idea es dejar que el $i$-ésimo subespacio hijo de la raíz consista en todos los árboles de expansión que no incluyen la arista $i$ del árbol de expansión mínima para cada $i\in [1,N-1]$.

Por desgracia, esto no funciona porque los subespacios hijos se solapan. En cambio, podemos dejar que el $i$-ésimo subespacio hijo contenga todos los árboles de expansión que

• incluyen las primeras $i-1$ aristas del MST
• no incluyen la $i$-ésima arista del MST

para cada $i\in [1,N-1]$. Todo árbol de expansión distinto de la raíz está contenido en exactamente uno de estos subespacios hijos, que es lo que queremos. Después de ordenar las aristas en orden creciente de peso una vez, podemos calcular el MST dentro de cada subespacio hijo en $\mathcal{O}(M\alpha (N))$ con DSU.

En total, el tiempo de ejecución es $\mathcal{O}(NMK\alpha(N))$ para guardar la información de cada árbol de expansión y $\mathcal{O}(NK\log (NK))$ para mantener la cola de prioridad de objetos de modo que podamos extraer el mínimo. Observar que con el segundo enfoque mencionado en la primera sección el tiempo de ejecución sería $\mathcal{O}(NMK\alpha(N)\log ans)$, que puede ser demasiado lento.

#include <bits/stdc++.h>
using namespace std;
typedef bitset<1225> B;
typedef vector<int> vi;
 
struct DSU {  // for Kruskal's
	vi e;
	void init(int n) { e = vi(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;
	}
};
 
int N, M, K;
vector<array<int, 3>> ed;
 
struct Partition {
	B ban;
	vi span;
	int wei = 0,
	    fix = 0;  // "fix" smallest edges must be contained in spanning tree
	Partition(B _ban, int _fix) : ban(_ban), fix(_fix) {
		DSU D;
		D.init(N);  // now find MST within subspace
		for (int i = 0; i < M; ++i)
			if (!ban[i] && D.unite(ed[i][1], ed[i][2]))
				span.push_back(i),
				    wei += ed[i][0];  // run Kruskal's ignoring banned edges
	}
};
bool operator<(const Partition &l, const Partition &r) {
	return l.wei > r.wei;
}  // for pq
 
int main() {
	cin >> N >> M >> K;
	for (int i = 0; i < M; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		ed.push_back({c, a - 1, b - 1});
	}
	sort(begin(ed), end(ed));
	priority_queue<Partition> pq;
	pq.push({B(), 0});  // start with MST
	for (int i = 1; i <= K; ++i) {
		if (!pq.size()) {
			cout << "-1\n";
			exit(0);
		}
		auto a = pq.top();
		pq.pop();
		assert(a.span.size() == N - 1);
		if (i == K) {
			cout << a.wei << "\n";
			exit(0);
		}  // print K-th smallest
		while (a.fix < a.span.size()) {  // insert O(N) children
			B t = a.ban;
			t[a.span[a.fix]] = 1;
			auto A = Partition(t, a.fix);
			if (A.span.size() == N - 1) pq.push(A);
			a.fix++;
		}
	}
}

Robotic Cow Herd

Como en el análisis, para cada ubicación se debería

• ordenar los controladores de esa ubicación por costo
• agregar el controlador de costo mínimo de cada ubicación al costo del robot más barato
• restar ese costo mínimo de cada controlador de esa ubicación (así ahora el controlador de costo mínimo de cada ubicación es simplemente cero)

Importante: luego deberíamos ordenar las ubicaciones por sus respectivos costos de segundo controlador mínimo.

Enfoque 1

Hacer búsqueda binaria sobre el costo $c$ del $K$-ésimo robot. Si podemos calcular los costos de todos los robots con costo a lo sumo $c$ o decir que hay más de $K$ en $\mathcal{O}(K)$, entonces podemos resolver este problema en $\mathcal{O}(N\log N+K\log \max(c))$ (similar al “Enfoque 2” de arriba). Este es el enfoque que toma la primera solución del análisis, aunque incluye un factor $\log N$ extra debido a upper_bound. Lo he quitado en mi solución de abajo.

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll, ll> pl;
 
#define f first
#define s second
 
int N, K;
ll tot;  // sum of cheapest
vector<vi> v;
 
ll mx;
ll res;
int num;
 
void dfs(int pos, ll cur, int id) {
	if (cur > mx || num == K) return;
	res += cur;
	num++;
	if (id + 1 < v[pos].size()) dfs(pos, cur + v[pos][id + 1] - v[pos][id], id + 1);
	for (int i = pos + 1; i < v.size(); ++i) {
		ll CUR = cur + v[i][1];
		if (num == K || CUR > mx) break;
		dfs(i, CUR, 1);
	}
}
 
void get() {
	res = num = 0;
	dfs(0, tot, 0);
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	freopen("roboherd.in", "r", stdin);
	freopen("roboherd.out", "w", stdout);
	cin >> N >> K;
	for (int i = 0; i < N; ++i) {
		int m;
		cin >> m;
		vi p(m);
		for (int &x : p) cin >> x;
		sort(begin(p), end(p));
		tot += p[0];
		for (int j = m - 1; j >= 0; --j) p[j] -= p[0];
		if (p.size() > 1) v.push_back(p);
	}
	sort(begin(v), end(v));  // sort by second-cheapest
	ll lo = 0, hi = 1e13;
	while (lo < hi) {
		mx = (lo + hi + 1) / 2;
		get();
		if (num < K) lo = mx;
		else hi = mx - 1;
	}
	mx = lo;
	get();
	cout << res + (K - num) * (mx + 1) << "\n";
}

Enfoque 2

También hay una solución $\mathcal{O}(N\log N+K\log K)$ con una cola de prioridad que construye los robots en orden creciente de costo. Como antes, queremos que cada robot tenga un número acotado de robots “hijos”. Sin embargo, si se mira mi función DFS de arriba, parece que cada robot puede tener hasta $N$ hijos. No obstante, el DFS toma $\mathcal{O}(K)$ en lugar de $\mathcal{O}(KN)$ debido al break, que funciona porque ordenamos por el segundo robot más barato.

De hecho, podemos modificar la función DFS de modo que cada robot tenga a lo sumo tres hijos en lugar de $N$.

void dfs(int pos, ll cur, int id) {
	if (cur > mx || num == K) return;
	res += cur;
	num++;
	if (id + 1 < v[pos].size()) dfs(pos, cur + v[pos][id + 1] - v[pos][id], id + 1);
	if (pos + 1 < v.size()) {
		if (id == 1) dfs(pos + 1, cur - v[pos][1] + v[pos + 1][1], 1);
		if (id) dfs(pos + 1, cur + v[pos + 1][1], 1);
	}
}

Ahora describiré cómo funciona la solución con cola de prioridad:

Primero empezamos con el robot de costo mínimo. El robot de segundo costo mínimo se puede formar simplemente eligiendo el segundo controlador mínimo para la primera ubicación. Después de esto, tenemos algunas opciones:

• Podemos elegir el tercer controlador mínimo para la primera ubicación.
• Podemos descartar el segundo controlador mínimo para la primera ubicación y seleccionar el segundo controlador mínimo para la segunda ubicación (y no volver a cambiar el controlador seleccionado para la primera ubicación).
• Podemos mantener el segundo controlador mínimo para la primera ubicación y seleccionar el segundo controlador mínimo para la segunda ubicación (y no volver a cambiar el controlador seleccionado para la primera ubicación).

Ninguna de estas opciones puede resultar en un robot de menor costo. En general, supongamos que tenemos un robot y estamos seleccionando actualmente el $j$-ésimo controlador más barato para la $i$-ésima ubicación. Entonces las transiciones son las siguientes:

• Seleccionar el $(j+1)$-ésimo controlador más barato para la $i$-ésima ubicación en su lugar.
• Si $j=2$, seleccionar el $1$-er controlador más barato para la $i$-ésima ubicación en su lugar y también seleccionar el $2$-do controlador más barato para la $(i+1)$-ésima.
• Mantener el $j$-ésimo controlador más barato para la $i$-ésima ubicación y también seleccionar el $2$-do controlador más barato para la $(i+1)$-ésima.

Como existe exactamente una forma de ir del robot más barato a cada robot posible, podemos usar una cola de prioridad.

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef pair<ll, pi> T;
 
#define f first
#define s second
 
int N, K;
ll tot;  // sum of cheapest
vector<vi> v;
priority_queue<T, vector<T>, greater<T>> pq;
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	freopen("roboherd.in", "r", stdin);
	freopen("roboherd.out", "w", stdout);
	cin >> N >> K;
	for (int i = 0; i < N; ++i) {
		int m;
		cin >> m;
		vi p(m);
		for (int &x : p) cin >> x;
		sort(begin(p), end(p));
		tot += p[0];
		for (int j = m - 1; j >= 0; --j) p[j] -= p[0];
		if (p.size() > 1) v.push_back(p);
	}
	sort(begin(v), end(v));  // sort by second-cheapest
	pq.push({0, {0, 0}});
	ll ans = 0;
	for (int i = 0; i < K; ++i) {
		auto a = pq.top();
		pq.pop();
		ans += tot + a.f;
		int pos = a.s.f, id = a.s.s;
		if (id + 1 < v[pos].size())
			pq.push({a.f + v[pos][id + 1] - v[pos][id], {pos, id + 1}});
		if (pos + 1 < v.size()) {
			if (id == 1) pq.push({a.f - v[pos][1] + v[pos + 1][1], {pos + 1, 1}});
			if (id) pq.push({a.f + v[pos + 1][1], {pos + 1, 1}});
		}
	}
	cout << ans << "\n";
}

Otros problemas