Neste artigo, exploraremos as soluções para dois desafios algorítmicos distintos, focando nas abordagens de design e nas estruturas de dados empregadas para otimização.

Problema 1: Reconstrução de Sequência Numérica com Propriedades de Origem

O primeiro problema exige uma análise cuidadosa da origem de cada elemento na sequência final. Considere que cada posição na sequência resultante deriva de uma posição original. A chave para a solução reside na observação de uma propriedade fundamental:

Propriedade de Origem: Se múltiplos elementos na sequência final compartilham a mesma origem na sequência inicial, a soma desses elementos, quando considerada módulo 10, será congruente ao valor do dígito na posição de origem correspondente. Isso ocorre porque todas as operações subsequentes mantêm essa relação modular para o conjunto de números derivados da mesma fonte.

Com base nesta propriedade, podemos empregar uma estratégia gulosa para preencher os valores. Para um grupo de k posições que se originaram do mesmo ponto na sequência inicial, podemos maximizar o valor preenchendo k-1 dessas posições com o dígito 9. O valor da última posição neste grupo pode então ser determinado utilizando a propriedade de origem e os valores já atribuídos (os 9s), garantindo que a soma modular seja mantida.

Implementação do Problema 1

A implementação envolve o rastreamento das origens e a aplicação da lógica gulosa. Primeiro, a sequência de dígitos inicial é lida e invertida para facilitar o processamento das posições. As operações de expansão são simuladas para determinar a origem final de cada nova posição. Um vetor de pares armazena a origem e o índice da posição, permitindo a ordenação para processar grupos de origens iguais de forma eficiente. Finalmente, os dígitos são atribuídos aplicando a estratégia gulosa.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility> // Para std::pair

// Usando aliases para namespaces comuns
using std::cin;
using std::cout;

const int MAX_LEN = 3000000 + 10; // Tamanho máximo da sequência final

int tamanho_original; // N original
int contagem_origem[MAX_LEN]; // Conta quantas vezes cada origem aparece
int digitos_iniciais[MAX_LEN]; // Sequência de dígitos original
int fonte_expandida[MAX_LEN]; // Mapeia posições expandidas para posições anteriores
int resultado_final[MAX_LEN]; // Sequência de dígitos final
int origem_final[MAX_LEN]; // Mapeia cada posição final para sua origem inicial
std::vector<std::pair<int, int>> pares_origem_indice; // (Origem, Índice na sequência final)

int main() {
    std::ios_base::sync_with_stdio(false); // Otimização de E/S
    cin.tie(NULL);

    int num_operacoes; // M operações
    cin >> num_operacoes;

    char caractere_atual;
    // Pular caracteres não-dígitos
    do {
        caractere_atual = getchar();
    } while (!isdigit(caractere_atual));

    // Ler os dígitos da sequência original
    while (isdigit(caractere_atual)) {
        digitos_iniciais[++tamanho_original] = caractere_atual - '0';
        caractere_atual = getchar();
    }

    // Inverter a sequência original para processamento do "fim para o começo"
    std::reverse(digitos_iniciais + 1, digitos_iniciais + tamanho_original + 1);

    int indice_esq = 1; // Ponteiro para o lado esquerdo da "janela" original
    int indice_dir = tamanho_original; // Ponteiro para o lado direito da "janela" original

    // Simular as operações de expansão (2 novas posições para cada original)
    for (int op = 1; op <= num_operacoes; ++op) {
        fonte_expandida[++indice_dir] = indice_esq;
        fonte_expandida[++indice_dir] = indice_esq;
        indice_esq++;
    }

    // Calcular a origem final para cada posição da sequência expandida
    for (int i = 1; i <= tamanho_original; ++i) {
        origem_final[i] = i; // Posições originais mapeiam para si mesmas
    }
    for (int i = tamanho_original + 1; i <= indice_dir; ++i) {
        origem_final[i] = origem_final[fonte_expandida[i]]; // Propagação da origem
    }

    // Coletar pares (origem, índice) para todas as posições relevantes
    for (int i = indice_esq; i <= indice_dir; ++i) {
        contagem_origem[origem_final[i]]++;
        pares_origem_indice.emplace_back(origem_final[i], i);
    }

    // Ordenar para agrupar posições com a mesma origem
    std::sort(pares_origem_indice.begin(), pares_origem_indice.end());

    int origem_atual = 0; // Para rastrear a origem sendo processada
    for (auto const& par : pares_origem_indice) {
        if (origem_atual != par.first) {
            // Nova origem, calcular o dígito para a primeira ocorrência
            origem_atual = par.first;
            // Usa (num[origem_atual] - (k-1)*9) mod 10
            long long valor_calculado = (long long)digitos_iniciais[origem_atual] - 1LL * (contagem_origem[origem_atual] - 1) * 9;
            resultado_final[par.second] = (valor_calculado % 10 + 10) % 10;
        } else {
            // Outras ocorrências da mesma origem recebem 9
            resultado_final[par.second] = 9;
        }
    }

    // Imprimir o resultado final na ordem correta (inversa da leitura)
    for (int i = indice_dir; i >= indice_esq; --i) {
        cout << resultado_final[i];
    }
    cout << '\n';

    return 0;
}

