Este artigo apresenta soluções eficientes para dois problemas de algoritmos, abordando técnicas como o tratamento de sequências circulares e a aplicação de algoritmos gulosos para otimização baseada em fatores de potência de dois.

Problema C: Otimizando Caminhos em Semáforos Circulares

O problema consiste em, dada uma sequência de semáforos (representada por uma string s) e um caractere alvo c, determinar o tempo máximo que um veículo leva para encontrar o próximo semáforo verde ('g') após passar por um semáforo do tipo c. A string de semáforos é considerada circular, e o tempo é medido pelo número de posições entre os semáforos.

Abordagem Eficiente (Tempo Linear)

A natureza circular da sequência é o ponto chave aqui. Uma técnica comum e elegante para resolver problemas com sequências circulares é duplicar a string original. Se a string s tem comprimento N, criamos uma nova string s_estendida = s + s. Essa duplicação permite que qualquer caminho circular seja tratado como um caminho linear dentro de s_estendida, eliminando a necessidade de cálculos de módulo ou tratamento especial para "dar a volta" no final da string.

A solução proposta utiliza uma única passagem pela string estendida, iterando de trás para frente para encontrar o semáforo verde mais próximo à direita de qualquer semáforo alvo c:

1. Crie a s_estendida concatenando a string original s com ela mesma (s + s).
2. Inicialize indiceVerdePosterior = -1 (indicando que nenhum 'g' foi encontrado à direita até o momento) e maiorDistancia = 0.
3. Percorra s_estendida de trás para frente, da última posição (2*N - 1) até a primeira (0).
4. Se o caractere atual s_estendida[i] for 'g', atualize indiceVerdePosterior = i.
5. Se s_estendida[i] for o caractere alvo c E indiceVerdePosterior não for -1 (ou seja, um 'g' já foi encontrado à direita ou na própria posição i), calcule a distância como indiceVerdePosterior - i.
6. Atualize maiorDistancia = std::max(maiorDistancia, indiceVerdePosterior - i).

Este método garente uma complexidade de tempo de O(N), pois cada posição é visitada uma única vez.

Implementação em C++ para o Problema C

#include <iostream>
#include <string>
#include <algorithm> // Para std::max
#include <vector>    // Não estritamente necessário para esta solução, mas comum em CP

void resolveProblemaC() {
   int n;
   char caracterAlvo;
   std::string sequenciaSemaforos;
   std::cin >> n >> caracterAlvo >> sequenciaSemaforos;

   std::string sequenciaEstendida = sequenciaSemaforos + sequenciaSemaforos;
   
   int indiceVerdePosterior = -1; // Armazena o índice do 'g' mais à direita encontrado até agora
   int maiorDistancia = 0;

   // Itera de trás para frente na sequência estendida para encontrar o 'g' mais próximo à direita
   for (int i = 2 * n - 1; i >= 0; --i) {
       if (sequenciaEstendida[i] == 'g') {
           indiceVerdePosterior = i; // Atualiza a posição do 'g' mais recente
       } else if (sequenciaEstendida[i] == caracterAlvo && indiceVerdePosterior != -1) {
           // Se encontrou o caracter alvo 'c' e já há um 'g' à direita
           maiorDistancia = std::max(maiorDistancia, indiceVerdePosterior - i);
       }
   }
   std::cout << maiorDistancia << std::endl;
}

int main() {
   // Otimização para entrada/saída em C++ (comum em competitive programming)
   std::ios_base::sync_with_stdio(false);
   std::cin.tie(NULL);

   int numTestes;
   std::cin >> numTestes; // Lê o número de casos de teste
   while (numTestes--) {
       resolveProblemaC(); // Resolve cada caso de teste
   }
   return 0;
}

Problema D: Minimizando Operações para Fatores de Potência de Dois

O problema consiste em, dado um array a de N inteiros, realizar o número mínimo de operações para que o produto de todos os seus elementos seja divisível por 2^N. Uma operação permite escolher um índice i (1-indexado) e substituir a_i por a_i \cdot i.

Estratégia Gulosa (Greedy)

A condição de divisibilidade por 2^N implica que a soma total dos expoentes de 2 (fatores de 2) na fatoração prima de todos os elementos do array deve ser, no mínimo, N. Cada operação, a_i \leftarrow a_i \cdot i, nos fornece contar_fatores_dois(i) novos fatores de 2, onde contar_fatores_dois(k) é o maior inteiro p tal que 2^p divide k.

Para minimiazr o número de operações, devemos escolher os índices i que fornecem o maior número de fatores de 2 primeiro. Esta é a essência da estratégia gulosa:

