Introdução aos Problemas Selecionados

A competição apresentada exigiu uma aplicação eficiente de conceitos fundamentais de algoritmos e estruturas de dados. Abaixo, detalhamos as abordagens utilizadas para resolver os quatro problemas propostos, focando na lógica implementada e na otimização de complexidade.

Problema 1: Simulação de Trajetória de Balões

O primeiro desafio consistia em determinar qual balão alcançava a maior altitude em um instante específico T. Dado que o tempo de lançamento t_i e a velocidade v_i são constantes para cada balão, a altura no momento de interesse é calculada diretamente como o produto entre a diferença temporal e a velocidade.

A solução ótima envolve iterar sobre todos os balões existentes e manter o registro do máximo encontrado até o momento, armazenando também o índice correspondente para resposta final. Essa abordagem linear garante uma eficiência de O(n), adequada para os limites de entrada.

#include <iostream>
#include <algorithm>

using namespace std;

// Definição de estrutura para representar o estado atual
struct Balao {
    int id;
    long long velocidade;
    long long tempoLancamento;
};

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

    int n; 
    long long tFinal;
    
    if (!(cin >> n >> tFinal)) return 0;

    int melhorIndice = -1;
    long long alturaMaxima = -1;

    for (int i = 0; i < n; ++i) {
        long long v, tInicial;
        cin >> v >> tInicial;
        
        // Cálculo da altura se estiver voando após o lançamento
        if (tFinal >= tInicial) {
            long long alt = (tFinal - tInicial) * v;
            
            if (alt > alturaMaxima) {
                alturaMaxima = alt;
                melhorIndice = i + 1; // Índices baseados em 1
            }
        }
    }

    cout << melhorIndice << "\n";

    return 0;
}

Problema 2: Construção de Strings e Recursos

Este problema envolve a construção de uma sequência de caracteres minimizando a ordem lexicográfica sob restrições específicas. Identificou-se primeiramente que existe um limite superior imposto pela quantidade total de recursos disponíveis (representados por glaciares ou números específicos).

Se a demanda exceder a capacidade de processamento inicial, a situação é inválida. Para garantir a menor ordem alfabética possível, a estratégia guloza recomenda selecionar o recurso mener disponível sempre que a instrução permitir ('Y'), ou iterar sequencialmente pelos recursos remanescentes ao processar a instrução restritiva ('N'). A verificação de disponibilidade é feita dinamicamente durante a geração da string.

A complexidade operacional situa-se em O(m), onde m representa o tamanho da saída ou da instrução.

Problema 3: Gerenciamento de Retas no Plano Cartesiano

Esta tarefa requer operações de adição, consulta e remoção de linhas definidas pela forma geral y = kx + b.

Operações:

• Adicionar: Insere a linha no conjunto e atualiza os contadores de frequências para coeficiente angular (k) e coeficiente linear (b).
• Consultar: Retorna a quantidade de retas que não são paralelas àquela especificada no input.
• Remover: Filtra todas as retas com um par específico (k, b) e compacta o array restante.

Para otimizar a remoção e evitar reescrita completa do conjunto a cada chamada, utiliza-se um mecanismo de marcação. Um vetor auxiliar rastreia quais coeficientes angulares já foram alvo de remoção massiva anteriormente. Se uma operação de remoção tentar eliimnar um k que já foi marcado como removido e nenhum outro b daquele k existir, a operação pode ser abortada precocemente. Caso contrário, realiza-se a filtragem manual reatribuindo o índice de topo.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

// Mapa para contar frequências de k e b
unordered_map<ll, int> freqK, freqB;
vector<pair<ll, ll>> linhasVivas;
vector<bool> kRemovido;
const int OFFSET = 100005; 

inline void lerInteiro(ll &x) {
    char c = getchar();
    while(c != '-' && !isdigit(c)) c = getchar();
    int sinal = 1;
    if (c == '-') sinal = -1;
    x = 0;
    while (isdigit(c)) {
        x = x * 10 + c - 48;
        c = getchar();
    }
    x *= sinal;
}

