Problema D

Enunciado: Dada uma sequência de inteiros, é permitido realizar operações ilimitadas em que se decrementa o elemento mais à esquerda em 1 e se incremetna o elemento mais à direita em 1. O objetivo é minimizar a diferença entre o valor máximo e mínimo da sequência após as operações.

Solução: A solução ótima pode ser encontrada de forma direta sem simular o processo de redistribuição. Para determinar o valor mínimo possível, considera-se que o valor no índice i pode ser a média dos primeiros i elementos (se for o ponto mais baixo). O valor mínimo global é o máximo dessas médias calculadas para cada i. Analogamente, para o valor máximo, inverte-se a perspectiva: o valor no índice i pode ser a média dos elementos a partir de i até o final, e o valor máximo global é o mínimo dessas médias. A diferença entre o valor máximo e mínimo obtidos é a resposta.

Implementação em C++:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long resolver(vector<long long>& nums) {
    int tamanho = nums.size();
    vector<long long> soma_acumulada(tamanho + 1, 0);
    for (int i = 1; i <= tamanho; ++i) {
        soma_acumulada[i] = soma_acumulada[i - 1] + nums[i - 1];
    }
    long long valor_minimo = 1e18;
    long long valor_maximo = 0;
    for (int i = 1; i <= tamanho; ++i) {
        long long media_prefixo = soma_acumulada[i] / i;
        long long media_sufixo = (soma_acumulada[tamanho] - soma_acumulada[i - 1] + tamanho - i) / (tamanho - i + 1);
        valor_minimo = min(valor_minimo, media_prefixo);
        valor_maximo = max(valor_maximo, media_sufixo);
    }
    return valor_maximo - valor_minimo;
}

int main() {
    int casos;
    cin >> casos;
    while (casos--) {
        int n;
        cin >> n;
        vector<long long> sequencia(n);
        for (int i = 0; i < n; ++i) {
            cin >> sequencia[i];
        }
        cout << resolver(sequencia) << endl;
    }
    return 0;
}

Problema E

Enunciado: Dado um array de inteiros, é possível reordená-lo livremente. O objetivo é minimizar a soma dos máximos divisores comuns (MDC) dos prefixos, ou seja, \(\sum_{i=1}^{n} \gcd(a_1, a_2, \ldots, a_i)\).

Solução: A estratégia ótima é um algoritmo guloso baseado em uma propriedade do MDC. Inicialmente, coloca-se o menor elemento como primeiro. Em seguida, repetidamente, escolhe-se o próximo elemento que minimiza o MDC acumulado. Quando o MDC atinge seu valor mínimo global, todos os elementos restantes podem ser adicionados sem alterar o MDC. A eficiência é garantida porque o MDC diminui pelo menos pela metade a cada passo significativo, requerendo no máximo \(O(\log n)\) iterações.

Implemantação em C++:

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

long long calcular_minimo_soma(vector<long long>& elementos) {
    sort(elementos.begin(), elementos.end());
    if (elementos.size() == 1) return elementos[0];
    long long mdc_global = elementos[0];
    for (long long num : elementos) {
        mdc_global = gcd(mdc_global, num);
    }
    long long soma_total = mdc_global * elementos.size();
    soma_total += elementos[0] - mdc_global;
    long long mdc_atual = elementos[0];
    while (true) {
        long long proximo_mdc = 1e18;
        for (long long num : elementos) {
            proximo_mdc = min(proximo_mdc, gcd(mdc_atual, num));
        }
        mdc_atual = proximo_mdc;
        soma_total += mdc_atual - mdc_global;
        if (mdc_atual == mdc_global) break;
    }
    return soma_total;
}

int main() {
    int tamanho;
    cin >> tamanho;
    vector<long long> arr(tamanho);
    for (int i = 0; i < tamanho; ++i) {
        cin >> arr[i];
    }
    cout << calcular_minimo_soma(arr) << endl;
    return 0;
}

Problema CF1614D

Enunciado: Semelhante ao Problema E, mas agora o objetivo é maximizar a soma dos MDC dos prefixos. A reordenação livre é permitida.

Solução: Esta variação não pode ser resolvida por guloso. Em vez disso, utiliza-se programação dinâmica com complexidade harmônica. Define-se cnt[i] como o número de elementos que são múltiplos de i, e dp[i] como a soma máxima dos MDC para subsequências com MDC igual a i. A transição é dp[i] = max(dp[j] + (cnt[i] - cnt[j]) * i), para j sendo múltiplos de i. O caso base é dp[i] = cnt[i] * i. A resposta é dp[1].

Implementação em C++ (versão easy):

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long resolver_maximo(vector<int>& dados, int max_valor) {
    vector<int> contagem(max_valor + 1, 0);
    for (int num : dados) contagem[num]++;
    vector<long long> cnt(max_valor + 1, 0);
    vector<long long> dp(max_valor + 1, 0);
    for (int i = max_valor; i >= 1; --i) {
        for (int j = i; j <= max_valor; j += i) {
            cnt[i] += contagem[j];
        }
        dp[i] = static_cast<long long>(cnt[i]) * i;
        for (int j = 2 * i; j <= max_valor; j += i) {
            dp[i] = max(dp[i], dp[j] + (cnt[i] - cnt[j]) * i);
        }
    }
    return dp[1];
}

int main() {
    int n;
    cin >> n;
    vector<int> entrada(n);
    int maximo = 0;
    for (int i = 0; i < n; ++i) {
        cin >> entrada[i];
        maximo = max(maximo, entrada[i]);
    }
    cout << resolver_maximo(entrada, maximo) << endl;
    return 0;
}