En el concurso CSP-S 2019, se presentaron problemas algorítmicos variados. A continuación, se detallan las soluciones para varios de ellos, con implementaciones en C++ y explicaciones técnicas.
Día 1, Problema 1: Código de Gray
El código de Gray es una secuencia cíclica de cadenas binarias de n bits donde cada elemento consecutivo difiere en exactamente un bit. Su generación es recursiva: para n=1, la secuencia es [0,1]. Para n+1, la primera mitad se obtiene de la secuencia de n bits con un prefijo 0, y la segunda mitad se obtiene de la secuencia inversa de n bits con un prefijo 1.
Problema: Dados n y k (0 ≤ k < 2^n), hallar la k-ésima cadena en el código de Gray de n bits.
Solución: Se puede emplear un enfoque basado en la posición, similar a la expansión de Cantor. Se procesan los bits desde el más significativo. Si k ≥ 2^{n-1}, el primer bit es 1 y se ajusta k restando 2^{n-1}, invirtiendo el orden para los bits restantes; de lo contrario, el primer bit es 0. Se repite para cada bit.
Implementación en C++ con cambio de nombres de variables y estructura:
#include <bits>
using namespace std;
typedef unsigned long long ull;
int main() {
int dim;
ull pos;
cin >> dim >> pos;
vector<int> resultado(dim);
ull mitad = 1ULL << (dim - 1);
for (int idx = dim - 1; idx >= 0; --idx) {
if ((pos >> idx) & 1) {
resultado[idx] = 1;
pos = (mitad << 1) - pos - 1;
} else {
resultado[idx] = 0;
}
}
for (int idx = dim - 1; idx >= 0; --idx) {
cout << resultado[idx];
}
cout << endl;
return 0;
}
</int></bits>
Día 1, Problema 2: Árbol de Paréntesis
Dado un árbol con raíz donde cada nodo contiene '(' o ')', sea s(i) la cadena formada por los caracteres en el camino de la raíz al nodo i. Sea k(i) el número de subcadenas de paréntesis válidas y distintas en s(i). Calcular la suma XOR de i * k(i) para todo i.
Solución: Usar DFS con una pila para rastrear paréntesis. Definir finpos[i] como el número de subcadenas válidas que terminan en i. Si el nodo actual es '(', se apila; si es ')' y la pila no está vacía, se desapila y se calcula finpos basado en el padre del nodo desapilado. La suma acumulada g[i] se calcula durante DFS.
Implementación en C++ con variables renombradas y ligeras modificaciones:
#include <bits>
using namespace std;
const int MAX_N = 500010;
int n, ancestro[MAX_N], finpos[MAX_N];
long long g[MAX_N];
stack<int> pila;
vector<int> descendientes[MAX_N];
char simbolo[MAX_N];
void dfs(int v) {
bool apilado = false;
int anterior = 0;
if (simbolo[v] == '(') {
pila.push(v);
apilado = true;
} else if (!pila.empty()) {
finpos[v] = finpos[ancestro[pila.top()]] + 1;
anterior = pila.top();
pila.pop();
}
g[v] = g[ancestro[v]] + finpos[v];
for (int hijo : descendientes[v]) {
dfs(hijo);
}
if (apilado && pila.top() == v) {
pila.pop();
}
if (anterior) {
pila.push(anterior);
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> simbolo[i];
}
for (int i = 2; i <= n; ++i) {
cin >> ancestro[i];
descendientes[ancestro[i]].push_back(i);
}
finpos[1] = 0;
g[1] = 0;
dfs(1);
long long res = 0;
for (int i = 1; i <= n; ++i) {
res ^= (i * g[i]);
}
cout << res << endl;
return 0;
}
</int></int></bits>
Día 1, Problema 3: Números en el Árbol
Dado un árbol de n nodos donde cada nodo tiene un número único de 1 a n, realizar exactamente n-1 operaciones de eliminación de bordes. En cada operación, elegir un borde no eliminado, intercambiar los números en sus extremos y eliminar el borde. Al final, ordenar los números 1 a n según los nodos donde se encuentran para obtener una permutación. Hallar la permutación lexicográficamente mínima posible.
Solución: Usar un enfoque voraz. Para cada número i de 1 a n, determinar si se puede mover a un nodo objetivo manteniendo las restricciones de orden de eliminación. Modelar las restricciones como un grafo donde los nodos representan bordes, y usar DFS para verificar factibilidad.
Implementación en C++ con cambios en estructura y variables:
#include <bits>
using namespace std;
const int MAX_N = 2010;
int n, ubicacion[MAX_N], cabeza[MAX_N], contador;
struct Arco {
int destino, siguiente;
} arco[MAX_N << 1];
struct GrafoNodo {
int primero, ultimo, total, conjunto[MAX_N];
bool entrante[MAX_N], saliente[MAX_N];
void limpiar() { primero = ultimo = total = 0; for (int i = 1; i <= n; ++i) conjunto[i] = i, entrante[i] = saliente[i] = 0; }
int encontrar(int x) { return x == conjunto[x] ? x : conjunto[x] = encontrar(conjunto[x]); }
} grafos[MAX_N];
void agregar(int u, int v) {
arco[++contador].destino = v; arco[contador].siguiente = cabeza[u]; cabeza[u] = contador; grafos[u].total++;
arco[++contador].destino = u; arco[contador].siguiente = cabeza[v]; cabeza[v] = contador; grafos[v].total++;
}
int dfs1(int u, int borde_entrante) {
int res = n + 1;
if (borde_entrante && (!grafos[u].ultimo || grafos[u].ultimo == borde_entrante)) {
if (!grafos[u].saliente[borde_entrante] && !(grafos[u].primero && grafos[u].total > 1 && grafos[u].encontrar(borde_entrante) == grafos[u].encontrar(grafos[u].primero)))
res = u;
}
for (int i = cabeza[u]; i; i = arco[i].siguiente) {
int v = arco[i].destino, borde_actual = i / 2;
if (borde_entrante == borde_actual) continue;
if (!borde_entrante) {
if (!grafos[u].primero || grafos[u].primero == borde_actual) {
if (grafos[u].entrante[borde_actual]) continue;
if (grafos[u].ultimo && grafos[u].total > 1 && grafos[u].encontrar(borde_actual) == grafos[u].encontrar(grafos[u].ultimo))
continue;
res = min(res, dfs1(v, borde_actual));
}
} else {
if (borde_entrante == grafos[u].ultimo || borde_actual == grafos[u].primero || grafos[u].encontrar(borde_entrante) == grafos[u].encontrar(borde_actual))
continue;
if (grafos[u].saliente[borde_entrante] || grafos[u].entrante[borde_actual]) continue;
if (grafos[u].primero && grafos[u].ultimo && grafos[u].total > 2 && grafos[u].encontrar(borde_entrante) == grafos[u].encontrar(grafos[u].primero) && grafos[u].encontrar(borde_actual) == grafos[u].encontrar(grafos[u].ultimo))
continue;
res = min(res, dfs1(v, borde_actual));
}
}
return res;
}
int dfs2(int u, int borde_entrante, int destino) {
if (u == destino) { grafos[u].ultimo = borde_entrante; return 1; }
for (int i = cabeza[u]; i; i = arco[i].siguiente) {
int v = arco[i].destino, borde_actual = i / 2;
if (borde_entrante != borde_actual) {
if (dfs2(v, borde_actual, destino)) {
if (!borde_entrante) grafos[u].primero = borde_actual;
else {
grafos[u].saliente[borde_entrante] = grafos[u].entrante[borde_actual] = 1; grafos[u].total--;
grafos[u].conjunto[grafos[u].encontrar(borde_entrante)] = grafos[u].encontrar(borde_actual);
}
return 1;
}
}
}
return 0;
}
int main() {
int casos;
cin >> casos;
while (casos--) {
contador = 1; memset(cabeza, 0, sizeof(cabeza));
cin >> n;
for (int i = 1; i <= n; ++i) grafos[i].limpiar(), cin >> ubicacion[i];
for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; agregar(u, v); }
if (n == 1) { cout << "1\n"; continue; }
int objetivo;
for (int i = 1; i <= n; ++i) {
objetivo = dfs1(ubicacion[i], 0); dfs2(ubicacion[i], 0, objetivo);
cout << objetivo << " ";
}
cout << "\n";
}
return 0;
}
</bits>
Día 2, Problema 1: Comida de Emiya Hoy
Hay n métodos de cocina y m ingredientes. Para el método i y ingrediente j, hay a_{i,j} platos. Una selección de k platos debe cumplir: k ≥ 1, cada método usado a lo sumo una vez, y cada ingrediente usado a lo sumo ⌊k/2⌋ veces. Contar el número de selecciones válidas módulo 998244353.
Solución: Usar inclusión-exclusión. Primero, calcular el número total de selecciones sin la restricción de ingredientes con DP. Luego, para cada ingrediente, calcular el número de selecciones donde ese ingrediente se usa más de la mitad de las veces, y restar. Optimizar usando la diferencia entre 2k - j para reducir la dimensionalidad.
Implementación en C++ con cambios en nombres y lógica:
#include <bits>
using namespace std;
const int MAX_N = 110, MAX_M = 2010;
const long long MOD = 998244353;
int n, m;
long long plato[MAX_N][MAX_M], total[MAX_N], dp[MAX_N << 1];
void sumar_mod(long long &a, long long b) {
a = (a + b) % MOD;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> plato[i][j];
sumar_mod(total[i], plato[i][j]);
}
}
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = i; j >= 1; --j) {
sumar_mod(dp[j], dp[j-1] * total[i] % MOD);
}
}
long long ans = 0;
for (int i = 1; i <= n; ++i) {
sumar_mod(ans, dp[i]);
}
for (int ing = 1; ing <= m; ++ing) {
memset(dp, 0, sizeof(dp));
dp[n] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n + i; ++j) {
long long temp = dp[j];
sumar_mod(temp, dp[j+1] * (total[i] - plato[i][ing] + MOD) % MOD);
sumar_mod(temp, dp[j-1] * plato[i][ing] % MOD);
dp[j] = temp;
}
}
for (int i = n + 1; i <= n * 2; ++i) {
sumar_mod(ans, MOD - dp[i]);
}
}
cout << ans % MOD << endl;
return 0;
}
</bits>
Día 2, Problema 2: Partición
Dada una secuencia de n números a_i, particionarla en segmentos contiguos no vacíos tal que la suma de cada segmento sea no decreciente, y minimizar la suma de los cuadrados de las sumas de los segmentos.
Solución: DP con optimización. Definir dp[i] como el costo mínimo para los primeros i elementos, con el último segmento terminando en i. La transición considera el último punto de corte j, con la condición de que la suma del segmento anterior no exceda la del actual. Se puede usar una cola monótona para optimizar a O(n) dado el crecimiento de las sumas.
Implementación en C++ con cambios en estructura y variables:
#include <bits>
using namespace std;
const int MAX_N = 40000010;
int n, tipo, cola[MAX_N];
long long arr[MAX_N], dp[MAX_N], anterior[MAX_N];
long long calcular(int x) {
return arr[x] * 2 - arr[anterior[x]];
}
int main() {
cin >> n >> tipo;
if (tipo == 0) {
for (int i = 1; i <= n; ++i) cin >> arr[i];
} else {
long long x, y, z;
cin >> x >> y >> z;
int semilla[2], m;
cin >> semilla[0] >> semilla[1] >> m;
vector<int> posiciones(m), limites_bajo(m), limites_alto(m);
for (int i = 0; i < m; ++i) cin >> posiciones[i] >> limites_bajo[i] >> limites_alto[i];
int ahora = 0;
for (int i = 1; i <= n; ++i) {
while (ahora < m && posiciones[ahora] < i) ahora++;
if (i <= 2) arr[i] = semilla[i-1] % (limites_alto[ahora] - limites_bajo[ahora] + 1) + limites_bajo[ahora];
else {
semilla[0] ^= semilla[1] ^= (semilla[0] = (y * semilla[0] + x * semilla[1] + z) % (1 << 30)) ^= semilla[1];
arr[i] = semilla[1] % (limites_alto[ahora] - limites_bajo[ahora] + 1) + limites_bajo[ahora];
}
}
}
for (int i = 1; i <= n; ++i) arr[i] += arr[i-1];
int izquierda = 0, derecha = 0;
for (int i = 1; i <= n; ++i) {
while (izquierda < derecha && calcular(cola[izquierda+1]) <= arr[i]) izquierda++;
anterior[i] = cola[izquierda];
while (izquierda < derecha && calcular(cola[derecha]) >= calcular(i)) derecha--;
cola[++derecha] = i;
}
__int128 res = 0;
int cnt = 0;
while (n > 0) {
res += (__int128)(arr[n] - arr[anterior[n]]) * (arr[n] - arr[anterior[n]]);
n = anterior[n];
}
while (res) {
cola[++cnt] = res % 10;
res /= 10;
}
for (int i = cnt; i >= 1; --i) cout << cola[i];
if (cnt == 0) cout << "0";
cout << endl;
return 0;
}
</int></bits>
Día 2, Porblema 3: Centroide del Árbol
Dado un árbol de n nodos, para cada borde eliminado, calcular la suma de los índices de los centroides de los dos subárboles resultantes. El centroide es el nodo cuya eliminación deja subárboles de tamaño a lo sumo ⌊n/2⌋.
Solución: Usar propiedades del centroide y DP con cambio de raíz. El centroide seimpre está en la cadena pesada. Implementar búsqueda binaria en la cadena pesada con preprocesamiento para saltos, logrando O(n log n).
Implementación en C++ con cambios en nombres y estructura:
#include <bits>
using namespace std;
const int MAX_N = 300010, LOG = 25;
struct Arco {
int destino, siguiente;
} arcos[MAX_N << 1];
int cabeza[MAX_N], contador, n, tamano[MAX_N], salto[MAX_N][LOG], hijo_pesado[MAX_N], padre[MAX_N];
long long respuesta;
void precalcular_saltos(int v) {
for (int i = 1; i < LOG; ++i) salto[v][i] = salto[salto[v][i-1]][i-1];
}
void calcular_centroide(int raiz) {
int u = raiz;
for (int i = LOG-2; i >= 0; --i) {
if (salto[u][i] && tamano[salto[u][i]] * 2 >= tamano[raiz]) u = salto[u][i];
}
if (tamano[u] * 2 == tamano[raiz]) respuesta += padre[u];
respuesta += u;
}
void dfs1(int v, int p) {
padre[v] = p; tamano[v] = 1; hijo_pesado[v] = 0;
for (int i = cabeza[v]; i; i = arcos[i].siguiente) {
int hijo = arcos[i].destino;
if (hijo == p) continue;
dfs1(hijo, v); tamano[v] += tamano[hijo];
if (tamano[hijo] > tamano[hijo_pesado[v]]) hijo_pesado[v] = hijo;
}
salto[v][0] = hijo_pesado[v]; precalcular_saltos(v);
}
void dfs2(int v, int p) {
int max1 = 0, max2 = 0;
for (int i = cabeza[v]; i; i = arcos[i].siguiente) {
int hijo = arcos[i].destino;
if (tamano[hijo] >= tamano[max1]) { max2 = max1; max1 = hijo; }
else if (tamano[hijo] >= tamano[max2]) max2 = hijo;
}
for (int i = cabeza[v]; i; i = arcos[i].siguiente) {
int hijo = arcos[i].destino;
if (hijo == p) continue;
calcular_centroide(hijo); salto[v][0] = (hijo == max1) ? max2 : max1; precalcular_saltos(v);
tamano[v] -= tamano[hijo]; tamano[hijo] += tamano[v];
calcular_centroide(v); padre[v] = hijo; dfs2(hijo, v);
tamano[hijo] -= tamano[v]; tamano[v] += tamano[hijo];
}
salto[v][0] = hijo_pesado[v]; precalcular_saltos(v); padre[v] = p;
}
void agregar(int u, int v) {
arcos[++contador].destino = v; arcos[contador].siguiente = cabeza[u]; cabeza[u] = contador;
arcos[++contador].destino = u; arcos[contador].siguiente = cabeza[v]; cabeza[v] = contador;
}
int main() {
int casos;
cin >> casos;
while (casos--) {
memset(tamano, 0, sizeof(tamano)); memset(hijo_pesado, 0, sizeof(hijo_pesado));
memset(salto, 0, sizeof(salto)); memset(padre, 0, sizeof(padre)); respuesta = 0;
memset(cabeza, 0, sizeof(cabeza)); contador = 0;
cin >> n;
for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; agregar(u, v); }
dfs1(1, 0); dfs2(1, 0);
cout << respuesta << "\n";
}
return 0;
}
</bits>