T1: Conectividad en Gráficos Dirigidos
Análisis del Problema
Consideramos un grafo dirigido donde cada nodo tiene exactamente dos aristas entrantes y dos aristas salientes. El objetivo es determinar el número de formas de seleccionar nodos de tal manera que ninguna de las aristas internas de un ciclo se elija consecutivamente. La estructura de este tipo de grafo garantiza que está compuesto por una serie de ciclos disjuntos. Para cada nodo, las dos aristas entrantes se pueden considerar unidas, y de manera similar, las dos aristas salientes también se unen. Esto nos permite transformar el problema a uno donde las "aristas" originales son los elementos a conectar, formando componentes. Utilizando una estructura de datos de Unión-Encuentra (Disjoint Set Union - DSU), podemos modelar esta conectividad. Cada arista del grafo original (hay 2\*N en total si N es el número de nodos) se convierte en un "elemento" en nuestro DSU. Para cada nodo u del grafo, unimos sus dos aristas entrantes y también unimos sus dos aristas salientes. Al final, el número de componentes conectados en el DSU será el número de ciclos en el grafo transformado. En cada ciclo, solo podemos seleccionar nodos de forma alternada. Esto significa que para cada ciclo, hay exactamente dos maneras de seleccionar los nodos (empezar con un nodo o con el siguiente). Por lo tanto, si hay C ciclos, la respuesta final es \\(2^C\\). ### Implementación
#include <iostream>
#include <vector>
#include <numeric> // Para std::iota
#include <map> // Para almacenar las aristas de cada nodo
const int MAX_NODES = 1e5 + 5;
const int MOD = 1e9 + 7; // Un módulo común para respuestas grandes
// Array para la estructura DSU
std::vector<int> padre;
// Función find con compresión de ruta
int encontrar(int i) {
if (padre[i] == i)
return i;
return padre[i] = encontrar(padre[i]);
}
// Función union por tamaño/rango
void unir(int i, int j) {
int raiz_i = encontrar(i);
int raiz_j = encontrar(j);
if (raiz_i != raiz_j) {
padre[raiz_i] = raiz_j;
}
}
// Función para calcular potencia modular
long long potencia(long long base, long long exp) {
long long res = 1;
base %= MOD;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % MOD;
base = (base * base) % MOD;
exp /= 2;
}
return res;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n_original; // Número de nodos en el grafo original
std::cin >> n_original;
// Hay 2*n_original aristas en total
padre.resize(2 * n_original + 1);
std::iota(padre.begin(), padre.end(), 0); // Inicializar DSU
// Mapas para almacenar las dos aristas entrantes y salientes de cada nodo
// {nodo: [arista1, arista2]}
std::map<int, std::vector<int>> aristas_entrantes;
std::map<int, std::vector<int>> aristas_salientes;
for (int i = 1; i <= 2 * n_original; ++i) {
int u, v; // u -> v (arista i)
std::cin >> u >> v;
aristas_salientes[u].push_back(i);
aristas_entrantes[v].push_back(i);
}
// Unir las aristas relacionadas para cada nodo
for (int i = 1; i <= n_original; ++i) {
// Unir las dos aristas entrantes del nodo i
if (aristas_entrantes[i].size() == 2) {
unir(aristas_entrantes[i][0], aristas_entrantes[i][1]);
}
// Unir las dos aristas salientes del nodo i
if (aristas_salientes[i].size() == 2) {
unir(aristas_salientes[i][0], aristas_salientes[i][1]);
}
}
// Contar el número de componentes (ciclos)
int num_ciclos = 0;
for (int i = 1; i <= 2 * n_original; ++i) {
if (padre[i] == i) { // Si i es la raíz de un componente
num_ciclos++;
}
}
// La respuesta es 2 elevado al número de ciclos
std::cout << potencia(2, num_ciclos) << std::endl;
return 0;
}
T2: Secuencias Monótonas Optimizadas
Análisis del Problema
El problema pide encontrar el valor máximo de la suma de elementos dividida por el número de segmentos, donde la secuencia original se divide en segmentos monótonos alternos (creciente, decreciente, creciente, etc.). Queremos maximizar \\(\frac{\sum \text{valores en segmentos}}{\text{número de segmentos}}\\). Podemos formular esto como un problema de programación dinámica. Sea dp\[k\]\[val\] la suma máxima posible utilizando k segmentos, donde el último segmento termina con un elemento cuyo valor original es val. Para manejar valores repetidos y optimizar las búsquedas, se realiza una compresión de coordenadas en los valores de los elementos. El desafío radica en la alternancia de segmentos monótonos. * Si el k-ésimo segmento es creciente, entonces el elemento actual actual\_val debe ser mayor que el elemento final prev\_val del (k-1)-ésimo segmento (si k-1 fue decreciente) o mayor que prev\_val del k-ésimo segmento (si k también fue creciente). * Si el k-ésimo segmento es decreciente, entonces actual\_val debe ser menor que prev\_val del (k-1)-ésimo segmento (si k-1 fue creciente) o menor que prev\_val del k-ésimo segmento (si k también fue decreciente). Para optimizar las transiciones de DP, que implican consultar rangos de valores previos, usamos árboles de segmentos. Tendremos un árbol de segmentos segment\_tree\[k\] para cada número de segmentos k. Cada nodo en segment\_tree\[k\] almacenará el valor máximo dp\[k\]\[val\] para el rango de valores comprimidos que representa. ### Implementación
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
const int MAX_N = 1e5 + 10;
const long long NEG_INF = -1e18; // Usar un valor negativo muy grande para DP
// Segment Tree para almacenar los valores máximos de DP para 'k' segmentos
struct SegmentTree {
std::vector<long long> tree;
int size;
SegmentTree(int n_compressed) {
size = n_compressed;
tree.assign(4 * size, NEG_INF); // Inicializar con -INF
}
void update(int node, int start, int end, int idx, long long val) {
if (start == end) {
tree[node] = std::max(tree[node], val);
return;
}
int mid = (start + end) / 2;
if (start <= idx && idx <= mid) {
update(2 * node, start, mid, idx, val);
} else {
update(2 * node + 1, mid + 1, end, idx, val);
}
tree[node] = std::max(tree[2 * node], tree[2 * node + 1]);
}
long long query(int node, int start, int end, int l, int r) {
if (r < start || end < l || l > r) { // Rango de consulta fuera de límites o inválido
return NEG_INF;
}
if (l <= start && end <= r) {
return tree[node];
}
int mid = (start + end) / 2;
long long p1 = query(2 * node, start, mid, l, r);
long long p2 = query(2 * node + 1, mid + 1, end, l, r);
return std::max(p1, p2);
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n;
std::cin >> n;
std::vector<int> arr_original(n);
std::vector<int> valores_para_comprimir(n);
for (int i = 0; i < n; ++i) {
std::cin >> arr_original[i];
valores_para_comprimir[i] = arr_original[i];
}
// Compresión de coordenadas
std::sort(valores_para_comprimir.begin(), valores_para_comprimir.end());
valores_para_comprimir.erase(
std::unique(valores_para_comprimir.begin(), valores_para_comprimir.end()),
valores_para_comprimir.end()
);
std::map<int, int> valor_a_indice;
for (int i = 0; i < valores_para_comprimir.size(); ++i) {
valor_a_indice[valores_para_comprimir[i]] = i + 1; // Índices 1-basados
}
std::vector<int> arr_codificado(n);
for (int i = 0; i < n; ++i) {
arr_codificado[i] = valor_a_indice[arr_original[i]];
}
int n_compressed = valores_para_comprimir.size();
// Segment trees para k=1 y k=2 segmentos
// T[0] -> para un segmento (creciente)
// T[1] -> para dos segmentos (creciente-decreciente)
// Se necesitan dos "niveles" de Segment Trees para la DP alterna
// T[0] maneja DP para segmentos impares, T[1] maneja DP para segmentos pares.
std::vector<SegmentTree> dp_segs;
dp_segs.emplace_back(n_compressed); // dp_segs[0] para k segmentos
dp_segs.emplace_back(n_compressed); // dp_segs[1] para k-1 segmentos
double max_promedio = 0.0;
for (int i = 0; i < n; ++i) {
int current_val_original = arr_original[i];
int current_val_codificado = arr_codificado[i];
// Caso base: 1 segmento (siempre creciente por definición del problema al iniciar)
// Max sum for 1 segment ending at current_val
long long dp_1 = current_val_original;
dp_segs[0].update(1, 1, n_compressed, current_val_codificado, dp_1);
max_promedio = std::max(max_promedio, (double)dp_1 / 1.0);
// Iterar para k=2 y k=3 (en general, k segmentos)
// El bucle de k en el original va de 2 a 1, lo que sugiere un orden de procesamiento.
// Aquí lo simplificamos a dos pasos: calculando para el 2do segmento y luego para el 3ro (que en general
// alternaría entre el Segment Tree que tiene los impares y el que tiene los pares).
// La lógica original es para k=2 luego k=1 (en el mismo punto i), que es peculiar.
// Lo interpretamos como: calcular dp[k][s[i]] basado en dp[k-1] y dp[k] (anteriormente calculados).
// Simula la iteración `for (int k = max_k_segments; k >= 1; k--)`
// Usamos k_idx para alternar entre los dos Segment Trees:
// dp_segs[0] para segmentos impares (1, 3, 5...), dp_segs[1] para segmentos pares (2, 4, 6...)
// (En el código original, T[1] y T[2] eran usados para "k" y "k-1".
// Aquí, dp_segs[0] será "actual", dp_segs[1] será "anterior" para evitar recomputaciones en el mismo i.)
// Actualizar dp_segs[1] (simulando dp[k] o dp[k+1] para la siguiente iteración)
// Query para el 'k-1' segmento anterior (actualmente en dp_segs[0])
long long prev_sum_from_k_minus_1;
// Si el segmento actual es decreciente (k par), el anterior (k-1 impar) debe ser creciente (menor valor)
// Query para valores menores que current_val_codificado en dp_segs[0] (impares)
prev_sum_from_k_minus_1 = dp_segs[0].query(1, 1, n_compressed, 1, current_val_codificado - 1);
long long current_dp_sum = NEG_INF;
if (prev_sum_from_k_minus_1 != NEG_INF) {
current_dp_sum = std::max(current_dp_sum, prev_sum_from_k_minus_1 + current_val_original);
}
// Si el segmento actual es decreciente (k par), puede continuar un segmento decreciente
// Query para valores mayores que current_val_codificado en dp_segs[1] (pares)
long long continue_decreasing_sum = dp_segs[1].query(1, 1, n_compressed, current_val_codificado + 1, n_compressed);
if (continue_decreasing_sum != NEG_INF) {
current_dp_sum = std::max(current_dp_sum, continue_decreasing_sum + current_val_original);
}
if (current_dp_sum != NEG_INF) {
dp_segs[1].update(1, 1, n_compressed, current_val_codificado, current_dp_sum);
max_promedio = std::max(max_promedio, (double)current_dp_sum / 2.0); // k=2 para este caso
}
// Ahora, actualizamos dp_segs[0] (simulando dp[k] o dp[k+1] para la siguiente iteración)
// Query para el 'k-1' segmento anterior (actualmente en dp_segs[1])
long long prev_sum_from_k;
// Si el segmento actual es creciente (k impar), el anterior (k par) debe ser decreciente (mayor valor)
// Query para valores mayores que current_val_codificado en dp_segs[1] (pares)
prev_sum_from_k = dp_segs[1].query(1, 1, n_compressed, current_val_codificado + 1, n_compressed);
current_dp_sum = NEG_INF;
if (prev_sum_from_k != NEG_INF) {
current_dp_sum = std::max(current_dp_sum, prev_sum_from_k + current_val_original);
}
// Si el segmento actual es creciente (k impar), puede continuar un segmento creciente
// Query para valores menores que current_val_codificado en dp_segs[0] (impares)
long long continue_increasing_sum = dp_segs[0].query(1, 1, n_compressed, 1, current_val_codificado - 1);
if (continue_increasing_sum != NEG_INF) {
current_dp_sum = std::max(current_dp_sum, continue_increasing_sum + current_val_original);
}
if (current_dp_sum != NEG_INF) {
dp_segs[0].update(1, 1, n_compressed, current_val_codificado, current_dp_sum);
max_promedio = std::max(max_promedio, (double)current_dp_sum / 3.0); // k=3 para este caso
}
// La implementación original itera k=2 y k=1. Esto significa que está calculando para 2 segmentos
// y luego actualizando para 1 segmento. El 'k&1' es para determinar el tipo de segmento.
// La DP con Segment Trees para k segmentos suele ser iterando k.
// El bucle original 'for(int k=2;k>=1;k--)' es un poco confuso y puede implicar un estado alterno.
// Mi interpretación arriba es que dp_segs[0] es para los impares, dp_segs[1] para los pares,
// y se actualizan de forma que siempre se utilizan los valores calculados en la iteración anterior para 'k-1'
// para calcular los de 'k'.
// La lógica del código original T[k] y T[k-1] se traduce mejor a:
// temp_dp_vals_k_odd y temp_dp_vals_k_even
// Let's retry the core DP loop to be closer to original logic for clarification,
// assuming T[1] is for 1-segment max sum, T[2] for 2-segment max sum, etc.
// This implies MAX_K needs to be defined for SegmentTree array.
// The problem description usually has a small K. The code has T[3] total which means max 3 segments.
// It's a common trick to only keep 2 DP arrays, for k and k-1.
// T[0] for current step, T[1] for previous step.
}
// El enfoque que usa 2 segment trees (uno para estados "pares" y otro para "impares")
// es más común para alternar tipos de segmentos. El código original usa T[3], implicando
// k_max=2 o 3. Con la estructura del original `for(int k=2;k>=1;k--)` se puede
// inferir que `T[k]` contiene la solución para `k` segmentos y se actualiza en cada paso.
// Vamos a usar un enfoque más directo que simula el `T[k]` del código original,
// donde `T[k]` almacena el max_sum para `k` segmentos.
// Esto implicaría un array de SegmentTree: `std::vector<segmenttree> segment_trees(MAX_K + 1, SegmentTree(n_compressed));`
// El código original parece usar 3 segment trees: T[0], T[1], T[2] o T[1], T[2], T[3].
// Los índices 0,1,2 de `T` en el código.
// Repitiendo la lógica central para `T[k]` del original
std::vector<SegmentTree> seg_trees_k(3, SegmentTree(n_compressed)); // T[0], T[1], T[2] en el original
max_promedio = 0.0; // Reset para el nuevo cálculo
for (int i = 0; i < n; ++i) {
int actual_val_original = arr_original[i];
int actual_val_codificado = arr_codificado[i];
// Calcular DP para 1 segmento (siempre creciente)
long long dp_val_k1 = actual_val_original;
seg_trees_k[0].update(1, 1, n_compressed, actual_val_codificado, dp_val_k1);
max_promedio = std::max(max_promedio, (double)dp_val_k1 / 1.0);
// Iterar para k = 2 (significando el segundo segmento, que sería decreciente)
// y k = 3 (tercer segmento, que sería creciente) en el original.
// El bucle original era `for (int k=2; k>=1; k--)`. Esto significa que k va de 2 a 1.
// Vamos a interpretar `T[k]` como DP para `k+1` segmentos, para coincidir con `k=0,1,2` en el código.
// T[0] is for `k_segs=1` (odd).
// T[1] is for `k_segs=2` (even).
// T[2] is for `k_segs=3` (odd).
// The original code implies T[k-1] and T[k] interactions.
// `k_num_segments` va de 2 a N. Solo consideraremos un número pequeño de segmentos
// como el código original parece implicar al usar T[3] máximo.
// Re-estructurando para emular el `for k=2;k>=1;k--` del original
// `temp` is the new value for `T[k]` at `s[i]`.
// The `temp` variable in original code stores `current_max_sum_ending_at_s[i]`.
// Simulate k=2 (represents 2 segments, decreasing)
long long current_max_sum_k2 = NEG_INF;
// Option 1: Continue from a 1-segment state (increasing) ending at a smaller value
long long from_1_segment_inc = seg_trees_k[0].query(1, 1, n_compressed, 1, actual_val_codificado - 1);
if (from_1_segment_inc != NEG_INF) {
current_max_sum_k2 = std::max(current_max_sum_k2, from_1_segment_inc + actual_val_original);
}
// Option 2: Continue from a 2-segment state (decreasing) ending at a larger value
long long from_2_segment_dec = seg_trees_k[1].query(1, 1, n_compressed, actual_val_codificado + 1, n_compressed);
if (from_2_segment_dec != NEG_INF) {
current_max_sum_k2 = std::max(current_max_sum_k2, from_2_segment_dec + actual_val_original);
}
if (current_max_sum_k2 != NEG_INF) {
seg_trees_k[1].update(1, 1, n_compressed, actual_val_codificado, current_max_sum_k2);
max_promedio = std::max(max_promedio, (double)current_max_sum_k2 / 2.0);
}
// Simulate k=3 (represents 3 segments, increasing)
long long current_max_sum_k3 = NEG_INF;
// Option 1: Continue from a 2-segment state (decreasing) ending at a larger value
long long from_2_segment_dec_to_3_inc = seg_trees_k[1].query(1, 1, n_compressed, actual_val_codificado + 1, n_compressed);
if (from_2_segment_dec_to_3_inc != NEG_INF) {
current_max_sum_k3 = std::max(current_max_sum_k3, from_2_segment_dec_to_3_inc + actual_val_original);
}
// Option 2: Continue from a 3-segment state (increasing) ending at a smaller value
long long from_3_segment_inc_cont = seg_trees_k[2].query(1, 1, n_compressed, 1, actual_val_codificado - 1);
if (from_3_segment_inc_cont != NEG_INF) {
current_max_sum_k3 = std::max(current_max_sum_k3, from_3_segment_inc_cont + actual_val_original);
}
if (current_max_sum_k3 != NEG_INF) {
seg_trees_k[2].update(1, 1, n_compressed, actual_val_codificado, current_max_sum_k3);
max_promedio = std::max(max_promedio, (double)current_max_sum_k3 / 3.0);
}
// The original problem likely limits the number of segments to a small constant, e.g., 2 or 3.
// My interpretation here models the interaction for k=1, 2, 3 segments.
// seg_trees_k[0] stores max sum for 1 segment (increasing)
// seg_trees_k[1] stores max sum for 2 segments (decreasing)
// seg_trees_k[2] stores max sum for 3 segments (increasing)
// This is a common pattern for N-log-N DP with limited K.
}
std::cout.precision(3);
std::cout << std::fixed << max_promedio << std::endl;
return 0;
}
</segmenttree>
T3: Transformación de Matriz Cuadrada
Análisis del Problema
El objetivo es transformar una matriz M de N x M a una matriz de todos ceros aplicando una serie de operaciones. Hay tres tipos de operaciones: 1. Sumar un valor d a todos los elementos de una fila r. 2. Sumar un valor d a todos los elementos de una columna c. 3. Sumar un valor d a todos los elementos de una diagonal. En este contexto, una "diagonal" se define por la diferencia constante row - col. Es decir, para un offset dado, la operación afecta a todos los M\[i\]\[j\] tales que i - j = offset. La estrategia de solución se basa en reducir progresivamente la matriz a ceros. Primero, se manipulan las dos primeras filas y columnas para igualar sus elementos y luego hacerlos cero. La idea central es que, si logramos hacer que M\[i\]\[j\] = M\[i+1\]\[j+1\] para la parte superior izquierda de la matriz, y luego reducir M\[1\]\[1\] a cero, podemos propagar este efecto. El problema se resuelve eliminando elementos de arriba hacia abajo y de izquierda a derecha. 1. **Igualar M\[1\]\[1\] y M\[2\]\[2\]:** Si M\[1\]\[1\] != M\[2\]\[2\], aplicamos una operación de fila a M\[1\] para hacer M\[1\]\[1\] = M\[2\]\[2\]. Esto afectará toda la primera fila. 2. **Eliminar M\[1\]\[j\] y M\[2\]\[j\] para j > 1:** Para cada columna j desde 2 hasta m-1, si M\[1\]\[j\] != M\[2\]\[j\], aplicamos una operación diagonal row - col = j-1 para igualar M\[1\]\[j\] y M\[2\]\[j\]. Esta operación afecta a M\[1\]\[j\], M\[2\]\[j+1\], .... 3. **Eliminar M\[i\]\[1\] y M\[i\]\[2\] para i > 1:** Similarmente para filas. Para cada fila i desde 2 hasta n-1, si M\[i\]\[1\] != M\[i\]\[2\], aplicamos una operación diagonal row - col = i-1 para igualar M\[i\]\[1\] y M\[i\]\[2\]. Esta operación afecta a M\[i\]\[1\], M\[i+1\]\[2\], .... 4. **Reducir las primeras filas a cero:** Una vez que las diferencias entre M\[1\]\[j\] y M\[2\]\[j\] (y M\[i\]\[1\] y M\[i\]\[2\]) se han manejado en cascada, podemos usar operaciones de columna para poner a cero M\[1\]\[j\] para cada j. Esto propagará los cambios hacia abajo. 5. **Reducir las primeras columnas a cero:** De manera análoga, usamos operaciones de fila para poner a cero M\[i\]\[1\] para cada i. Esto propagará los cambios hacia la derecha. Si después de todas las operaciones, algún elemento de la matriz no es cero, entonces es imposible lograr el objetivo. ### Implementación
#include <iostream>
#include <vector>
#include <numeric> // Para std::iota
#include <algorithm>
struct Operacion {
int tipo; // 1: fila, 2: columna, 3: diagonal
int indice_o_desplazamiento; // Fila/columna index, o desplazamiento para diagonal (row-col)
long long valor; // Valor a sumar
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n_filas, m_columnas;
std::cin >> n_filas >> m_columnas;
std::vector<std::vector<long long>> matriz(n_filas, std::vector<long long>(m_columnas));
for (int i = 0; i < n_filas; ++i) {
for (int j = 0; j < m_columnas; ++j) {
std::cin >> matriz[i][j];
}
}
std::vector<Operacion> operaciones_registradas;
// Casos especiales para N=1 o M=1
if (n_filas == 1) {
for (int j = 0; j < m_columnas; ++j) {
if (matriz[0][j] != 0) {
operaciones_registradas.push_back({2, j + 1, -matriz[0][j]}); // Columna 1-basada
matriz[0][j] = 0;
}
}
std::cout << operaciones_registradas.size() << std::endl;
for (const auto& op : operaciones_registradas) {
std::cout << op.tipo << " " << op.indice_o_desplazamiento << " " << op.valor << std::endl;
}
return 0;
}
if (m_columnas == 1) {
for (int i = 0; i < n_filas; ++i) {
if (matriz[i][0] != 0) {
operaciones_registradas.push_back({1, i + 1, -matriz[i][0]}); // Fila 1-basada
matriz[i][0] = 0;
}
}
std::cout << operaciones_registradas.size() << std::endl;
for (const auto& op : operaciones_registradas) {
std::cout << op.tipo << " " << op.indice_o_desplazamiento << " " << op.valor << std::endl;
}
return 0;
}
// Paso 1: Igualar M[0][0] y M[1][1] (en índices 0-basados)
if (matriz[0][0] != matriz[1][1]) {
long long diff = matriz[1][1] - matriz[0][0];
operaciones_registradas.push_back({1, 1, diff}); // Operación en fila 1 (0-basada)
for (int j = 0; j < m_columnas; ++j) {
matriz[0][j] += diff;
}
}
// Paso 2: Ajustar filas para que M[0][j] y M[1][j] sean iguales (para j > 0)
// Esto se hace con operaciones diagonales de tipo (row - col = constante)
for (int j = 1; j < m_columnas; ++j) {
if (matriz[0][j] != matriz[1][j]) {
long long diff = matriz[1][j] - matriz[0][j];
// La diagonal afectada para M[0][j] es (0 - j), para M[1][j] es (1 - j).
// La diagonal que pasa por (0,j) y (1,j+1) tiene offset col-row = j.
// La operación diagonal en el original es (opt=3, x, dat) donde x = i-1 o 1-i.
// Si es i-1, opera sobre (x,y) donde y-x = i-1.
// Si es 1-i, opera sobre (x,y) donde x-y = i-1.
// El código original usa `q[++cnt]=(Node){3,i-1,temp}` donde `i` es la columna (`2..m`).
// `for(int x=1,y=i;x<=n&&y<=m;x++,y++) s[x][y]+=temp;`
// Esto significa que el `x` en `Node` es `col_idx - row_idx` (1-basado).
// Para `matriz[0][j]` (columna `j+1` en 1-based) y `matriz[1][j]` (columna `j+1` en 1-based),
// el offset para `j` es `(j+1)-1 = j`.
operaciones_registradas.push_back({3, j, diff}); // Desplazamiento j (col-row)
for (int r = 0; r < n_filas; ++r) {
int c = r + j; // c = r + (col - row)
if (c < m_columnas) {
matriz[r][c] += diff;
}
}
}
}
// Paso 3: Ajustar columnas para que M[i][0] y M[i][1] sean iguales (para i > 0)
for (int i = 1; i < n_filas; ++i) {
if (matriz[i][0] != matriz[i][1]) {
long long diff = matriz[i][1] - matriz[i][0];
// El offset es `row_idx - col_idx` (1-basado). Para `matriz[i][0]`, es `(i+1)-1 = i`.
operaciones_registradas.push_back({3, -i, diff}); // Desplazamiento -i (row-col)
for (int c = 0; c < m_columnas; ++c) {
int r = c + i; // r = c + (row - col)
if (r < n_filas) {
matriz[r][c] += diff;
}
}
}
}
// Paso 4: Poner a cero la primera fila usando operaciones de columna
for (int j = 0; j < m_columnas; ++j) {
if (matriz[0][j] != 0) {
long long diff = -matriz[0][j];
operaciones_registradas.push_back({2, j + 1, diff}); // Columna j+1 (1-basada)
for (int i = 0; i < n_filas; ++i) {
matriz[i][j] += diff;
}
}
}
// Paso 5: Poner a cero la primera columna usando operaciones de fila
for (int i = 0; i < n_filas; ++i) {
if (matriz[i][0] != 0) {
long long diff = -matriz[i][0];
operaciones_registradas.push_back({1, i + 1, diff}); // Fila i+1 (1-basada)
for (int j = 0; j < m_columnas; ++j) {
matriz[i][j] += diff;
}
}
}
// Verificar si toda la matriz es cero
for (int i = 0; i < n_filas; ++i) {
for (int j = 0; j < m_columnas; ++j) {
if (matriz[i][j] != 0) {
std::cout << -1 << std::endl;
return 0;
}
}
}
std::cout << operaciones_registradas.size() << std::endl;
for (const auto& op : operaciones_registradas) {
std::cout << op.tipo << " " << op.indice_o_desplazamiento << " " << op.valor << std::endl;
}
return 0;
}
T4: Optimización con Envolvente Convexa (Convex Hull Trick)
Análisis del Problema
El problema se formula como una programación dinámica donde el estado dp\[i\]\[j\] representa la solución óptima para un prefijo de la secuencia, con i siendo el índice final del segmento actual y j el índice final del segmento anterior. Se busca maximizar el valor de la expresión: \\(dp_{i,j} = \max_{0 \le k < j} \{ dp_{j,k} + (S_i - S_j)(S_j - S_k) \}\\) donde \\(S_x\\) es la suma de prefijos hasta el índice \\(x\\). Podemos reescribir la relación de recurrencia para aplicar la técnica de optimización de envolvente convexa (Convex Hull Trick - CHT): \\(dp_{i,j} = (S_i - S_j)S_j + \max_{0 \le k < j} \{ dp_{j,k} - (S_i - S_j)S_k \}\\) Sea \\(m = (S_i - S_j)\\) (la pendiente) y \\(x = S_k\\). Queremos maximizar \\(y - mx\\), donde \\(y = dp_{j,k}\\). Esta es la forma estándar de CHT, donde \\(C = y - mx\\) es la intersección con el eje Y que queremos maximizar para una pendiente dada \\(m\\). Las "líneas" que estamos considerando son \\(L_k(x) = -S_k \cdot x + dp_{j,k}\\). Queremos encontrar la línea \\(L_k\\) que maximice \\(L_k(S_i - S_j)\\). Para que CHT funcione eficientemente con una cola monótona (deque), necesitamos que las pendientes \\(m = (S_i - S_j)\\) sean monótonas y que las \\(x = S_k\\) de las líneas que añadimos a la envolvente también sean monótonas. En este caso, iteramos sobre j (el final del segmento anterior) y i (el final del segmento actual). La pendiente \\(S_i - S_j\\) puede no ser monótona de forma simple si i y j no se comportan adecuadamente. La estrategia común es: 1. Iterar sobre j (el final del segmento actual). 2. Para cada j, construir una envolvente convexa con los puntos \\((S_k, dp_{j,k})\\) para todo \\(k < j\\). 3. Luego, para cada i (el final del siguiente segmento), y con la pendiente \\(m = S_i - S_j\\), consultar la envolvente convexa para encontrar el \\(k\\) óptimo. Para manejar las pendientes de manera eficiente, los valores \\(S_k\\) se pueden ordenar. El código original pre-calcula sumas de prefijo y las guarda en una estructura junto con el índice original, luego las ordena. Esto permite un recorido eficiente para construir y consultar la envolvente. ### Implementación
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
const int MAX_N = 5005;
const long long NEG_INF = 0x8f8f8f8f8f8f8f8fLL; // Un valor muy pequeño para inicializar DP
long long dp[MAX_N][MAX_N]; // dp[actual_end_idx][prev_end_idx]
long long prefix_sums[MAX_N]; // prefix_sums[i] = sum(a[1]...a[i])
// Estructura para almacenar sumas de prefijo con su índice original
struct PrefijoInfo {
int id_original;
long long valor_suma;
// Criterio de ordenación para CHT: por valor_suma, luego por id_original
bool operator<(const PrefijoInfo& other) const {
if (valor_suma == other.valor_suma) {
return id_original < other.id_original;
}
return valor_suma < other.valor_suma;
}
};
// Función para calcular la pendiente de la línea que conecta dos puntos (x1, y1) y (x2, y2)
// Retorna (y1 - y2) / (x1 - x2)
// Para evitar divisiones con punto flotante, se trabaja con productos cruzados
long double calcular_pendiente(int k1_idx, int k2_idx, int fixed_j_val) {
if (prefix_sums[k1_idx] == prefix_sums[k2_idx]) {
// Vertical line, handle carefully. Maximize dp[fixed_j_val][k]
// If x_coords are same, compare y_coords.
return dp[fixed_j_val][k1_idx] > dp[fixed_j_val][k2_idx] ? -1e18 : 1e18; // Effectively infinite slope
}
return (long double)(dp[fixed_j_val][k1_idx] - dp[fixed_j_val][k2_idx]) / (prefix_sums[k1_idx] - prefix_sums[k2_idx]);
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n;
std::cin >> n;
std::vector<int> a(n + 1);
PrefijoInfo prefijo_data[MAX_N];
// Inicializar DP con NEG_INF
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= n; ++j) {
dp[i][j] = NEG_INF;
}
}
// Calcular sumas de prefijo y preparar datos para CHT
prefix_sums[0] = 0;
prefijo_data[0] = {0, 0};
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
prefix_sums[i] = prefix_sums[i - 1] + a[i];
prefijo_data[i] = {i, prefix_sums[i]};
}
// Casos base: dp[i][0] y dp[i][i] podrían ser 0.
// dp[i][0] significa que el segmento actual termina en i, y el anterior "terminó" en 0 (inicio de la secuencia).
// dp[i][i] es un caso de un segmento de longitud cero, o un solo elemento.
// El original pone `f[i][0]=f[i][i]=0`.
// f[i][0]=0 means an empty previous segment contributes 0.
// f[i][i]=0 implies (S_i-S_i)(S_i-S_i) = 0.
for(int i = 0; i <= n; ++i) {
dp[i][0] = 0; // Segmento vacío antes del primer elemento.
}
// Sort prefix_sums based on their values for CHT
// This helps maintain monotonicity of x-coordinates (S_k)
std::sort(prefijo_data, prefijo_data + n + 1);
long long max_resultado_global = NEG_INF;
// Bucle principal de DP (iterar 'j' como final del segmento actual)
for (int j = 1; j <= n; ++j) {
std::deque<int> cola_monotona; // Almacena índices k (originales)
// Construir la envolvente convexa con puntos (S_k, dp[j][k]) para k < j
for (int p_idx = 0; p_idx <= n; ++p_idx) { // Iterar sobre los prefijo_data ordenados
int k_original = prefijo_data[p_idx].id_original;
if (k_original >= j) continue; // Solo considerar k < j
if (dp[j][k_original] == NEG_INF) continue; // Skip if no valid path to this state
// Mantener la propiedad de envolvente convexa (upper envelope para maximización)
// (y2-y1)/(x2-x1) < (y3-y2)/(x3-x2) for the last two points and the new point
while (cola_monotona.size() >= 2) {
int k1 = cola_monotona[cola_monotona.size() - 2];
int k2 = cola_monotona[cola_monotona.size() - 1];
// Check if the new point k_original makes the slope flatter
// (dp[j][k2] - dp[j][k1]) * (prefix_sums[k_original] - prefix_sums[k2])
// >= (dp[j][k_original] - dp[j][k2]) * (prefix_sums[k2] - prefix_sums[k1])
// The CHT condition for removing points for upper envelope.
// If slopes are (y1-y2)/(x1-x2) vs (y2-y3)/(x2-x3) and we want decreasing slopes:
// (Y[k2]-Y[k1])*(X[k_original]-X[k2]) >= (Y[k_original]-Y[k2])*(X[k2]-X[k1])
// Or simplified: slope(k1, k2) >= slope(k2, k_original)
// Using cross product to avoid division:
if ((dp[j][k2] - dp[j][k1]) * (prefix_sums[k_original] - prefix_sums[k2]) >=
(dp[j][k_original] - dp[j][k2]) * (prefix_sums[k2] - prefix_sums[k1])) {
cola_monotona.pop_back();
} else {
break;
}
}
cola_monotona.push_back(k_original);
}
// Consultar la envolvente convexa para i > j
// Iterar i en orden inverso para que la pendiente (S_i - S_j) sea monótona decreciente
// (o al menos más fácil de manejar si S_i.dat se recorre en un orden específico)
for (int p_idx = n; p_idx >= 0; --p_idx) {
int i_original = prefijo_data[p_idx].id_original;
if (i_original <= j) continue; // Solo considerar i > j
// La pendiente para esta consulta es m = S_i - S_j
long long m = prefijo_sums[i_original] - prefix_sums[j];
// Eliminar puntos de la cola cuyo segmento ya no es óptimo
// Esto es para pendientes decrecientes y maximización (upper envelope)
while (cola_monotona.size() >= 2) {
int k1 = cola_monotona[0];
int k2 = cola_monotona[1];
// If slope(k1,k2) < m, k1 is not optimal anymore. Pop from front.
// (dp[j][k1] - dp[j][k2]) / (prefix_sums[k1] - prefix_sums[k2]) < m
// Again, use cross product to avoid division.
if ((dp[j][k1] - dp[j][k2]) < m * (prefix_sums[k1] - prefix_sums[k2])) {
cola_monotona.pop_front();
} else {
break;
}
}
if (!cola_monotona.empty()) {
int best_k = cola_monotona.front();
// dp[i_original][j] = (S_i - S_j)S_j + dp[j][best_k] - (S_i - S_j)S_k
dp[i_original][j] = m * prefix_sums[j] + dp[j][best_k] - m * prefix_sums[best_k];
}
max_resultado_global = std::max(max_resultado_global, dp[i_original][j]);
}
}
std::cout << max_resultado_global << std::endl;
return 0;
}