Problema A: División de Elementos

Se proporciona un arreglo ordenado ascendentemente. El objetivo es construir una cadena de caracteres compuesta por 'R' y 'B' de tal manera que la diferencia entre el valor máximo y mínimo de los elementos asignados a 'R' sea distinta a la diferencia correspondiente a los elementos asignados a 'B'.

Si todos los elementos del arreglo son idénticos, la diferencia será cero en ambos casos, por lo que la respuesta es "NO". En caso contrario, podemos asignar el segundo elemento a 'R' (lo que garantiza una diferencia de 0) y el resto de los elementos a 'B'. Dado que el arreglo contiene al menos dos valores distintos, la diferencia en 'B' será estrictamente mayor a 0.

#include <iostream>
#include <vector>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> elements(n);
    bool all_same = true;
    
    for (int i = 0; i < n; ++i) {
        cin >> elements[i];
        if (i > 0 && elements[i] != elements[0]) {
            all_same = false;
        }
    }

    if (all_same) {
        cout << "NO\n";
    } else {
        cout << "YES\n";
        for (int i = 0; i < n; ++i) {
            cout << (i == 1 ? 'R' : 'B');
        }
        cout << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tests;
    cin >> tests;
    while (tests--) {
        solve();
    }
    return 0;
}

Problema B: Suma de Gran Magnitud

El problema consiste en determinar si un número dado puede ser expresado como la suma de dos números que poseen la misma cantidad de dígitos.

Para que dos números de $d$ dígitos sumen un resultado de $d+1$ dígitos, el primer dígito del resultado debe ser obligatoriamente '1' (ya que la suma máxima es menor a $2 \times 10^d$). El último dígito no puede ser '9', ya que esto implicaría combinaciones de dígitos finales que generan carries incompatibles con la restricción de longitud. Además, ningún dígito intermedio puede ser '0'; si lo fuera, indicaría que no hubo carry desde la posición inferior, lo que forzaría a que los dígitos sumados en esa posición sean menores a 5, violando las condiciones del problema.

#include <iostream>
#include <string>

using namespace std;

void solve() {
    string num_str;
    cin >> num_str;
    int len = num_str.length();
    bool is_valid = true;

    if (num_str[0] != '1' || num_str[len - 1] == '9') {
        is_valid = false;
    } else {
        for (int i = 1; i < len - 1; ++i) {
            if (num_str[i] == '0') {
                is_valid = false;
                break;
            }
        }
    }

    cout << (is_valid ? "YES" : "NO") << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tests;
    cin >> tests;
    while (tests--) {
        solve();
    }
    return 0;
}

Problema C1: Magnitud (Versión Fácil)

Dado un areglo, se aplican operaciones secuenciales para maximizar el valor final. La operación óptima implica invertir el signo del valor acumulado cuando este es negativo, transformándolo en un valer positivo más grande antes de continuar sumando.

En esta versión, basta con mantener un seguimiento del valor máximo actual. Al procesar cada elemento, se actualiza el máximo y el mínimo acumulado. Si al invertir el signo del mínimo acumulado este supera al máximo actual, se actualiza el máximo.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void process_test_case() {
    int size;
    cin >> size;
    vector<long long> sequence(size);
    for (int i = 0; i < size; ++i) {
        cin >> sequence[i];
    }

    long long max_val = 0;
    long long min_val = 0;

    for (int i = 0; i < size; ++i) {
        max_val += sequence[i];
        min_val += sequence[i];
        if (-min_val > max_val) {
            max_val = -min_val;
        }
    }

    cout << max_val << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        process_test_case();
    }
    return 0;
}

Problema C2: Magnitud (Versión Difícil)

Esta es la extensión del problema anterior, donde se debe calcular la suma de los resultados bajo todas las combinaciones posibles de operaciones, módulo 998244353.

Si todos los elementos del arreglo son no negativos, cada elemento puede procesarse de dos formas sin afectar la optimalidad, resultando en $2^n$ combinaciones. Si existen valores negativos, debemos identificar el punto donde la suma prefija alcanza su mínimo. A partir de este punto, las operaciones posteriores no alterarán la optimalidad, ya que la suma de los elementos restantes será no negativa. El cálculo final combina las potencias de 2 basándose en la posición del mínimo prefijo y la cantidad de sumas prefijas no negativas.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MOD = 998244353;
const int MAX_N = 200005;
long long power_of_two[MAX_N];

void precompute() {
    power_of_two[0] = 1;
    for (int i = 1; i < MAX_N; ++i) {
        power_of_two[i] = (power_of_two[i - 1] * 2) % MOD;
    }
}

void solve_hard() {
    int n;
    cin >> n;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    vector<long long> prefix(n + 1, 0);
    long long min_prefix = 1000000000000000000LL;
    bool has_negative = false;

    for (int i = 1; i <= n; ++i) {
        prefix[i] = prefix[i - 1] + a[i];
        if (prefix[i] < min_prefix) {
            min_prefix = prefix[i];
        }
        if (prefix[i] < 0) {
            has_negative = true;
        }
    }

    if (!has_negative) {
        cout << power_of_two[n] << "\n";
        return;
    }

    long long ans = 0;
    int non_neg_count = 0;

    for (int i = 1; i <= n; ++i) {
        if (prefix[i] == min_prefix) {
            ans = (ans + power_of_two[n - i + non_neg_count]) % MOD;
        } else if (prefix[i] >= 0) {
            non_neg_count++;
        }
    }

    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    precompute();
    int t;
    cin >> t;
    while (t--) {
        solve_hard();
    }
    return 0;
}