Problema 1: Bonecas Russas

Este problema envolve o empilhamento de bonecas russas (matryoshka). Cada boneca possui um diâmetro R e uma altura H. Uma boneca pode conter apenas outras bonecas com diâmetro e altura estritamente menores. O objetivo é determinar, para cada consulta (A, B), quantas bonecas podem ser aninhadas otimamente considerando apenas aquelas com diâmetro ≥ A e altura ≤ B.

A abordagem utilizar BIT (Binary Indexed Tree) para manter o máximo de aninhamentos possíveis. Primeiro, discretizamos todas as alturas presetnes, tanto das bonecas quanto das consultas. Depois, ordenamos as bonecas por diâmetro decrescente e processamos as consultas em ordem.

A seguir, apresentamos uma implementação em C++:

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

struct Item {
    int dim;
    int alt;
    int ind;
};

int n, q;
int BIT[500010];
int resultado[500010];
vector<int> valores;

int consulta(int idx) {
    int resp = 0;
    while (idx > 0) {
        resp = max(resp, BIT[idx]);
        idx -= idx & (-idx);
    }
    return resp;
}

void atualiza(int idx, int valor) {
    while (idx <= (int)valores.size()) {
        BIT[idx] = max(BIT[idx], valor);
        idx += idx & (-idx);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> q;
    vector<Item> bonecas(n);
    vector<Item> consultas(q);
    
    for (int i = 0; i < n; i++) {
        cin >> bonecas[i].dim >> bonecas[i].alt;
        valores.push_back(bonecas[i].alt);
    }
    
    for (int i = 0; i < q; i++) {
        cin >> consultas[i].dim >> consultas[i].alt;
        consultas[i].ind = i;
        valores.push_back(consultas[i].alt);
    }
    
    sort(valores.begin(), valores.end());
    valores.erase(unique(valores.begin(), valores.end()), valores.end());
    
    sort(bonecas.begin(), bonecas.end(), [](const Item& a, const Item& b) {
        return a.dim > b.dim;
    });
    sort(consultas.begin(), consultas.end(), [](const Item& a, const Item& b) {
        return a.dim > b.dim;
    });
    
    int ptr = 0;
    for (const auto& consul : consultas) {
        while (ptr < n && bonecas[ptr].dim >= consul.dim) {
            int pos = lower_bound(valores.begin(), valores.end(), bonecas[ptr].alt) - valores.begin() + 1;
            int val = 1 + consulta(pos);
            atualiza(pos, val);
            ptr++;
        }
        int pos = upper_bound(valores.begin(), valores.end(), consul.alt) - valores.begin();
        resultado[consul.ind] = consulta(pos);
    }
    
    for (int i = 0; i < q; i++) {
        cout << resultado[i] << '\n';
    }
    
    return 0;
}

Problema 2: Barracas

Este problema combinatorial trata de posicionar barracas em uma grade. Cada linha e cada coluna pode conter no máximo 2 barracas. Após posicionar uma barrada em (i, j), a linha i e coluna j não podem receber mais barracas.

A solução utiliza programação dinâmica bidimensional. Definimos f[i][j] como o número de maneiras de posicionar barracas considerando as primeiras i linhas e primeiras j colunas.

Existem três casos principais:

• Uma única baraca: Pode ser posicionada em 4 direções diferentes. A fórmula é: 4 × f[i-1][j-1] × C(j,1)
• Duas barracas na mesma linha: Ocupa uma linha e duas colunas: f[i-1][j-2] × C(j,2)
• Duas barracas na mesma coluna: Ocupa duas linhas e uma coluna: f[i-2][j-1] × C(i-1,1) × C(j,1)

Como podem existir células vazias, o resultado final cosnidera todas as combinações possíveis de linhas e colunas utilizadas:

∑(i=1..H) ∑(j=1..W) f[i][j] × C(H,i) × C(W,j)

Implementação em C++:

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;

long long combinacoes[3010][3010];
long long dp[3010][3010];

long long mul_mod(long long a, long long b) {
    return (a % MOD) * (b % MOD) % MOD;
}

long long add_mod(long long a, long long b) {
    return (a % MOD + b % MOD) % MOD;
}

int main() {
    long long H, L;
    cin >> H >> L;
    
    int maxN = max(H, L);
    
    for (int i = 0; i <= maxN; i++) {
        combinacoes[i][0] = combinacoes[i][i] = 1;
        for (int j = 1; j < i; j++) {
            combinacoes[i][j] = add_mod(combinacoes[i-1][j], combinacoes[i-1][j-1]);
        }
    }
    
    dp[0][0] = 1;
    
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= L; j++) {
            long long caso1 = mul_mod(4LL, mul_mod(dp[i-1][j-1], j));
            dp[i][j] = add_mod(dp[i][j], caso1);
            
            if (j >= 2) {
                long long caso2 = mul_mod(dp[i-1][j-2], combinacoes[j][2]);
                dp[i][j] = add_mod(dp[i][j], caso2);
            }
            
            if (i >= 2) {
                long long caso3 = mul_mod(dp[i-2][j-1], mul_mod(i-1, j));
                dp[i][j] = add_mod(dp[i][j], caso3);
            }
        }
    }
    
    long long resposta = 0;
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= L; j++) {
            long long termo = mul_mod(dp[i][j], mul_mod(combinacoes[H][i], combinacoes[L][j]));
            resposta = add_mod(resposta, termo);
        }
    }
    
    cout << resposta << '\n';
    
    return 0;
}

Estes problemas demonstram aplicações importantes de estruturas de dados (BIT) e programação dinâmica combinatorial em competições de programação.