División Bronce (Cu)
Problema 1: Segmentos de Mayoría
Dado un arreglo de $n$ elementos, una operación consiste en seleccionar un subarreglo donde un valor aparezca más de la mitad de las veces y transformar todo el subarreglo a ese valor. El objetivo es identificar qué valores pueden dominar eventualmente todo el arreglo.
Estrategia: Un valor puede expandirse indefinidamente si existe una "semilla" de tamaño 2 o 3 donde sea mayoría. Esto ocurre si encontramos dos elementos iguales adyacentes (A A) o separados por un solo elemento (A B A). En estos casos, el valor puede convertir a su vecino inmediato y luego seguir expandiéndose. Si no se cumple esta condición local en ninguna parte, el valor nunca podrá ser mayoría en un rango mayor.
#include <iostream>
#include <vector>
#include <algorithm>
void resolver_t1() {
int n;
std::cin >> n;
std::vector<int> nums(n);
std::vector<bool> posible(n + 1, false);
for (int i = 0; i < n; ++i) std::cin >> nums[i];
for (int i = 0; i < n; ++i) {
if (i + 1 < n && nums[i] == nums[i+1]) {
posible[nums[i]] = true;
}
if (i + 2 < n && nums[i] == nums[i+2]) {
posible[nums[i]] = true;
}
}
std::vector<int> resultados;
for (int i = 1; i <= n; ++i) {
if (posible[i]) resultados.push_back(i);
}
if (resultados.empty()) {
std::cout << -1;
} else {
for (size_t i = 0; i < resultados.size(); ++i) {
std::cout << resultados[i] << (i == resultados.size() - 1 ? "" : " ");
}
}
std::cout << "\n";
}
int main() {
int t;
std::cin >> t;
while (t--) resolver_t1();
return 0;
}
Problema 2: Simulación de Trayectoria
El problema describe un movimiento en una línea con rebotes y cambios de energía. Dado que la velocidad (o el salto) no disminuye, el proceso puede simularse directamente. La clave es detectar ciclos para evitar bucles infinitos cuando el personaje queda atrapado saltando entre las mismas posiciones con los mismos parámetros.
#include <iostream>
#include <vector>
#include <set>
int main() {
int n, pos_inicial;
std::cin >> n >> pos_inicial;
std::vector<int> tipo(n + 1), valor(n + 1);
for (int i = 1; i <= n; ++i) std::cin >> tipo[i] >> valor[i];
int potencia = 1, direccion = 1, objetivos_rotos = 0;
std::vector<bool> roto(n + 1, false);
std::set<std::pair<int, std::pair<int, int>>> visitado;
int actual = pos_inicial;
while (actual >= 1 && actual <= n) {
if (visitado.count({actual, {potencia, direccion}})) break;
visitado.insert({actual, {potencia, direccion}});
if (tipo[actual] == 0) {
direccion *= -1;
potencia += valor[actual];
} else {
if (!roto[actual] && potencia >= valor[actual]) {
roto[actual] = true;
objetivos_rotos++;
}
}
actual += direccion * potencia;
}
std::cout << objetivos_rotos << std::endl;
return 0;
}
Problema 3: Balanceo con Progresiones Aritméticas
Se requiere transformar un arreglo a cero sumando o restando progresiones aritméticas que comienzan en una posición determinada hasta el final.
Solución: El uso de diferencias finitas simplifica el problema. Aplicar una progresión aritmética en el arreglo original equivale a sumar un valor constante a una sección del arrreglo de diferencias de primer orden ($B_i = A_i - A_{i-1}$). Si aplicamos una segunda diferencia ($C_i = B_i - B_{i-1}$), la operación se convierte en una modificación puntual. El número mínimo de operaciones es la suma de los valores absolutos del arreglo de segundas diferencias.
#include <iostream>
#include <vector>
#include <cmath>
int main() {
int n;
std::cin >> n;
std::vector<long long> a(n + 1, 0);
for (int i = 1; i <= n; ++i) std::cin >> a[i];
std::vector<long long> dif1(n + 1, 0);
for (int i = 1; i <= n; ++i) dif1[i] = a[i] - a[i-1];
long long total_ops = 0;
long long prev_dif = 0;
for (int i = 1; i <= n; ++i) {
total_ops += std::abs(dif1[i] - prev_dif);
prev_dif = dif1[i];
}
std::cout << total_ops << std::endl;
return 0;
}
División Plata (Ag)
Problema 1: Máximos de Prefijo Lexicográficos
Dada una secunecia con valores desconocidos (ceros) y restricciones sobre cuándo el máximo de prefijo aumenta, debemos completra el arreglo para que sea lexicográficamente mínimo.
Solución: Las restricciones $(a_j, h_j)$ implican que $max(C_1 \dots C_{h_j-1}) < C_{h_j}$ y que $max(C_1 \dots C_{a_j}) = max(C_1 \dots C_{h_j-1})$. Al ordenar las restricciones, podemos ajustar los máximos de prefijo necesarios de forma codiciosa. Si en algún punto una restricción requiere un valor mayor al límite $C$ o contradice una restricción previa, la solución es imposible.
#include <iostream>
#include <vector>
#include <algorithm>
struct Restriccion {
int a, h;
};
bool compararRestricciones(const Restriccion& r1, const Restriccion& r2) {
if (r1.a == r2.a) return r1.h < r2.h;
return r1.a < r2.a;
}
void resolver_plata_t1() {
int n, q, limite_c;
std::cin >> n >> q >> limite_c;
std::vector<int> c(n + 1);
std::vector<int> pref_max(n + 1, 0);
for (int i = 1; i <= n; ++i) {
std::cin >> c[i];
pref_max[i] = std::max(pref_max[i - 1], c[i]);
}
std::vector<Restriccion> res(q);
for (int i = 0; i < q; ++i) std::cin >> res[i].a >> res[i].h;
std::sort(res.begin(), res.end(), compararRestricciones);
// Lógica de ajuste codicioso de pref_max (resumen)
// Se debe verificar la consistencia de cada restricción y
// llenar los espacios vacíos con 1 para mantener el orden lexicográfico.
// ... [Validación y construcción de la salida]
}
Problema 2: Recolección de Pociones en Árboles
Se debe recorrer un árbol desde la raíz hasta las hojas. Cada vez que se genera una poción, se puede recoger si el nodo está en el camino actual. El número total de recorridos está limitado por la cantidad de hojas en el árbol.
Solución: Este es un problema de flujo o emparejamiento que puede resolverse mediante Programación Dinámica en árboles. Para cada nodo $u$, calculamos cuántas hojas $sze[u]$ tiene su subárbol y cuántas pociones $f[u]$ puede aportar ese subárbol. Una poción en el nodo $u$ solo puede tomarse si hay al menos una hoja disponible que no haya sido "utilizada" por una poción más profunda en el subárbol.
#include <iostream>
#include <vector>
const int MAXN = 100005;
std::vector<int> adj[MAXN];
int pociones_en_nodo[MAXN];
int num_hojas[MAXN], dp[MAXN];
void dfs_pociones(int u, int p) {
bool es_hoja = true;
for (int v : adj[u]) {
if (v == p) continue;
es_hoja = false;
dfs_pociones(v, u);
num_hojas[u] += num_hojas[v];
dp[u] += dp[v];
}
if (es_hoja) num_hojas[u] = 1;
if (pociones_en_nodo[u] > 0) {
int disponibles = num_hojas[u] - dp[u];
int usar = std::min(disponibles, pociones_en_nodo[u]);
dp[u] += usar;
}
}
int main() {
int n;
std::cin >> n;
std::vector<int> orden_pociones(n + 1);
for (int i = 1; i <= n; ++i) std::cin >> orden_pociones[i];
for (int i = 0; i < n - 1; ++i) {
int u, v;
std::cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int hojas_totales = 0;
for (int i = 2; i <= n; ++i) if (adj[i].size() == 1) hojas_totales++;
for (int i = 1; i <= hojas_totales; ++i) pociones_en_nodo[orden_pociones[i]]++;
dfs_pociones(1, 0);
std::cout << dp[1] << std::endl;
return 0;
}
Problema 3: Restricciones de Módulo
Encontrar la suma de todos los $L$ tales que $4L \le min(a_i)$ y el conjunto $\{a_i \pmod L\}$ tenga a lo sumo 3 elementos distintos.
Solución: Por el Principio del Palomar, en cualquier conjunto de 4 números, al menos dos deben ser congruentes módulo $L$ si solo se permiten 3 residuos. Por lo tanto, $L$ debe ser un divisor de la diferencia $|a_i - a_j|$ para algún par $(i, j)$ dentro de los primeros 4 elementos del arreglo ordenado. Esto reduce drásticamente el espacio de búsqueda. Iteramos sobre los divisores de estas diferencias y verificamos la condición en $O(n)$.
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
bool es_valido(long long L, const std::vector<long long>& a) {
if (L == 0) return false;
std::set<long long> residuos;
for (long long x : a) {
residuos.insert(x % L);
if (residuos.size() > 3) return false;
}
return true;
}
int main() {
int n;
std::cin >> n;
std::vector<long long> a(n);
long long min_val = 4e18;
for (int i = 0; i < n; ++i) {
std::cin >> a[i];
min_val = std::min(min_val, a[i]);
}
std::sort(a.begin(), a.end());
a.erase(std::unique(a.begin(), a.end()), a.end());
if (a.size() <= 3) {
long long max_L = min_val / 4;
std::cout << max_L * (max_L + 1) / 2 << std::endl;
return 0;
}
std::set<long long> candidatos;
for (int i = 0; i < 4 && i < a.size(); ++i) {
for (int j = i + 1; j < 4 && j < a.size(); ++j) {
long long diff = a[j] - a[i];
for (long long d = 1; d * d <= diff; ++d) {
if (diff % d == 0) {
if (d * 4 <= min_val) candidatos.insert(d);
if ((diff / d) * 4 <= min_val) candidatos.insert(diff / d);
}
}
}
}
long long suma_L = 0;
for (long long L : candidatos) {
if (es_valido(L, a)) suma_L += L;
}
std::cout << suma_L << std::endl;
return 0;
}