Problema 2: Otimização de Compra e Venda de Itens

Este problema envolve a gestão de um inventário de itens com custos de compra (a_i) e valores de venda (b_i), onde a contagem de moedas pode se tornar negativa durante as operações. O objetivo é maximizar o número de itens comprados, dadas as restrições.

Uma abordagem eficaz é iterar sobre cada item p, assumindo que ele é o último item a ser comprado. Para cada p, precisamos otimizar a seleção dos itens anteriores e posteriores.

**Transformação do Problema:**Para simplificar, podemos ajustar os custos. Se um item i ≤ p for comprado, ele consome a_i moedas e adiciona b_i ao nosso saldo inicial (como se tivéssemos ∑ b_j moedas onde j ≤ p). Se ele for vendido, ele nos "custa" a_i + b_i para não comprá-lo e ainda obter o benefício b_i. Itens i > p custam apenas a_i para serem comprados.

**Restrições e Casos:**1. **Limite de Vendas:** Podemos vender no máximo m itens. Isso implica que, dos p primeiros itens, devemos comprar pelo menos p - m. 2. **Vendas Insuficientes:** Se vendermos menos de m itens no total, significa que compramos todos os itens restantes. Este é um caso mais simples que pode ser resolvido com uma estratégia gulosa direta. 3. **Vendas Exatas:** A situação mais complexa ocorre quando vendemos exatamente m itens. Para este caso, precisamos selecionar os p - m itens mais baratos entre os primeiros p itens (considerando o custo ajustado a_i + b_i para "não comprá-los" ou vendê-los), e então selecionar itens adicionais dos n-p itens restantes que possam ser comprados com o saldo restante.

Estruturas de Dados para Otimização:

• **Fila de Prioridade (Min-Heap):** Armazena os custos a_i + b_i para os itens i ≤ p que podem ser "vendidos" (ou seja, não comprados para liberar espaço para outros). A min-heap nos permite sempre remover o item com menor custo de "venda", garantindo que compramos os p - m itens mais caros (ou vendemos os m itens mais baratos).
• **Árvore de Segmentos (Segment Tree):** Gerencia os custos a_i dos itens i > p. Esta estrutura permite consultas eficientes para determinar quantos itens podem ser comprados com um determinado saldo restante, além de atualizar as contagens de itens disponíveis. A árvore de segmentos deve suportar a consulta de prefixos (quantos itens posso comprar até um certo custo) e a atualização de valores de itens individuais.

Algoritmo Principal:

1. Inicialize o saldo com a soma de todos os b_i dos itens até p.
2. Para cada item i de 1 a n (servindo como o potencial "último item comprado" p):
   • Adicione a_i + b_i à min-heap (itens que podem ser "vendidos").
   • Remova a_i do segmento de árvore (itens que podem ser "comprados" posteriormente, mas estão sob consideração de i como último).
   • Se i < m, continue para o próximo item (ainda não há m itens para "vender").
   • Se i >= m:
     • Se i > m, removemos o menor (a_j + b_j) da min-heap e ajustamos o saldo, pois estamos fixando m itens para serem "vendidos" entre os primeiros i.
     • Verifique se o saldo é suficiente. Se negativo, continue.
     • O número de itens comprados até agora é i - m (items fixados para compra).
     • Use a árvore de segmentos para consultar quantos itens adicionais podem ser comprados dos itens i+1 a n com o saldo restante.
     • Atualize a resposta máxima.
3. Após o loop, considere o caso em que todos os itens são comprados (ou seja, vendemos 0 itens, que é < m).

