Problemas de Programação Competitiva: Contagem de Inversões

Neste artigo, exploraremos soluções para problemas de contagem de inversões, abordando tanto abordagens diretas quanto soluções otimizadas usando programação dinâmica com soma de prefixos.

Problema 1: Contagem de Inversões (P1521)

O problema consiste em encontrar o número de permutações de tamanho N com exatamente K inversões. Uma inversão ocorre quando em uma sequência ordenada, um elemento precede outro elemento manor.

Solução Bruta (30 pontos)

Uma abordagem inicial é gerar todas as permutações possíveis e contar as inversões em cada uma. Embora ineficiente para valores grandes de N, pode render pontos significativos em competições.

#include <bits>
using namespace std;

int n, k;
long long resultado = 0;
int sequencia[1010];

int main() {
    cin >> n >> k;
    
    // Inicializa a primeira permutação
    long long total_permutacoes = 1;
    for (int i = 1; i <= n; i++) {
        sequencia[i] = i;
        total_permutacoes *= i;
    }
    
    // Conta permutações com exatamente K inversões
    for (int i = 1; i <= total_permutacoes; i++) {
        next_permutation(sequencia + 1, sequencia + n + 1);
        
        int inversoes = 0;
        for (int x = 1; x <= n; x++)
            for (int y = x + 1; y <= n; y++)
                if (sequencia[x] > sequencia[y]) 
                    inversoes++;
        
        if (inversoes == k) 
            resultado++;
    }
    
    cout << resultado % 10000 << endl;
    return 0;
}
</bits>

Solução Otimizada com Programação Dinâmica

Uma abordagem mais eficiente usa programação dinâmica com otimização de soma de prefixos. Definimos dp[i][j] como o número de sequências com i elementos que contêm exatamente j inversões.

A transição de estado considera onde o i-ésimo elemento é inserido na sequência existente. Cada posição de inserção adiciona um número diferente de inversões:

#include <bits>
using namespace std;

int n, k;
int dp[5010][5010];

int main() {
    scanf("%d%d", &n, &k);
    
    // Casos base
    dp[1][0] = 1;
    dp[2][0] = 1;
    dp[2][1] = 1;
    dp[0][0] = 1;
    
    // Programação dinâmica com otimização
    for (int i = 3; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            // Soma das transições possíveis
            for (int q = 0; q <= min(i - 1, j); q++) {
                dp[i][j] = (dp[i - 1][j - q] + dp[i][j]) % 10000;
            }
        }
    }
    
    printf("%d\n", dp[n][k]);
    return 0;
}
</bits>

Análise da Solução Otimizada

A solução otimizada explora a relação entre o i-ésimo elemento e a sequência dos primeiros i-1 elementos. Ao inserir o novo elemento em diferentes posições, podemos controlar quantas novas inversões são adicionadas à sequência existente.

A complexidade temporal é O(N*K*N), mas pode ser otimizada para O(N*K) usando somas de prefixos para evitar o loop interno mais profundo.

Problemas Relacionados

Outros problemas interessantes nesta categoria incluem:

• P2511: Divisão de Varas - Problema de dificuldade superior que requer técnicas avançadas de programação dinâmica
• Problemas de Mesclagem de Pedras - Variações clássicas que podem ser resolvidas com abordagens semelhantes

É fundamental dominar tanto soluções diretas quanto otimizadas. As soluções brutas frequentemente fornecem insights cruciais para desenvolver algoritmos mais eficientes.