Problema A: Navegación en Grafos Dirigidos

El desafío consiste en identificar, para cada nodo en un grafo dirigido, el índice del nodo con el mayor valor de "atractivo" que sea alcanzable. Cada nodo posee un valor único.

La estrategia óptima implica invertir el grafo original. Al construir un grafo con aristas en sentido contrario, podemos utilizar un nodo fuente virtual conectado a todos los demás, o simplemente procesar los nodos en orden descendente de sus valores. Al aplicar un algoritmo similar a Dijkstra (o un BFS priorizado), el primer nodo de alto valor que "visite" a un nodo con menor rango determinará el máximo alcanzable para este último.

#include <iostream>
<vector>
<queue>
<map>

using namespace std;

const int MAXN = 1e6 + 10;
long long valores[MAXN];
int resultado_id[MAXN];
bool procesado[MAXN];
vector<pair<int, long long>> adj[MAXN];
map<long long, int> valor_a_indice;

void buscar_maximos(int n) {
    priority_queue<pair<long long, int>> pq;
    // Nodo virtual n+1 conectado a todos
    for(int i = 1; i <= n; ++i) {
        pq.push({valores[i], i});
        resultado_id[i] = i;
    }

    while(!pq.empty()) {
        long long val_actual = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if(procesado[u]) continue;
        procesado[u] = true;

        for(auto& edge : adj[u]) {
            int v = edge.first;
            if(valores[resultado_id[v]] < val_actual) {
                resultado_id[v] = valor_a_indice[val_actual];
                pq.push({val_actual, v});
            }
        }
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%lld", &valores[i]);
        valor_a_indice[valores[i]] = i;
    }
    for(int i = 0; i < m; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        // Construcción del grafo invertido
        adj[v].push_back({u, valores[v]});
    }

    buscar_maximos(n);

    for(int i = 1; i <= n; ++i) {
        printf("%d%c", resultado_id[i], i == n ? '\n' : ' ');
    }
    return 0;
}

Problema B: Concatanación y Aritmética Modular

Se solicita contar cuántas combinaciones de dos números (a_i, a_j) de una secuencia, al ser concaetnados, generan un número que no es diviisble por un entero k. La concatenación de x seguido de y se representa matemáticamente como $x \cdot 10^{\text{longitud}(y)} + y$.

Para resolver esto eficientemente, es mejor calcular el total de combinaciones posibles $n \cdot (n-1)$ y restar aquellas que sí son múltiplos de k. La condición de divisibilidad es: $(x \cdot 10^{\text{len}(y)} + y) \equiv 0 \pmod k$. Esto equivale a: $(x \cdot 10^{\text{len}(y)}) \pmod k \equiv -y \pmod k$.

Preprocesamos los restos de cada número $a_i \cdot 10^L \pmod k$ para todas las longitudes posibles $L \in [1, 10]$ y almacenamos sus frecuencias.

#include <iostream>
<vector>
<map>

using namespace std;

typedef long long ll;
const int MAXN = 1e5 + 7;
ll elementos[MAXN];
int longitudes[MAXN];
ll potencias_diez[12];
map<ll, int> frecuencia_restos[12];

int obtener_longitud(ll n) {
    int len = 0;
    while(n) { n /= 10; len++; }
    return len;
}

int main() {
    int n;
    ll k;
    scanf("%d %lld", &n, &k);

    potencias_diez[0] = 1 % k;
    for(int i = 1; i <= 11; ++i) potencias_diez[i] = (potencias_diez[i-1] * 10) % k;

    for(int i = 1; i <= n; ++i) {
        scanf("%lld", &elementos[i]);
        longitudes[i] = obtener_longitud(elementos[i]);
        for(int j = 1; j <= 10; ++j) {
            ll resto = (elementos[i] * potencias_diez[j]) % k;
            frecuencia_restos[j][resto]++;
        }
    }

    ll validos = 0;
    for(int i = 1; i <= n; ++i) {
        ll target = (k - (elementos[i] % k)) % k;
        if(frecuencia_restos[longitudes[i]].count(target)) {
            validos += frecuencia_restos[longitudes[i]][target];
        }
        // Excluir el caso donde el número se concatena consigo mismo
        if(((elementos[i] % k) * potencias_diez[longitudes[i]] + elementos[i]) % k == 0) {
            validos--;
        }
    }

    printf("%lld\n", (ll)n * (n - 1) - validos);
    return 0;
}

Problema D: Conteo de Prefijos mediante KMP

El objetivo es determinar cuántas cadenas distintas se pueden formar concatenando un prefijo no vacío de una cadena S con un prefijo no vacío de una cadena T.

El total teórico es $|S| \cdot |T|$. Sin embargo, ocurren duplicados cuando existe una coincidencia de bordes. Específicamente, si un prefijo de S termina con un carácter que coincide con el inicio de T, pueden generarse colisiones. El uso del arreglo de fallos (o función $\pi$) del algoritmo KMP permite identificar estas repeticiones estructurales en los prefijos.

#include <iostream>
<cstring>
<vector>

using namespace std;

const int MAXN = 2e5 + 10;
char S[MAXN], T[MAXN];
int pi[MAXN], conteo[MAXN];

int main() {
    scanf("%s %s", S + 1, T + 1);
    int n = strlen(S + 1);
    int m = strlen(T + 1);

    // Construcción de la tabla KMP para la cadena T
    for(int i = 2, j = 0; i <= m; ++i) {
        while(j > 0 && T[j + 1] != T[i]) j = pi[j];
        if(T[j + 1] == T[i]) j++;
        pi[i] = j;
    }

    // Análisis de coincidencias de S con prefijos de T
    for(int i = 1, j = 0; i <= n; ++i) {
        while(j > 0 && T[j + 1] != S[i]) j = pi[j];
        if(T[j + 1] == S[i]) j++;
        
        if(j == i && i > 0) conteo[pi[j]]++;
        else if(j > 0) conteo[j]++;
    }

    for(int i = m; i > 0; --i) {
        if(pi[i] > 0) conteo[pi[i]] += conteo[i];
    }

    long long total_combinaciones = (long long)n * m;
    for(int i = 1; i < m; ++i) {
        if(pi[i + 1] > 0) {
            // Ajuste basado en la periodicidad de los prefijos
            total_combinaciones -= conteo[pi[i + 1]];
        }
    }

    printf("%lld\n", total_combinaciones);
    return 0;
}