Este documento analiza tres desafíos clásicos de programación competitiva que involucran relaciones de recurrencia en estructuras combinatorias, verificación de consistencia en grafos dirigidos mediante recorridos, y consultas eficientes sobre rangos utilizando árboles persistentes (conocidos comúnmente como "Árbol de Presidente" o Chairman Tree).
- Conteo de Ciclos Disjuntos en Permutaciones
Problema: Dado un número $n$ de elementos y un número $k$ de ciclos, calcular cuántas permutaciones de $n$ elementos constan exactamente de $k$ ciclos disjuntos. Un requisito fundamental es que cada ciclo debe tener una longitud mínima de 3 elementos.
Enfoque Dinámico:
La solución se basa en una relación de recurrencia $dp[i][j]$, donde $i$ representa el número total de elementos considerados hasta ahora y $j$ el número de ciclos formados.
- Caso Base: $dp[0][0] = 1$. Existe una única forma de tener 0 elementos con 0 ciclos.
- Transición: Para construir $dp[i][j]$, podemos añadir el elemento actual $i$ a la estructura existente de dos maneras principales derivadas de la restricción de longitud mínima del ciclo (3):
- Formar un nuevo ciclo de longitud 3: Si el último ciclo añadido tiene exactamente 3 elementos, estamos cerrando ese ciclo. Esto implica seleccionar 2 elementos previos para formar el trío junto con el elemento actual $i$. El número de formas de elegir estos pares depende de las posiciones relativas, pero la lógica combinatoria estándar sugiere multiplicar por los factores de disposición disponibles. En la implementación optimizada observada, esto se modela como $(i-1)(i-2) \times dp[i-3][j-1]$.
- Añadir al último ciclo existente: Si no se cierra un ciclo nuevo, el elemento $i$ puede insertarse dentro del último ciclo abierto. Hay $i-1$ posiciones posibles para insertar este elemento en una secuencia circular previa de tamaño $i-1$. La transición es $(i-1) \times dp[i-1][j]$.
El resultado final es $dp[n][k] \pmod p$.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Matriz de memoria dinámica para n <= 3000, k <= 3000
ll dp[3005][3005];
int main() {
int n, k, mod;
if(scanf("%d%d%d", &n, &k, &mod) != 3) return 0;
dp[0][0] = 1; // Caso base
for (int j = 1; j <= k; ++j) {
// i representa el número de elementos usados
// Empezamos desde 3*j porque cada ciclo requiere mínimo 3 elementos
for (int i = 3 * j; i <= n; ++i) {
ll term1 = 0, term2 = 0;
// Opción 1: Cerrar un ciclo de longitud 3 usando el elemento actual 'i'
// Requerimos que antes tuviéramos i-3 elementos formando j-1 ciclos
if (i - 3 >= 0) {
term1 = (ll)(i - 1) * (i - 2) % mod * dp[i - 3][j - 1] % mod;
}
// Opción 2: Insertar el elemento 'i' en uno de los ciclos existentes
// No aumenta el conteo de ciclos (j permanece igual), pero aumenta i
term2 = (ll)(i - 1) * dp[i - 1][j] % mod;
dp[i][j] = (term1 + term2) % mod;
}
}
printf("%lld\n", dp[n][k]);
return 0;
}
- Validación de Eventos en Grafo Dirigido Acíclico (DAG)
Problema: Dado un grafo dirigido con $N$ nodos y $M$ aristas, y un conjunto $D$ de eventos "fijos" (nodos que deben ocurrir), determinar qué nodos adicionales pueden ser forzados a ocurrir si asumimos que un nodo candidato específico ocurre. Se busca identificar todos los nodos que son consistentes con la hipótesis de que ellos mismos causan la ocurrencia de todos los eventos fijos.
Lógica de Verificación (BFS Bidireccional):
Para un nodo candidato $v$, verificamos su viabilidad mediante dos condiciones lógicas basadas en la propagación de dependencias:
- Propagación hacia atrás (Ancestros):** Si realizamos un BFS inverso desde $v$ (siguiendo aristas entrantes), y alcanzamos algún nodo que está marcado como "fijo" ($a_i \in D$), entonces $v$ es válido. Esto significa que $v$ es un ancestro directo o indirecto de un evento obligatorio, por lo tanto, si $v$ ocurre, el evento obligatorio también puede justificarse.
- **Propagación hacia adelante (Descendientes):** Si no se cumple la condición 1, debemos verificar si activar $v$ permite cubrir todos los eventos fijos restantes a través de sus descendientes.
- Iniciamos un BFS desde todos los nodos fuentes (in-degree 0) que no son ancestros de $v$ (para evitar doble conteo o conflictos lógicos iniciales complejos, aunque la implementación simplificada usa todos los fuentes no visitados).
- Marcamos todos los nodos alcanzables desde estas fuentes.
- Si alguno de los eventos fijos NO ha sido alcanzado en esta segunda pasada, entonces $v$ no es suficiente para explicar la ocurrencia global bajo la premisa de que solo $v$ y las fuentes naturales inician el proceso. Sin embargo, la lógica específica del código proporcionado verifica si existe alguna ruta alternativa.**
Nota: La implementación concreta realiza una comprobación más estricta: Si $v$ no alcanza ningún fijo hacia atrás, se simula el flujo desde todas las fuentes (excluyendo aquellas que ya están "cubiertas" por la influencia de $v$ o simplemente todas las fuentes) y se chequea si algún fijo queda sin visitar. Si queda alguno sin visitar, la hipótesis falla o requiere más nodos. El código dado marca como válidos aquellos $x$ donde $\text{check}(x)$ devuelve true.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<int> adj[MAXN], radj[MAXN];
int fixedNodes[MAXN], isFixed[MAXN];
int visited[MAXN], timestamp = 0;
int N, M, K; // N: nodos, M: aristas, K: cantidad de eventos fijos
void addEdge(int u, int v) {
adj[u].push_back(v);
radj[v].push_back(u);
}
// BFS en grafo original (hacia adelante)
bool bfsForward(int start) {
queue<int> q;
q.push(start);
visited[start] = ++timestamp;
while(!q.empty()) {
int u = q.front(); q.pop();
for(int v : adj[u]) {
if(visited[v] != timestamp) {
visited[v] = timestamp;
q.push(v);
}
}
}
return true; // Helper simple
}
// Verifica si el nodo x es un candidato válido
bool isValidCandidate(int x) {
++timestamp;
queue<int> q;
// Paso 1: Chequeo hacia atrás (ancestros)
q.push(x);
visited[x] = timestamp;
bool foundFixedInBackward = false;
while(!q.empty()) {
int u = q.front(); q.pop();
if(isFixed[u]) foundFixedInBackward = true;
for(int v : radj[u]) {
if(visited[v] != timestamp) {
visited[v] = timestamp;
q.push(v);
}
}
}
// Si x es ancestro de algún evento fijo, es válido inmediatamente
if(foundFixedInBackward) return true;
// Paso 2: Chequeo hacia adelante desde fuentes
// Reiniciamos la visita conceptualmente incrementando timestamp
++timestamp;
// Añadimos todas las fuentes (in-degree 0) que no fueron visitadas en el paso anterior?
// La lógica del código original añade fuentes que NO fueron visitadas en el backward pass.
// Calculamos in-degrees primero o usamos la lista precomputada.
vector<int> sources;
// Nota: En una implementación completa necesitaríamos calcular in-degree.
// Aquí simulamos la lógica: añadir nodos con indegree 0.
// Para brevedad, asumimos que 'deg' fue calculado externamente.
// Lógica simplificada basada en el snippet:
// Si ningún fijo fue encontrado hacia atrás, probamos si cubrimos los fijos hacia adelante
// desde las fuentes naturales.
queue<int> q2;
// En el código original, se iteraba sobre todos los nodos con deg==0
// y si no estaban marcados en la pasada anterior, se añadían.
// Aquí representamos esa intención:
/* Supongamos un array inDeg[] disponible */
for(int i=1; i<=N; ++i) {
if(inDeg[i] == 0 && visited[i] != timestamp - 1) { // No visitado en backward pass
q2.push(i);
visited[i] = timestamp;
}
}
while(!q2.empty()) {
int u = q2.front(); q2.pop();
for(int v : adj[u]) {
if(visited[v] != timestamp) {
visited[v] = timestamp;
q2.push(v);
}
}
}
// Verificar si TODOS los eventos fijos fueron alcanzados en esta segunda pasada
for(int i=0; i<K; ++i) {
if(visited[fixedNodes[i]] != timestamp) {
return false; // Falló cubrir un evento fijo
}
}
return true;
}
int main() {
scanf("%d%d%d", &N, &M, &K);
memset(inDeg, 0, sizeof(inDeg));
memset(isFixed, 0, sizeof(isFixed));
for(int i=0; i<M; ++i) {
int u, v; scanf("%d%d", &u, &v);
addEdge(u, v);
inDeg[v]++;
}
for(int i=0; i<K; ++i) {
scanf("%d", &fixedNodes[i]);
isFixed[fixedNodes[i]] = 1;
}
vector<int> results;
for(int i=1; i<=N; ++i) {
if(isFixed[i] || isValidCandidate(i)) {
results.push_back(i);
}
}
sort(results.begin(), results.end());
for(int val : results) printf("%d ", val);
puts("");
return 0;
}
- Consultas de Máximo Valor en Rango con Árboles Persistentes
Problema: Dada una secuencia de números $A_1, \dots, A_N$ con valores pequeños ($\le 1000$), responder a múltiples consultas. Cada consulta especifica un rango de índices $[l, r]$ y un parámetro $p$. Se debe encontrar el valor máximo posible tal que exista un número en el subarreglo $A[l \dots r]$ cuya diferencia con respecto a un múltiplo de $p$ sea máxima, o más precisamente, según la lógica del código: encontrar la mayor distancia entre un valor presente en el rango y el límite inferior de su bloque de tamaño $p$.
Estructura de Datos: Chairman Tree (Segment Tree Persistente):
Dado que el dominio de valores es pequeño ($V_{max} = 1000$), podemos construir un árbol de segmentos persistante sobre el dominio de los valores, no sobre los índices.
- Construcción: Cada versión $root[i]$ del árbol representa la distribución de frecuencias de los valores encontrados en los primeros $i$ elementos del arreglo. Esto se logra copiando los nodos necesarios de $root[i-1]$ y actualizando la frecuencia del valor $A[i]$.
- Consulta: Para un rango $[l, r]$, la información relevante reside en la diferencia entre $root[r]$ y $root[l-1]$. Queremos maximizar la "distancia residual".
- Iteramos sobre bloques de tamaño $p$: $[0, p-1], [p, 2p-1], \dots$.
- Para cada bloque, preguntamos al árbol persistente si existe algún valor en el rango $[l,r]$ que caiga dentro de ese bloque.
- Si existe, intentamos encontrar el valor más grande dentro de ese bloque presente en el rango. La contribución sería
valor\_encontrado - inicio\_bloque. - Opitmización: Como buscamos el máximo, podemos usar una búsqueda binaria sobre el árbol o una función de descenso recursiva que priorice los hijos derechos (mayores valores) si contienen elementos en el rango deseado.
La función query implementa el descenso por el árbol para encontrar el mayor valor presente en la intersección de versiones. La función solve divide el espacio de valores en bloques de tamaño $p$ y llama a query para cada bloque potencial, manteniendo el máximo global.
#include <bits/stdc++.h>
using namespace std;
const int MAX_VAL = 1000;
const int MAXN = 1000005;
// Arrays para el árbol persistente
int leftChild[MAXN * 20];
int rightChild[MAXN * 20];
int countVal[MAXN * 20];
int rootVersion[MAXN];
int nodeCnt = 0;
// Construir estructura vacía inicial
void build(int &node, int l, int r) {
node = ++nodeCnt;
countVal[node] = 0;
if (l == r) return;
int mid = (l + r) / 2;
build(leftChild[node], l, mid);
build(rightChild[node], mid + 1, r);
}
// Actualizar: crear nueva versión añadiendo 'pos'
void update(int &newNode, int oldNode, int l, int r, int pos) {
newNode = ++nodeCnt;
leftChild[newNode] = leftChild[oldNode];
rightChild[newNode] = rightChild[oldNode];
countVal[newNode] = countVal[oldNode] + 1;
if (l == r) return;
int mid = (l + r) / 2;
if (pos <= mid) {
update(leftChild[newNode], leftChild[oldNode], l, mid, pos);
} else {
update(rightChild[newNode], rightChild[oldNode], mid + 1, r, pos);
}
}
// Búsqueda auxiliar: Encuentra el mayor valor en el rango [L, R] de índices
// que está presente en la diferencia de versiones (rRoot - lRoot)
// y que cae dentro del intervalo de valores [ql, qr]
int findMaxInRange(int lRoot, int rRoot, int ql, int qr, int valL, int valR) {
if (countVal[rRoot] - countVal[lRoot] == 0) return -1; // No hay elementos
if (valL > qr || valR < ql) return -1; // Fuera del rango de interés
if (valL == valR) return valL; // Hoja encontrada
int mid = (valL + valR) / 2;
// Priorizamos buscar en el hijo derecho (valores mayores)
int resRight = findMaxInRange(rightChild[lRoot], rightChild[rRoot], ql, qr, mid + 1, valR);
if (resRight != -1) return resRight;
return findMaxInRange(leftChild[lRoot], leftChild[rRoot], ql, qr, valL, mid);
}
int main() {
int N, Q;
scanf("%d%d", &N, &Q);
// Inicializar raíz 0
build(rootVersion[0], 0, MAX_VAL);
int arr[MAXN];
for (int i = 1; i <= N; ++i) {
scanf("%d", &arr[i]);
update(rootVersion[i], rootVersion[i-1], 0, MAX_VAL, arr[i]);
}
while (Q--) {
int l, r, p;
scanf("%d%d%d", &l, &r, &p);
if (l > r) swap(l, r);
int maxDiff = 0;
// Iterar sobre bloques de tamaño p: [0, p-1], [p, 2p-1], ...
for (int blockStart = 0; blockStart <= MAX_VAL; blockStart += p) {
int blockEnd = min(blockStart + p - 1, MAX_VAL);
// Buscar el mayor valor presente en el rango [l, r] que esté en [blockStart, blockEnd]
int valFound = findMaxInRange(rootVersion[l-1], rootVersion[r], blockStart, blockEnd, 0, MAX_VAL);
if (valFound != -1) {
// La "ganancia" o métrica suele ser la distancia al inicio del bloque
// Según el código original: ans = max(ans, l - L) donde l era el valor encontrado
// y L era el inicio del bloque.
int currentDiff = valFound - blockStart;
if (currentDiff > maxDiff) {
maxDiff = currentDiff;
}
}
// Optimización: Si encontramos un valor que da la máxima diferencia posible (p-1), podemos parar
if (maxDiff == p - 1) break;
}
printf("%d\n", maxDiff);
}
return 0;
}