A prova da CSP 2025 apresentou desafios clássicos de programação competitiva, exigindo conhecimentos sólidos em algoritmos de grafos, manipulação de strings e técnicas de otimização de busca. Abaixo, detalhamos as abordagens para os probleams centrais, focando em complexidade e implementação eficiente.

Problema 1: Otimização de Atribuição com Restrições de Carga

O primiero problema exigia a seleção de valores máximos entre três categorias para $n$ elementos, sob a restrição de que nenhuma categoria poderia conter mais de $n/2$ elementos. A estratégia inicial consiste em uma abordagem gulosa, seguida por um ajuste baseado no menor custo de oportunidade para reequilibrar as categorias excedentes.

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

using namespace std;

struct Item {
    int v[4];
};

void processarCaso() {
    int n;
    cin >> n;
    vector<Item> dados(n + 1);
    int contadores[4] = {0, 0, 0, 0};
    long long somaTotal = 0;
    vector<int> diferencas[4];

    for (int i = 1; i <= n; i++) {
        cin >> dados[i].v[1] >> dados[i].v[2] >> dados[i].v[3];
        int melhor = 1;
        if (dados[i].v[2] > dados[i].v[melhor]) melhor = 2;
        if (dados[i].v[3] > dados[i].v[melhor]) melhor = 3;

        contadores[melhor]++;
        somaTotal += dados[i].v[melhor];
        
        // Calcula a penalidade mínima para mudar de categoria
        int diff1 = dados[i].v[melhor] - (melhor == 1 ? max(dados[i].v[2], dados[i].v[3]) : (melhor == 2 ? max(dados[i].v[1], dados[i].v[3]) : max(dados[i].v[1], dados[i].v[2])));
        diferencas[melhor].push_back(diff1);
    }

    int limite = n / 2;
    for (int c = 1; c <= 3; c++) {
        if (contadores[c] > limite) {
            sort(diferencas[c].begin(), diferencas[c].end());
            int excesso = contadores[c] - limite;
            for (int j = 0; j < excesso; j++) {
                somaTotal -= diferencas[c][j];
            }
        }
    }
    cout <> somaTotal << endl;
}

Problema 2: Árvore Geradora Mínima com Pontos Extras (Bitmask)

Este problema envolvia a construção de uma Árvore Geradora Mínima (MST) em um grafo onde pontos adicionais (centros rurais) poderiam ser ativados. Como o número de centros $k$ é pequeno, a técnica de Bitmask é ideal para explorar todas as combinações de ativação.

A otimização crucial reside em perceber que as arestas da MST original do grafo base são as únicas candidatas necessárias entre os nós principais. Ao adicionar um centro rural, novas arestas são conectadas a todos os nós $n$, e a complexidade pode ser mantida sob controle pré-ordenando as arestas.

#include <vector>
#include <algorithm>

struct Conexao {
    int de, para, custo;
};

bool compararCusto(const Conexao& a, const Conexao& b) {
    return a.custo < b.custo;
}

struct DSU {
    std::vector<int> pai;
    DSU(int n) { pai.resize(n + 1); for(int i=0; i<=n; i++) pai[i]=i; }
    int localizar(int x) { return pai[x] == x ? x : pai[x] = localizar(pai[x]); }
    bool unir(int a, int b) {
        int rA = localizar(a), rB = localizar(b);
        if (rA != rB) { pai[rA] = rB; return true; }
        return false;
    }
};

long long resolverMST(int n, int k, std::vector<Conexao>& baseMST, std::vector<std::vector<int>>& custosExtras) {
    long long melhorResposta = 2e18; 
    
    for (int mask = 0; mask < (1 << k); mask++) {
        long long custoAtual = 0;
        std::vector<Conexao> arestasAtivas = baseMST;
        int componentes = n;

        for (int i = 0; i < k; i++) {
            if ((mask >> i) & 1) {
                custoAtual += custosExtras[i][0]; // Custo de ativação do centro
                componentes++;
                for (int j = 1; j <= n; j++) {
                    arestasAtivas.push_back({n + i + 1, j, custosExtras[i][j]});
                }
            }
        }

        std::sort(arestasAtivas.begin(), arestasAtivas.end(), compararCusto);
        DSU dsu(n + k);
        int arestasContadas = 0;
        for (auto& ed : arestasAtivas) {
            if (dsu.unir(ed.de, ed.para)) {
                custoAtual += ed.custo;
                arestasContadas++;
            }
        }
        if (arestasContadas == componentes - 1) {
            melhorResposta = std::min(melhorResposta, custoAtual);
        }
    }
    return melhorResposta;
}

Problema 3: Casamento de Padrões e Análise de Prefixos

O terceiro desafio focou em processamento de strings, exigindo encontrar ocorrências de padrões em textos transformados. A aplicação do algoritmo KMP (Knuth-Morris-Pratt) permite localizar sub-strings em tempo linear $O(|S| + |T|)$. No entanto, para consultas múltiplas, a eficiência depende de como as propriedades de prefixo e sufixo são comparadas após a substituição.

Um erro comum é o uso de estruturas de dados pesadas como std::map dentro de loops críticos, o que eleva a complexidade para $O(Q \cdot N \log N)$. A substituição por vetores de frequência ou técnicas de hash pode mitigar o TLE (Time Limit Exceeded).

#include <string>
#include <vector>

std::vector<int> calcular_pi(const std::string& p) {
    int m = p.length();
    std::vector<int> pi(m);
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && p[i] != p[j]) j = pi[j-1];
        if (p[i] == p[j]) j++;
        pi[i] = j;
    }
    return pi;
}

std::vector<int> buscar_kmp(const std::string& texto, const std::string& padrao) {
    std::vector<int> ocorrencias;
    if (padrao.empty()) return ocorrencias;
    std::vector<int> pi = calcular_pi(padrao);
    for (int i = 0, j = 0; i < texto.length(); i++) {
        while (j > 0 && texto[i] != padrao[j]) j = pi[j-1];
        if (texto[i] == padrao[j]) j++;
        if (j == padrao.length()) {
            ocorrencias.push_back(i - j + 1);
            j = pi[j-1];
        }
    }
    return ocorrencias;
}

Considerações de Complexidade e Performance

A análise pós-prova revelou que, no Problema 2, a reordenação das arestas (sort) dentro do loop da Bitmask foi o principal gargalo para muitos competidores. Mover a ordenação para fora e filtrar apenas as arestas necessárias reduz drasticamente o tempo de execução. No Problema 3, a transição de uma solução baseada em KMP simples para uma que utiliza Aho-Corasick ou Hash de Strings mostrou-se necessária para atingir a pontuação máxima em casos de teste com grandes volumes de consultas.