1. Pré-cálculo de Fatores de 2 por Índice: É eficiente pré-calcular contar_fatores_dois(k) para cada k de 1 até o valor máximo de N. Isso é feito uma única vez antes de todos os casos de teste.
2. Soma Inicial de Fatores de 2: Some os fatores de 2 de todos os elementos originais a_j do array. Armazene esta soma em somaTotalPotenciasDeDois.
3. Verificação Inicial: Se somaTotalPotenciasDeDois já for maior ou igual a N, a resposta é 0 operações.
4. Coleta e Frequência dos Fatores de 2 Ganhos: Se mais fatores forem necessários, crie um array de frequência (ex: frequenciaFatoresIndices) para registrar quantas vezes cada valer de contar_fatores_dois(i) (para i de 1 a N) aparece. Por exemplo, frequenciaFatoresIndices[3] conteria o número de índices i que, ao serem usados em uma operação, adicionariam exatamente 3 fatores de 2. O valor máximo de fatores de 2 para N até 2e5 é aproximadamente 17-18, então um array de tamanho 20 é suficiente.
5. Aplicação Gulosa:
   • Calcule fatoresNecessarios = N - somaTotalPotenciasDeDois.
   • Inicialize operacoes = 0.
   • Itere powerVal do maior valor de fatores de 2 possível (ex: 19) para 1.
   • Enquanto fatoresNecessarios > 0 e houverem índices disponíveis que fornecem powerVal fatores de 2 (verificado por frequenciaFatoresIndices[powerVal] > 0):
     • Subtraia powerVal de fatoresNecessarios.
     • Decrementa a contagem em frequenciaFatoresIndices[powerVal].
     • Incrementa operacoes.
6. Resultado Final: Se, após a aplicação gulosa, fatoresNecessarios <= 0, então operacoes é a resposta. Caso contrário, é impossível atingir a meta, e a resposta é -1.

Implementação em C++ para o Problema D

#include <iostream>
#include <vector>
#include <numeric> // Para std::accumulate (não usado diretamente no exemplo, mas útil)
#include <algorithm> // Para std::max

// Define um limite superior para N, usado para pré-cálculos.
// 2e5 + 5 é um valor de segurança comum.
const int MAX_VAL_N_PROBLEM_D = 200005; 

// Armazena o número de fatores de 2 para cada número 'k' (de 1 a MAX_VAL_N_PROBLEM_D-1)
std::vector<int> potencias_de_dois_por_indice(MAX_VAL_N_PROBLEM_D);

// Função auxiliar para contar o número de fatores de 2 em um inteiro
int contar_fatores_dois(int num) {
   if (num == 0) return 0; // Trata o caso de 0, embora geralmente problemas de CP evitem isso
   int count = 0;
   while (num > 0 && num % 2 == 0) {
       count++;
       num /= 2;
   }
   return count;
}

// Pré-calcula os fatores de 2 para todos os possíveis índices 'i' ou valores
void precalcular_potencias_de_dois_globais() {
   for (int i = 1; i < MAX_VAL_N_PROBLEM_D; ++i) {
       potencias_de_dois_por_indice[i] = contar_fatores_dois(i);
   }
}

void resolveProblemaD() {
   int n;
   std::cin >> n;

   long long somaTotalPotenciasDeDois = 0;
   for (int i = 0; i < n; ++i) {
       int elemento;
       std::cin >> elemento;
       somaTotalPotenciasDeDois += contar_fatores_dois(elemento);
   }

   if (somaTotalPotenciasDeDois >= n) {
       std::cout << 0 << std::endl;
       return;
   }

   long long fatoresNecessarios = n - somaTotalPotenciasDeDois;
   int operacoes = 0;

   // Frequência de fatores de 2 que podem ser obtidos de índices de 1 a N.
   // O valor máximo de fatores de 2 para um número até 2e5 é 17 (2^17 = 131072).
   // Um array de tamanho 20 é suficiente para cobrir até 19 fatores de 2.
   std::vector<int> frequenciaFatoresIndices(20, 0); 
   for (int i = 1; i <= n; ++i) {
       // Usa o valor pré-calculado para fatores de 2 do índice 'i'
       frequenciaFatoresIndices[potencias_de_dois_por_indice[i]]++;
   }

   // Aplicação da estratégia gulosa: prioriza índices com mais fatores de 2
   for (int powerVal = 19; powerVal >= 1; --powerVal) { // Começa do maior 'powerVal' possível
       while (fatoresNecessarios > 0 && frequenciaFatoresIndices[powerVal] > 0) {
           fatoresNecessarios -= powerVal;
           frequenciaFatoresIndices[powerVal]--;
           operacoes++;
       }
   }

   if (fatoresNecessarios <= 0) {
       std::cout << operacoes << std::endl;
   } else {
       std::cout << -1 << std::endl; // Impossível atingir a meta
   }
}

int main() {
   // Otimização para entrada/saída em C++
   std::ios_base::sync_with_stdio(false);
   std::cin.tie(NULL);

   // Chama o pré-cálculo uma única vez antes de todos os casos de teste
   precalcular_potencias_de_dois_globais(); 

   int numTestes;
   std::cin >> numTestes; // Lê o número de casos de teste
   while (numTestes--) {
       resolveProblemaD(); // Resolve cada caso de teste para o Problema D
   }
   return 0;
}