Implementação do Problema 2

A implementação utiliza compressão de coordenadas para os valores a_i para gerenciar a árvore de segmentos de forma eficiente. A árvore de segmentos armazena a soma total dos custos e a contagem de itens em um dado intervalo de custos. A fila de prioridade armazena os custos ajustados para os itens à esquerda do "último item comprado".

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue> // Para std::priority_queue
#include <map> // Para compressão de coordenadas, alternativamente std::vector e sort/unique

using std::cin;
using std::cout;
typedef long long ll;

const int MAX_N_ITENS = 500000 + 10; // Máximo de itens

// Estrutura para nós da árvore de segmentos
struct InfoNo {
    ll soma_custos;
    ll contagem_itens;

    // Sobrecarga do operador + para combinar informações de nós filhos
    friend InfoNo operator+(const InfoNo& esquerda, const InfoNo& direita) {
        InfoNo resultado;
        resultado.soma_custos = esquerda.soma_custos + direita.soma_custos;
        resultado.contagem_itens = esquerda.contagem_itens + direita.contagem_itens;
        return resultado;
    }
};

InfoNo arvore_segmentos[MAX_N_ITENS << 2]; // Árvore de segmentos, tamanho 4*N

// Macros para navegação na árvore de segmentos
#define ID_RAIZ 1, num_valores_unicos, 1
#define FILHO_ESQ esq, meio, no_idx << 1
#define FILHO_DIR meio + 1, dir, no_idx << 1 | 1

int custo_compra[MAX_N_ITENS]; // Custos 'a_i'
int valor_venda[MAX_N_ITENS]; // Valores 'b_i'

// Arrays para compressão de coordenadas
int contagem_valor_mapeado[MAX_N_ITENS]; // Contagem de cada valor 'a_i' mapeado
int mapeamento_valor[MAX_N_ITENS]; // Mapeamento de 'a_i' original para índice comprimido
int valor_real_mapeado[MAX_N_ITENS]; // Valor 'a_i' real para um índice comprimido

std::vector<int> valores_unicos_a; // Todos os valores 'a_i' únicos para compressão
std::priority_queue<int, std::vector<int>, std::greater<int>> fila_prioridade_vendas; // Min-heap para a_i + b_i

// Constrói a árvore de segmentos
void construir_arvore(int esq, int dir, int no_idx) {
    if (esq == dir) {
        arvore_segmentos[no_idx].contagem_itens = contagem_valor_mapeado[esq];
        arvore_segmentos[no_idx].soma_custos = 1LL * contagem_valor_mapeado[esq] * valor_real_mapeado[esq];
        return;
    }
    int meio = (esq + dir) >> 1;
    construir_arvore(FILHO_ESQ);
    construir_arvore(FILHO_DIR);
    arvore_segmentos[no_idx] = arvore_segmentos[no_idx << 1] + arvore_segmentos[no_idx << 1 | 1];
}

// Diminui a contagem de um item na árvore de segmentos
void diminuir_contagem(int esq, int dir, int no_idx, int pos_mapeada) {
    if (esq == dir) {
        arvore_segmentos[no_idx].contagem_itens--;
        arvore_segmentos[no_idx].soma_custos -= valor_real_mapeado[esq];
        return;
    }
    int meio = (esq + dir) >> 1;
    if (pos_mapeada <= meio) {
        diminuir_contagem(FILHO_ESQ, pos_mapeada);
    } else {
        diminuir_contagem(FILHO_DIR, pos_mapeada);
    }
    arvore_segmentos[no_idx] = arvore_segmentos[no_idx << 1] + arvore_segmentos[no_idx << 1 | 1];
}

// Consulta quantos itens podem ser comprados com um dado saldo máximo 'saldo_max'
// Retorna a contagem de itens
int consultar_max_itens(int esq, int dir, int no_idx, ll saldo_max) {
    if (arvore_segmentos[no_idx].soma_custos <= saldo_max) {
        return arvore_segmentos[no_idx].contagem_itens; // Todo o subárvore pode ser comprada
    }
    if (esq == dir) {
        // No folha: quantos itens com este custo podem ser comprados
        return std::min((ll)arvore_segmentos[no_idx].contagem_itens, saldo_max / valor_real_mapeado[esq]);
    }
    int meio = (esq + dir) >> 1;
    if (arvore_segmentos[no_idx << 1].soma_custos > saldo_max) {
        // Se a subárvore esquerda excede o saldo, consulte apenas nela
        return consultar_max_itens(FILHO_ESQ, saldo_max);
    }
    // Caso contrário, compre tudo da esquerda e use o saldo restante para a direita
    return arvore_segmentos[no_idx << 1].contagem_itens + consultar_max_itens(FILHO_DIR, saldo_max - arvore_segmentos[no_idx << 1].soma_custos);
}

