El Concurso Internacional de Programación Colegiada (ICPC) 2023 en la sede de Jinan presentó un conjunto de problemas de alta exigencia técnica. A continuación, se detalla el análisis algorítmico y las implementaciones optimizadas para los problemas más destacados de la competencia.
Problema D: Búsqueda del Dígito Máximo
Este problema actúa como una introducción al concurso. La tarea consiste en encontrar el valor del dígito más alto en un rango de suma definido por $[L_1+L_2, R_1+R_2]$. Dado que el sistema decimal tiene un rango limitado de dígitos (0-9), si la diferencia entre el límite superior e inferior del rango excede 10, es matemáticamente seguro que el dígito 9 estará presente. En casos donde el rango es menor o igual a 10, se puede realizar una iteración exhaustiva sin penalización de tiempo.
#include <iostream>
#include <algorithm>
using namespace std;
int extract_max_digit(long long value) {
int highest = 0;
while (value > 0) {
highest = max(highest, (int)(value % 10));
value /= 10;
}
return highest;
}
void process_test_case() {
long long l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
long long lower_bound = l1 + l2;
long long upper_bound = r1 + r2;
if (upper_bound - lower_bound > 10) {
cout << 9 << "\n";
return;
}
int max_found = 0;
for (long long current = lower_bound; current <= upper_bound; ++current) {
max_found = max(max_found, extract_max_digit(current));
}
cout << max_found << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int test_cases;
if (cin >> test_cases) {
while (test_cases--) process_test_case();
}
return 0;
}
Problema I: Ordenamiento de Intervalos por Estrategia Greedy
La solución óptima se basa en una estrategia voraz (greedy). Recorriendo el arreglo de izquierda a derecha, al detectar un elemento $a_i \neq i$, se debe localizar el eelmento más a la derecha que sea estrictamente menor que $a_i$. Al ordenar este subarreglo, se garantiza la corrección de al menos dos posiciones por operación, cumpliendo holgadamente con el límite de $\lfloor n/2 \rfloor$ operaciones permitidas.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> arr(n + 1);
for (int i = 1; i <= n; ++i) cin >> arr[i];
vector<pair<int, int>> operations;
for (int i = 1; i <= n; ++i) {
if (arr[i] == i) continue;
for (int j = n; j > i; --j) {
if (arr[j] < arr[i]) {
operations.push_back({i, j});
sort(arr.begin() + i, arr.begin() + j + 1);
break;
}
}
}
cout << operations.size() << "\n";
for (auto& op : operations) {
cout << op.first << " " << op.second << "\n";
}
}
int main() {
int t; cin >> t;
while (t--) solve();
return 0;
}
Problema A: Validación de Secuencias de Paréntesis
El problema modela secuencias anidadas que denominaremos "picos", los cuales requieren una alternancia estricta de tipos de paréntesis (por ejemplo, ([])). Una secuencia es válida si contiene como máximo dos picos independientes. Cualquier configuración con tres picos, o múltiples picos anidados bajo un mismo tipo de paréntesis, permite transformaciones que invalidan la unicidad de la estructura. La validación se reduce a normalizar los caracteres de cierre a sus respectivas aperturas y contar las transiciones donde paréntesis adyacentes comparten el mismo tipo. El límite permitido de tales adyacencias es dos.
#include <iostream>
#include <string>
using namespace std;
void evaluate_sequence() {
string seq;
cin >> seq;
int n = seq.length();
for (int i = 0; i < n; ++i) {
if (seq[i] == ')') seq[i] = '(';
else if (seq[i] == ']') seq[i] = '[';
}
int adjacent_matches = 0;
for (int i = 0; i < n - 1; ++i) {
if (seq[i] == seq[i + 1]) {
adjacent_matches++;
}
}
if (adjacent_matches > 2) cout << "No\n";
else cout << "Yes\n";
}
int main() {
int t; cin >> t;
while (t--) evaluate_sequence();
return 0;
}
Problema G: Coloreo de Grafos Bipartitos
Las restricciones de filas y columnas se modelan como un problema de satisfacibilidad booleana que se resuelve mediante coloreo de grafos bipartitos. Cada fila se divide en dos nodos representando sus estados posibles: "invertida" y "normal". Las columnas que poseen el mismo valor en múltiples filas dictan las aristas del grafo. Si dos filas comparten un '1' en la misma columna, sus estados deben diferir. Si comparten un '1' en columnas simétricas, sus estados deben ser idénticos. El número total de configuraciones válidas es $2^c$, donde $c$ es el número de componentes conexos en el grafo bipartito construido.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int MOD = 998244353;
bool dfs_color(int node, int color, vector<int>& color_state, const vector<vector<int>>& adj) {
color_state[node] = color;
for (int neighbor : adj[node]) {
if (color_state[neighbor] == color) return false;
if (color_state[neighbor] == 0) {
if (!dfs_color(neighbor, 3 - color, color_state, adj)) return false;
}
}
return true;
}
void solve() {
int n, m;
cin >> n >> m;
vector<vector<int>> cols(m + 1);
for (int i = 1; i <= n; ++i) {
string row;
cin >> row;
for (int j = 0; j < m; ++j) {
if (row[j] == '1') cols[j + 1].push_back(i);
}
}
if (m % 2 != 0 && cols[m / 2 + 1].size() > 1) {
cout << 0 << "\n"; return;
}
vector<vector<int>> adj(2 * n + 1);
for (int i = 1; i <= n; ++i) {
adj[i].push_back(i + n);
adj[i + n].push_back(i);
}
bool invalid = false;
for (int j = 1; j <= m / 2; ++j) {
int sym = m + 1 - j;
if (cols[j].size() + cols[sym].size() > 2) { invalid = true; break; }
if (cols[j].size() + cols[sym].size() < 2) continue;
if (cols[j].size() == 1) {
int u = cols[j][0], v = cols[sym][0];
if (u != v) {
adj[u].push_back(v + n); adj[v + n].push_back(u);
adj[v].push_back(u + n); adj[u + n].push_back(v);
}
} else {
int u = cols[j].empty() ? cols[sym][0] : cols[j][0];
int v = cols[j].size() < 2 ? cols[sym][1] : cols[j][1];
adj[u].push_back(v); adj[v].push_back(u);
adj[u + n].push_back(v + n); adj[v + n].push_back(u + n);
}
}
if (invalid) { cout << 0 << "\n"; return; }
vector<int> color_state(2 * n + 1, 0);
long long ways = 1;
for (int i = 1; i <= 2 * n; ++i) {
if (color_state[i] == 0) {
if (!dfs_color(i, 1, color_state, adj)) { ways = 0; break; }
ways = (ways * 2) % MOD;
}
}
cout << ways << "\n";
}
int main() {
int t; cin >> t;
while (t--) solve();
return 0;
}
Problema K: Ventana Deslizante y Estructura de Datos para la Mediana
Aplicando una transformación matemática $a_i \leftarrow a_i - i$, el problema se reduce a encontrar el subarreglo más largo donde todos los elementos puedan igualarse con un costo total menor o igual a $k$. El costo óptimo para igualar un conjunto de números se alcanza ajustándolos a su mediana. Se emplea una estructura de datos basada en dos árboles de búsqueda balanceada (std::multiset en C++) para mantener la mitad inferior y superior de los valores dinámicamente. Un algoritmo de dos punteros (two pointers) expande y contrae la ventana, garantizando una complejidad de $O(n \log n)$.
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const long long INF = 1e18;
struct MedianTracker {
multiset<long long> lower_half, upper_half;
long long sum_lower = 0, sum_upper = 0;
bool has_median = false;
long long current_median = 0;
MedianTracker() {
lower_half.insert(-INF);
upper_half.insert(INF);
}
void clear() {
lower_half.clear(); upper_half.clear();
lower_half.insert(-INF); upper_half.insert(INF);
sum_lower = sum_upper = 0;
has_median = false; current_median = 0;
}
void insert(long long val) {
if (!has_median) {
long long max_l = *lower_half.rbegin();
long long min_u = *upper_half.begin();
if (val >= max_l && val <= min_u) {
current_median = val;
} else if (val < max_l) {
lower_half.erase(lower_half.find(max_l));
lower_half.insert(val);
sum_lower += val - max_l;
current_median = max_l;
} else {
upper_half.erase(upper_half.find(min_u));
upper_half.insert(val);
sum_upper += val - min_u;
current_median = min_u;
}
has_median = true;
} else {
if (val >= current_median) {
lower_half.insert(current_median); sum_lower += current_median;
upper_half.insert(val); sum_upper += val;
} else {
upper_half.insert(current_median); sum_upper += current_median;
lower_half.insert(val); sum_lower += val;
}
has_median = false;
}
}
void erase(long long val) {
long long max_l = *lower_half.rbegin();
long long min_u = *upper_half.begin();
if (!has_median) {
if (max_l >= val) {
lower_half.erase(lower_half.find(val)); sum_lower -= val;
upper_half.erase(upper_half.find(min_u)); sum_upper -= min_u;
current_median = min_u;
} else {
upper_half.erase(upper_half.find(val)); sum_upper -= val;
lower_half.erase(lower_half.find(max_l)); sum_lower -= max_l;
current_median = max_l;
}
has_median = true;
} else {
if (current_median != val) {
if (val > current_median) {
upper_half.erase(upper_half.find(val));
upper_half.insert(current_median);
sum_upper += current_median - val;
} else {
lower_half.erase(lower_half.find(val));
lower_half.insert(current_median);
sum_lower += current_median - val;
}
}
has_median = false;
}
}
long long get_cost() const {
return sum_upper - sum_lower;
}
};
void solve() {
int n; long long k;
cin >> n >> k;
vector<long long> a(n + 2);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
a[i] -= i;
}
a[n + 1] = INF;
MedianTracker tracker;
tracker.insert(a[1]);
int max_len = 1, right = 1;
for (int left = 1; left <= n; ++left) {
while (tracker.get_cost() <= k) {
max_len = max(max_len, right - left + 1);
tracker.insert(a[++right]);
}
tracker.erase(a[left]);
}
cout << max_len << "\n";
}
int main() {
int t; cin >> t;
while (t--) solve();
return 0;
}
Problema M: Geometría Computacional y Envolvente Convexa
La resolución requiere identificar triángulos vacíos dentro de un conjunto de puntos. Se utiliza el algoritmo de Monotone Chain para extraer la envolvente convexa. Posteriormente, se pueden abordar dos enfoques: 1) Iterar sobre puntos internos utilizándolos como polos para un ordenamiento por ángulo polar, buscando aristas adyacentes en la envolvente. 2) Evaluar aristas de la envolvente y aplicar una reducción bidimensional para puntos internos. El ordenamiento polar se implementa mediante productos cruz para evitar imprecisiones de punto flotante.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Point {
long long x, y;
int id;
bool is_hull;
};
long long cross_product(Point o, Point a, Point b) {
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
bool polar_sort(const Point& a, const Point& b, const Point& pole, const Point& ref) {
long long cp_a = cross_product(pole, ref, a);
long long cp_b = cross_product(pole, ref, b);
bool pos_a = (cp_a > 0) || (cp_a == 0 && (ref.x - pole.x) * (a.x - pole.x) > 0);
bool pos_b = (cp_b > 0) || (cp_b == 0 && (ref.x - pole.x) * (b.x - pole.x) > 0);
if (pos_a != pos_b) return pos_a > pos_b;
return cross_product(pole, a, b) > 0;
}
bool standard_cmp(const Point& a, const Point& b) {
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
void solve() {
int n;
cin >> n;
vector<Point> pts(n);
for (int i = 0; i < n; ++i) {
cin >> pts[i].x >> pts[i].y;
pts[i].id = i;
pts[i].is_hull = false;
}
sort(pts.begin(), pts.end(), standard_cmp);
vector<int> hull;
for (int i = 0; i < n; ++i) {
while (hull.size() >= 2 && cross_product(pts[hull[hull.size() - 2]], pts[hull.back()], pts[i]) <= 0) hull.pop_back();
hull.push_back(i);
}
int lower_size = hull.size();
for (int i = n - 2; i >= 0; --i) {
while (hull.size() > lower_size && cross_product(pts[hull[hull.size() - 2]], pts[hull.back()], pts[i]) <= 0) hull.pop_back();
hull.push_back(i);
}
hull.pop_back();
for (int idx : hull) pts[idx].is_hull = true;
long long valid_triangles = 1;
for (int i = 0; i < n; ++i) {
if (pts[i].is_hull) continue;
vector<Point> others;
for (int j = 0; j < n; ++j) {
if (i != j) others.push_back(pts[j]);
}
Point pole = pts[i];
Point ref = {pole.x - 1, pole.y, -1, false};
sort(others.begin(), others.end(), [&pole, &ref](const Point& a, const Point& b) {
return polar_sort(a, b, pole, ref);
});
if (others.front().is_hull && others.back().is_hull) valid_triangles++;
for (size_t j = 0; j < others.size() - 1; ++j) {
if (others[j].is_hull && others[j + 1].is_hull) valid_triangles++;
}
}
cout << valid_triangles << "\n";
}
int main() {
solve();
return 0;
}
Problema E: Flujo en Redes y Análisis de Redes Residuales
El modelo requiere emparejamiento bipartito donde la adición de una arista incremente el flujo máximo. Tras ejecutar el algoritmo de Dinic, se analiza la red residual. Una nueva arista puede crear un camino de aumento si conecta un nodo alcanzable desde la fuente en la partición izquierda con un nodo que puede alcanzar el sumidero en la partición derecha. La respuesta total es el producto del conteo de nodos que cumplen ambas condiciones en sus respectivas particiones.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int INF = 1e9;
struct Edge {
int to, cap, flow, rev;
};
struct Dinic {
int n, s, t;
vector<vector<Edge>> adj;
vector<int> level, ptr;
Dinic(int n, int s, int t) : n(n), s(s), t(t) {
adj.resize(n);
level.resize(n);
ptr.resize(n);
}
void add_edge(int from, int to, int cap) {
adj[from].push_back({to, cap, 0, (int)adj[to].size()});
adj[to].push_back({from, 0, 0, (int)adj[from].size() - 1});
}
bool bfs() {
fill(level.begin(), level.end(), -1);
level[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int v = q.front(); q.pop();
for (auto& edge : adj[v]) {
if (edge.cap - edge.flow > 0 && level[edge.to] == -1) {
level[edge.to] = level[v] + 1;
q.push(edge.to);
}
}
}
return level[t] != -1;
}
int dfs(int v, int pushed) {
if (pushed == 0 || v == t) return pushed;
for (int& cid = ptr[v]; cid < adj[v].size(); ++cid) {
auto& edge = adj[v][cid];
int tr = edge.to;
if (level[v] + 1 != level[tr] || edge.cap - edge.flow == 0) continue;
int push = dfs(tr, min(pushed, edge.cap - edge.flow));
if (push == 0) continue;
edge.flow += push;
adj[tr][edge.rev].flow -= push;
return push;
}
return 0;
}
int max_flow() {
int flow = 0;
while (bfs()) {
fill(ptr.begin(), ptr.end(), 0);
while (int pushed = dfs(s, INF)) flow += pushed;
}
return flow;
}
void count_reachable(int start_node, int target_side, int required_cap_state, vector<int>& vis, long long& count) {
vis[start_node] = 1;
if ((start_node <= n / 2 - 1) == (target_side == 1)) count++;
for (auto& edge : adj[start_node]) {
if (!vis[edge.to] && (edge.cap - edge.flow == required_cap_state || edge.cap == 0 && required_cap_state == 0)) {
// Lógica de traversal adaptada a la red residual específica
if ((edge.cap > 0 && edge.flow < edge.cap && required_cap_state == 1) ||
(edge.cap == 0 && edge.flow < 0 && required_cap_state == 0)) { // Ajuste conceptual
count_reachable(edge.to, target_side, required_cap_state, vis, count);
}
}
}
}
};
void solve() {
int n, m;
cin >> n >> m;
int s = 0, t = 2 * n + 1;
Dinic dinic(t + 1, s, t);
for (int i = 1; i <= n; ++i) {
dinic.add_edge(s, i, 1);
dinic.add_edge(i + n, t, 1);
}
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
dinic.add_edge(u, v + n, 1);
}
dinic.max_flow();
vector<int> vis(t + 1, 0);
long long left_reach = -1, right_reach = -1;
// Recorrido desde la fuente en la red residual (capacidad restante > 0)
auto dfs_source = [&](auto& self, int u) -> void {
vis[u] = 1;
if (u >= 1 && u <= n) left_reach++;
for (auto& edge : dinic.adj[u]) {
if (edge.cap - edge.flow > 0 && !vis[edge.to]) self(self, edge.to);
}
};
dfs_source(dfs_source, s);
fill(vis.begin(), vis.end(), 0);
// Recorrido inverso desde el sumidero
auto dfs_sink = [&](auto& self, int u) -> void {
vis[u] = 1;
if (u > n && u <= 2 * n) right_reach++;
for (auto& edge : dinic.adj[u]) {
// En el grafo residual inverso, buscamos aristas con flujo > 0 (que actúan como capacidad inversa)
int rev_idx = edge.rev;
auto& rev_edge = dinic.adj[edge.to][rev_idx];
if (rev_edge.cap - rev_edge.flow > 0 && !vis[edge.to]) self(self, edge.to);
}
};
dfs_sink(dfs_sink, t);
cout << left_reach * right_reach << "\n";
}
int main() {
int t; cin >> t;
while (t--) solve();
return 0;
}
Problema B: Programación Dinámica en Árboles con Descomposición por Raíz Cuadrada
El problema plantea una variante de la mochila en estructuras arbóreas. Para $k < \sqrt{n}$, se aplica DP clásica con complejidad $O(nk)$. Cuando $k \ge \sqrt{n}$, la cantidad de bloques válidos de tamaño $k$ es drásticamente pequeña. Se optimiza el espacio reemplazando la matriz bidimensional por tablas hash (std::unordered\_map), almacenando exclusivamente los estados alcanzables. La condición matemática $(size - i \cdot k) \pmod{k+1}$ limita drásticamente el espacio de estados por subárbol.
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
const int MOD = 998244353;
const int THRESHOLD = 660;
int n, K;
vector<vector<int>> tree;
vector<int> sz;
int dp_small[100005][666];
unordered_map<int, int> dp_large[100005];
void dfs_small(int u, int p) {
sz[u] = 1;
dp_small[u][1] = 1;
for (int v : tree[u]) {
if (v == p) continue;
dfs_small(v, u);
vector<int> temp(K + 2, 0);
for (int j = 0; j <= min(K, sz[v]); ++j) {
if (!dp_small[v][j]) continue;
for (int k = min(K + 1 - j, sz[u]); k >= 1; --k) {
if (!dp_small[u][k]) continue;
temp[j + k] = (temp[j + k] + 1LL * dp_small[v][j] * dp_small[u][k]) % MOD;
}
}
for (int j = 0; j <= K + 1; ++j) dp_small[u][j] = temp[j];
sz[u] += sz[v];
}
dp_small[u][0] = (dp_small[u][K] + dp_small[u][K + 1]) % MOD;
}
void dfs_large(int u, int p) {
sz[u] = 1;
dp_large[u][1] = 1;
for (int v : tree[u]) {
if (v == p) continue;
dfs_large(v, u);
unordered_map<int, int> temp;
for (auto& kv_v : dp_large[v]) {
for (auto& kv_u : dp_large[u]) {
if (kv_v.first + kv_u.first > K + 1) continue;
temp[kv_v.first + kv_u.first] = (temp[kv_v.first + kv_u.first] + 1LL * kv_v.second * kv_u.second) % MOD;
}
}
dp_large[u] = move(temp);
sz[u] += sz[v];
}
dp_large[u][0] = (dp_large[u][K] + dp_large[u][K + 1]) % MOD;
if (dp_large[u][K] == 0) dp_large[u].erase(K);
if (dp_large[u][K + 1] == 0) dp_large[u].erase(K + 1);
if (dp_large[u][0] == 0) dp_large[u].erase(0);
// Liberación de memoria para evitar Memory Limit Exceeded
if (u != 1) dp_large[u].clear();
}
void solve() {
cin >> n >> K;
tree.assign(n + 1, vector<int>());
sz.assign(n + 1, 0);
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u);
}
if (K <= THRESHOLD) {
for (int i = 1; i <= n; ++i) fill(dp_small[i], dp_small[i] + K + 2, 0);
dfs_small(1, 0);
cout << (dp_small[1][0] % MOD + MOD) % MOD << "\n";
} else {
for (int i = 1; i <= n; ++i) dp_large[i].clear();
dfs_large(1, 0);
cout << (dp_large[1][0] % MOD + MOD) % MOD << "\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
if (cin >> t) while (t--) solve();
return 0;
}