Problema D - Sky Reflector

Neste problema, trabalhamos com uma matriz de dimensões $n \times m$ onde cada célula contém um valor inteiro entre $1$ e $k$. Definimos $A_i$ como o valor mínimo da linha $i$ e $B_j$ como o valor máximo da coluna $j$. O objetivo é calcular o número de pares distintos de sequências $(A, B)$ que podem ser formados, aplicando o módulo $998244353$.

Para casos degenerados onde uma das dimensões é igual a 1:

• Se $n=1$, qualquer sequência $B$ de comprimento $m$ é válida, resultando em $k^m$ possibilidades.
• Se $m=1$, qualquer sequência $A$ de comprimanto $n$ é válida, resultando em $k^n$ possibilidades.

Para $n, m > 1$, a condição fundamental para a existência da matriz é que o valor máximo da sequência $A$ seja menor ou igual ao valor mínimo da sequência $B$. Ou seja, $\max(A_i) \leq \min(B_j)$. Se essa condição for respeitada, é sempre possível construir uma matriz válida.

Podemos iterar sobre o valor de $X = \max(A_i)$. Para um $X$ fixo:

1. O número de sequências $A$ onde o valor máximo é exatamente $X$ é dado por $X^n - (X-1)^n$.
2. O número de sequências $B$ onde todos os elementos são pelo menos $X$ (garantindo $\min(B_j) \geq X$) é $(k - X + 1)^m$.

O reslutado final é a soma desses produtos para todos os $X$ de $1$ até $k$.

#include <iostream>

using namespace std;

long long modular_pow(long long base, long long exp) {
    long long res = 1;
    base %= 998244353;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % 998244353;
        base = (base * base) % 998244353;
        exp /= 2;
    }
    return res;
}

int main() {
    long long n, m, k;
    if (!(cin >> n >> m >> k)) return 0;

    const int MOD = 998244353;

    if (n == 1) {
        cout << modular_pow(k, m) << endl;
        return 0;
    }
    if (m == 1) {
        cout << modular_pow(k, n) << endl;
        return 0;
    }

    long long total_combinations = 0;
    for (int x = 1; x <= k; ++x) {
        long long count_A = (modular_pow(x, n) - modular_pow(x - 1, n) + MOD) % MOD;
        long long count_B = modular_pow(k - x + 1, m);
        total_combinations = (total_combinations + (count_A * count_B) % MOD) % MOD;
    }

    cout << total_combinations << endl;
    return 0;
}

Problema E - Rvom and Rsrev

Dado uma string $S$ composta por 'a' e 'b', a operação permitida consiste em escolher dois caracteres idênticos, inverter a subsequência entre eles e remover os dois caracteres escolhidos. O objetiov é obter a string lexicograficamente máxima.

A estratégia varia dependendo do final da string original e da contagem de caracteres:

Caso 1: String termina em 'a'

O foco é mover o maior número possível de 'b's para o início. Definimos um sistema de potencial para minimizar as remoções de 'a' e maximizar a sequência final de 'a's após todos os 'b's possíveis terem sido agrupados no prefixo.

Caso 2: String termina em 'b'

• Quantidade par de 'a': É possível remover todos os 'a's, restando apenas os 'b's originais.
• Quantidade ímpar de 'a':
  • Se terminar em "...ab" ou "...abb", a melhor forma é manter um 'a' próximo ao final, resultando em algo como "bbb...bab" ou "bbb...babb".
  • Se terminar em "bbb", tentamos trazer um 'a' para o final da string ou reduzir a string para "abb...b" se ela for majoritariamente composta por 'a's no início.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void solve_suffix_a(int ca, int cb, const string& s) {
    int blocks_aa = 0, blocks_single_a = 0, current_a = 0;
    for (char c : s) {
        if (c == 'a') current_a++;
        else {
            if (current_a == 1) blocks_single_a++;
            else if (current_a > 1) blocks_aa++;
            current_a = 0;
        }
    }
    int reduction = blocks_aa + (blocks_single_a + 1) / 2;
    cout << string(cb, 'b') + string(max(0, ca - 2 * reduction), 'a') << endl;
}

void process() {
    string s;
    cin >> s;
    int n = s.length();
    int ca = 0, cb = 0;
    for (char c : s) (c == 'a' ? ca++ : cb++);

    if (s.back() == 'a') {
        solve_suffix_a(ca, cb, s);
    } else {
        if (ca % 2 == 0) {
            cout << string(cb, 'b') << endl;
        } else {
            if (n >= 2 && s[n - 2] == 'a') {
                cout << string(cb - 1, 'b') + "ab" << endl;
            } else if (n >= 3 && s[n - 3] == 'a') {
                cout << string(cb - 2, 'b') + "ab" + "b" << endl;
            } else {
                // Caso complexo bbb
                int target = -1;
                for (int i = 0; i < n - 3; i++) {
                    if (s[i] == 'b' && s[i + 1] == 'a' && s[i + 2] == 'a') target = i;
                }
                if (target == -1) {
                    for (int i = 0; i < n - 3; i++) {
                        if (s[i] == 'b' && s[i + 1] == 'a' && s[i + 2] == 'b') { target = i; break; }
                    }
                }
                
                if (target == -1) cout << "a" + string(cb, 'b') << endl;
                else {
                    string next_s = s.substr(0, target) + s.substr(target + 1, n - target - 3);
                    // Lógica simplificada de recursão para o caso transformado
                    int nca = 0, ncb = 0;
                    for(char c : next_s) (c == 'a' ? nca++ : ncb++);
                    solve_suffix_a(nca, ncb, next_s);
                }
            }
        }
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) process();
    return 0;
}

Problema F - Social Distance

Este problema envolve geometria estocástica. Temos $n$ indivíduos em um eixo real, onde a posição de cada um é uma variável aleatória uniforme dentro de um intervalo $[X_{i-1}, X_i]$. O desafio é encontrar o valor esperado da menor distância entre quaisquer dois indivíduos.

A solução envolve a integração da função de sobrevivência da distribuição da distância mínima. Para $n$ pontos, a complexidade reside no cálculo da probabilidade de que todas as distâncias sejam simultaneamente maiores que um valor $d$. Esse problema pode ser modelado através de programação dinâmica ou processamento de funções polinomiais por partes ao longo dos intervalos definidos.