int main() {
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int num_itens, max_vendas; // N e M do problema
    cin >> num_itens >> max_vendas;

    for (int i = 1; i <= num_itens; ++i) {
        cin >> custo_compra[i] >> valor_venda[i];
        valores_unicos_a.push_back(custo_compra[i]); // Coletar valores para compressão
    }

    // Compressão de coordenadas para os custos 'a_i'
    std::sort(valores_unicos_a.begin(), valores_unicos_a.end());
    valores_unicos_a.erase(std::unique(valores_unicos_a.begin(), valores_unicos_a.end()), valores_unicos_a.end());

    int num_valores_unicos = valores_unicos_a.size(); // Número de IDs únicos após compressão
    for (int i = 1; i <= num_itens; ++i) {
        // Mapear custo_compra[i] para um índice comprimido (1-baseado)
        mapeamento_valor[i] = std::lower_bound(valores_unicos_a.begin(), valores_unicos_a.end(), custo_compra[i]) - valores_unicos_a.begin() + 1;
        valor_real_mapeado[mapeamento_valor[i]] = custo_compra[i]; // Armazenar o valor real no índice comprimido
        contagem_valor_mapeado[mapeamento_valor[i]]++; // Contar ocorrências para a árvore
    }

    construir_arvore(ID_RAIZ); // Construir a árvore de segmentos inicialmente

    ll saldo_atual = 0; // Saldo de moedas
    int max_itens_comprados = 0; // Resposta final

    // Loop principal: 'i' é o item atual sob consideração como o "último comprado"
    for (int i = 1; i <= num_itens; ++i) {
        saldo_atual += valor_venda[i]; // Adicionar valor de venda ao saldo
        fila_prioridade_vendas.push(custo_compra[i] + valor_venda[i]); // Adicionar custo de 'venda' ao heap
        diminuir_contagem(ID_RAIZ, mapeamento_valor[i]); // Remover este item da árvore de segmentos (agora considerado na "janela" esquerda)

        if (i < max_vendas) { // Se não temos itens suficientes para vender 'm'
            continue;
        }

        // Se a janela esquerda (itens 1 a i) tem mais que 'm' itens para "vender",
        // removemos o mais barato (já que queremos maximizar compras)
        if (fila_prioridade_vendas.size() > max_vendas) {
            saldo_atual -= fila_prioridade_vendas.top(); // Remover o custo de "venda" do mais barato
            fila_prioridade_vendas.pop();
        }

        if (saldo_atual < 0) { // Se o saldo for negativo, não podemos comprar nada
            continue;
        }
        
        // i - max_vendas = número de itens comprados obrigatoriamente da esquerda
        // consultar_max_itens busca os itens mais baratos à direita
        max_itens_comprados = std::max(max_itens_comprados, i - max_vendas + consultar_max_itens(ID_RAIZ, saldo_atual));
    }

    // Caso especial: Considerar comprar todos os itens se possível (menos de 'max_vendas' vendidos)
    // Para isso, calculamos a soma de todos (a_i + b_i) e vemos quantos podem ser "vendidos"
    ll saldo_total_para_todos = 0;
    std::vector<int> custos_venda_total; // Para calcular o cenário de todos
    for (int i = 1; i <= num_itens; ++i) {
        saldo_total_para_todos += valor_venda[i];
        custos_venda_total.push_back(custo_compra[i] + valor_venda[i]);
    }
    std::sort(custos_venda_total.begin(), custos_venda_total.end());

    int itens_comprados_se_todos = num_itens;
    for (int custo_venda_item : custos_venda_total) {
        if (saldo_total_para_todos >= custo_venda_item) {
            saldo_total_para_todos -= custo_venda_item;
            itens_comprados_se_todos--; // Este item não foi comprado (foi "vendido")
        } else {
            break;
        }
    }
    max_itens_comprados = std::max(max_itens_comprados, itens_comprados_se_todos);


    cout << max_itens_comprados << '\n';

    return 0;
}