int main() {
    ios_base::sync_with_stdio(0);
    
    ll nOp;
    cin >> nOp;

    for(int i = 0; i < nOp; ++i) {
        int op;
        cin >> op;
        ll k, b;
        cin >> k >> b;
        k += OFFSET; // Offset para evitar índices negativos
        
        if(op == 1) {
            // Adicionar nova linha
            linhasVivas.emplace_back(k - OFFSET, b);
            freqK[k]++;
            freqB[b]++;
            kRemovido[k] = false;
        } 
        else if(op == 2) {
            // Consultar retas não paralelas
            ll totais = linhasVivas.size();
            ll paralelas = freqK[k];
            cout << (totais - paralelas) << "\n";
        } 
        else if(op == 3) {
            // Remover linha específica
            // Verifica se o k já foi totalmente limpo anteriormente sem necessidade
            if(kRemovido[k] && freqB[b] == 0) continue; 
            
            vector<pair<ll, ll>> proximoSet;
            bool mudouAlguma = false;

            for(auto &p : linhasVivas) {
                if(p.first == k - OFFSET && p.second == b) {
                    mudaAlguma = true;
                } else {
                    proximoSet.push_back(p);
                }
            }
            
            if(!mudouAlguma) {
                 // Não tinha nada pra remover
                 continue;
            }

            // Limpa mapas e reconstrói
            freqK.clear();
            freqB.clear();
            
            swap(linhasVivas, proximoSet);
            
            for(auto &p : linhasVivas) {
                freqK[p.first + OFFSET]++;
                freqB[p.second]++;
            }
            
            kRemovido[k] = true;
        }
    }
    return 0;
}

Problema 4: Correspondência de Sequências com Buffer Cíclico

O quarto problema visa encontrar a subsequência comum mais longa entre um alvo T e múltiplas cópias de uma fonte S. Existem duas partes principais na resolução.

No cenário inicial, percorreríamos o texto T simulando o ciclo infinito de S. Uma otimização simples seria rastrear a posição do último caractere utilizado dentro de S e apenas avançar quando necessário. Contudo, isso pode levar a Timeout se houver muitos saltos repetitivos.

Para atingir a pontuação máxima, pré-processamos as posições de ocorrência de cada número distinto presente em S usando vetores ordenados. Quando buscamos o próximo valor desejado em T, realizamos uma busca binária nos índices armazenados para encontrar o primeiro local maior que a posição corrente. Isso permite calcular quantos ciclos adicionais são necessários em O(log n) por elemento.

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

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    long long custo1, custo2;
    cin >> n >> m >> custo1 >> custo2;

    vector<int> padrao(n);
    // Mapeia valores para suas posições no padrão S
    map<int, vector<int>> posicoes;
    for(int i = 0; i < n; ++i) {
        cin >> padrao[i];
        posicoes[padrao[i]].push_back(i);
    }

    vector<int> alvo(m);
    for(int i = 0; i < m; ++i) cin >> alvo[i];

    int inicioAtual = 0; // Posição atual dentro do ciclo de S
    long long ciclos = 1;

    for(int i = 0; i < m; ++i) {
        if(posicoes.find(alvo[i]) == posicoes.end()) {
            cout << 0 << " " << 0 << endl;
            return 0;
        }

        auto &indices = posicoes[alvo[i]];

        // Binário: procura primeiro index > inicioAtual
        auto it = upper_bound(indices.begin(), indices.end(), inicioAtual);

        if(it != indices.end()) {
            inicioAtual = *it;
        } else {
            // Se não encontrou maior, precisa dar a volta
            inicioAtual = indices[0];
            ciclos++;
        }
    }

    if(alvos == 0 || inicioAtual == 0) ciclos = 0; // Correção lógica de caso especial
    
    // Se a busca falhou inicialmente ou algo similar
    if (m == 0) {
         cout << 0 << " " << 0 << endl;
    } else {
         cout << (long long)m * custo1 << " " << ciclos * custo2 << endl;
    }

    return 0;
}