Este artigo apresenta um resumo das soluções para os problemas A, B, C, D e E do Codeforces Round 1017, Divisão 4. As soluções focam em otimização e lógica para resolver cada desafio de forma eficiente.

Problema A A tarefa consiste em receber três strings e concatenar o primeiro caractere de cada uma delas para formar a saída. A solução itera sobre as três strings de entrada e imprime o caractere na posição de índice 0 de cada uma, seguido por uma nova linha. Ver Código

#include <iostream>
#include <string>
#include <vector>

void solve() {
    std::vector<std::string> s(3);
    for (int i = 0; i < 3; ++i) {
        std::cin >> s[i];
    }
    for (int i = 0; i < 3; ++i) {
        std::cout << s[i][0];
    }
    std::cout << std::endl;
}

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

Problema B O problema envolve a propagação de um valor em um intervalo. A chave é que a propagação começa do meio. Precisamos construir um intervalo de comprimento m que contenha o zero e esteja dentro do intervalo [l, r]. A estratégia é estender o intervalo o máximo possível para a esquerda e, se necessário, esetnder para a direita. Ver Código

#include <iostream>
#include <algorithm>

void solve() {
    long long n, m, l, r;
    std::cin >> n >> m >> l >> r;
    // A condição principal é garantir que o intervalo de comprimento m
    // contenha o zero e esteja contido em [l, r].
    // Uma construção possível é tentar alocar o intervalo o mais à esquerda possível.
    // Se o limite inferior (-m) for menor que -l, significa que podemos
    // posicionar o intervalo de forma que seu início seja -m e seu fim seja 0.
    if (-m < l) { // Se o ponto mais à esquerda do nosso intervalo (-m) for maior que o limite l
        std::cout << l << " " << l + m << "\n";
    } else { // Caso contrário, podemos colocar o intervalo começando em -m
        std::cout << -m << " " << 0 << "\n";
    }
}

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

Problema C Neste problema, a soma i+j de posições na matriz é dada, exceto pela primeira posição. A única posição restante a ser preenchida é a primeira. A solução consiste em identificar qual número não foi usado nas somas dadas e colocá-lo na primeira posição. Ver Código

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

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> diag_sum(2 * n + 1, 0);
    std::vector<bool> used_num(2 * n + 1, false);
    int missing_num = -1;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int val;
            std::cin >> val;
            if (i + j <= 2 * n) { // Evita índice fora dos limites
                diag_sum[i + j] = val;
                used_num[val] = true;
            }
        }
    }

    // Encontrar o número que não foi usado
    for (int k = 1; k <= 2 * n; ++k) {
        if (!used_num[k]) {
            missing_num = k;
            break;
        }
    }
    
    diag_sum[1] = missing_num; // Coloca o número ausente na posição de soma 1 (a única não preenchida)

    for (int i = 1; i <= 2 * n; ++i) {
        std::cout << diag_sum[i] << (i == 2 * n ? "" : " ");
    }
    std::cout << std::endl;
}

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

Problema D Este problema aborda a expansão de strings compostas por 'L' e 'R'. A ideia é que sequências de 'L' podem se expandir para 'LL' e vice-versa. A solução verifica a viabilidade dessa expansão comparando sequências consecutivas de 'L' e 'R'. As condições de impossibilidade incluem a incompatibilidade na ordem de alternância entre 'L' e 'R', e casos onde uma expansão não é suficiente ou é excessiva. Ver Código

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

void solve() {
    std::string s, p;
    std::cin >> s >> p;
    int n = s.length();
    int m = p.length();

    // Condição inicial: se p for mais que o dobro de s, é impossível.
    if (m > n * 2) {
        std::cout << "NO\n";
        return;
    }

    int i = 0, j = 0; // Pointers para s e p
    while (i < n && j < m) {
        char current_char_s = s[i];
        char current_char_p = p[j];

        if (current_char_s != current_char_p) {
            std::cout << "NO\n";
            return;
        }

        // Conta repetições em s
        int count_s = 0;
        int temp_i = i;
        while (temp_i < n && s[temp_i] == current_char_s) {
            count_s++;
            temp_i++;
        }

        // Conta repetições em p
        int count_p = 0;
        int temp_j = j;
        while (temp_j < m && p[temp_j] == current_char_p) {
            count_p++;
            temp_j++;
        }

        // Condições de validade para expansão
        // count_p deve ser entre count_s e 2 * count_s
        if (count_p < count_s || count_p > 2 * count_s) {
            std::cout << "NO\n";
            return;
        }

        i = temp_i; // Avança o ponteiro de s
        j = temp_j; // Avança o ponteiro de p
    }

    // Se ambos os ponteiros chegaram ao fim, a string é válida
    if (i == n && j == m) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

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

Problema E Para calcular eficientemente a soma máxima após operações XOR, a abordagem de força bruta é inviável. A solução propõe calcular bit a bit. Para cada posição de bit (de 0 a 29), contamos a quantidade de números com bit 0 e bit 1. Em seguida, para cada número de entrada, calculamos o valor máximo que pode ser obtido XORando com outros números, considerando as contagens de bits. Ver Código

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath> // Para std::pow

// Função auxiliar para calcular potência, otimizada para base 2
long long power_of_2(int exp) {
    if (exp < 0) return 0; // Ou lance um erro, dependendo da necessidade
    return 1LL << exp;
}

void solve() {
    int n;
    std::cin >> n;
    std::vector<long long> a(n);
    // cnt[bit_pos][bit_value]: contagem de números com bit_value na posição bit_pos
    std::vector<std::vector<int>> cnt(30, std::vector<int>(2, 0));

    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        for (int j = 0; j < 30; ++j) {
            if ((a[i] >> j) & 1) {
                cnt[j][1]++;
            } else {
                cnt[j][0]++;
            }
        }
    }

    long long max_xor_sum = 0;

    for (int i = 0; i < n; ++i) {
        long long current_xor_sum = 0;
        for (int j = 0; j < 30; ++j) {
            // Se o j-ésimo bit de a[i] é 1
            if ((a[i] >> j) & 1) {
                // O resultado XOR terá 0 neste bit se o outro número tiver 1.
                // A contagem de números com 1 neste bit é cnt[j][1].
                // A contribuição para a soma é cnt[j][1] * (2^j).
                current_xor_sum += (long long)cnt[j][1] * power_of_2(j);
            } else { // Se o j-ésimo bit de a[i] é 0
                // O resultado XOR terá 1 neste bit se o outro número tiver 1.
                // A contagem de números com 1 neste bit é cnt[j][1].
                // A contribuição para a soma é cnt[j][1] * (2^j).
                current_xor_sum += (long long)cnt[j][1] * power_of_2(j);
            }
        }
        max_xor_sum = std::max(max_xor_sum, current_xor_sum);
    }
    std::cout << max_xor_sum << "\n";
}

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