Implementaciones en C++ para Codeforces Round 912 (División 2)

Este artículo presenta soluciones optimizadas en C++ para los problemas del concurso Codeforces Round 912 (División 2), con enfoque en estructuras de código eficientes y explicaciones técnicas concisas.

Problema A: Cajas de Halloumi

Se requiere determinar si un arreglo puede ordenarse con un número limitado de operaciones. La solución verifica si las operaciones permitidas son mayores que 1, en cuyo caso siempre es factible, o si el arreglo ya está ordenado no descendente.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int casos;
    cin >> casos;
    while (casos--) {
        int longitud, operaciones;
        cin >> longitud >> operaciones;
        vector<int> arreglo(longitud);
        for (int i = 0; i < longitud; i++) cin >> arreglo[i];
        if (operaciones > 1) {
            cout << "YES" << endl;
            continue;
        }
        bool ordenado = true;
        for (int i = 1; i < longitud; i++) {
            if (arreglo[i] < arreglo[i-1]) {
                ordenado = false;
                break;
            }
        }
        cout << (ordenado ? "YES" : "NO") << endl;
    }
    return 0;
}

Problema B: Sala de Almacenamiento

Este problema implica reconstruir un arreglo a partir de una matriz de operaciones OR. La solución utiliza un enfoque de conteo de bits para determinar los valores originales del arreglo mediante mapas y operaciones bitwise.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int tamano;
    cin >> tamano;
    vector<vector<int>> matriz(tamano, vector<int>(tamano));
    for (int i = 0; i < tamano; i++)
        for (int j = 0; j < tamano; j++)
            cin >> matriz[i][j];
    
    vector<int> valores(tamano, 0);
    for (int i = 0; i < tamano; i++) {
        map<int, int> conteoBits;
        for (int j = 0; j < tamano; j++) {
            if (i == j) continue;
            int valor = matriz[i][j];
            for (int bit = 0; bit < 30; bit++) {
                if ((valor >> bit) & 1) {
                    conteoBits[1 << bit]++;
                }
            }
        }
        for (auto [bit, cnt] : conteoBits) {
            if (cnt == tamano - 1) {
                valores[i] += bit;
            }
        }
    }
    
    for (int i = 0; i < tamano; i++) {
        for (int j = 0; j < tamano; j++) {
            if (i == j) continue;
            if ((valores[i] | valores[j]) != matriz[i][j]) {
                cout << "NO" << endl;
                return 0;
            }
        }
    }
    
    cout << "YES" << endl;
    for (int i = 0; i < tamano; i++) cout << valores[i] << " ";
    cout << endl;
    return 0;
}

Problema C: La Pesadilla de Theofanis

El objetivo es maximizar una suma ponderada segmentando un arreglo. La solución emplea una estrategia greedy con una cola doble, basándose en prefijos negativos para agrupar elementos y calcular la contribución óptima.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> arr(n);
    vector<long long> prefijo(n+1, 0);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        prefijo[i+1] = prefijo[i] + arr[i];
    }
    
    deque<long long> segmentos;
    for (int i = 0; i < n; i++) {
        long long restante = prefijo[n] - prefijo[i];
        if (restante < 0) {
            if (!segmentos.empty()) {
                segmentos.back() += arr[i];
            } else {
                segmentos.push_back(arr[i]);
            }
        } else {
            segmentos.push_back(arr[i]);
        }
    }
    
    long long total = 0;
    for (size_t i = 0; i < segmentos.size(); i++) {
        total += segmentos[i] * (i + 1);
    }
    cout << total << endl;
    return 0;
}

Problema D1: Consultas de AND Máximo (versión fácil)

Se busca maximizar el resultado de operaciones AND en un arreglo mediante incrementos controlados. La solución implementa un enfoque greedy con programación dinámica de bits, calculando costos para establecer bits individuales y optimizando el uso de operaciones disponibles.

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e5 + 5;
long long arreglo[MAX_N], temporal[MAX_N], resultado[105];
int numElementos, consultas;

long long calcularCosto(int posBit, long long limite) {
    long long costo = 0;
    for (int j = 1; j <= numElementos; j++) {
        if ((temporal[j] & (1LL << posBit)) == 0) {
            costo += (1LL << posBit) - ((1LL << (posBit + 1)) - 1LL & temporal[j]);
            if (costo > limite) return costo;
        }
    }
    return costo;
}

void resolver(long long k) {
    memset(resultado, 0, sizeof(resultado));
    for (int i = 1; i <= numElementos; i++) {
        temporal[i] = arreglo[i];
    }
    for (int i = 60; i >= 0; i--) {
        long long costo = calcularCosto(i, k);
        if (costo <= k) {
            resultado[i] = 1;
            k -= costo;
            for (int j = 1; j <= numElementos; j++) {
                if ((temporal[j] & (1LL << i)) == 0) {
                    temporal[j] = ((temporal[j] | (1LL << i)) & (1LL << i));
                }
            }
        }
    }
    long long res = 0;
    for (int i = 0; i <= 60; i++) {
        res |= (resultado[i] << i);
    }
    cout << res << endl;
}

int main() {
    cin >> numElementos >> consultas;
    for (int i = 1; i <= numElementos; i++) {
        cin >> arreglo[i];
    }
    while (consultas--) {
        long long k;
        cin >> k;
        resolver(k);
    }
    return 0;
}