Problema B: Cuadrado Primo

Construir una matriz \(n\times n\) donde la suma de cada fila y columna sea un número primo, y ningún elemento sea primo. Sea \(p\) esta suma, colocar \(p-n+1\) en la diagonal principal y 1 en las demás posiciones. Encontrar el primo más pequeño \(p\) tal que \(p-n+1\) no sea primo.

Problema C: Búsqueda Binaria

Dada una secuencia ordenada donde la búsqueda binaria de \(x\) retorna una posición específica, determinar cuántas permutaciones de \(n\) elementos mantienen esa posición cuando se aplica la búsqueda binaria. Simular el proceso de búsqueda binaria para contar cuántos elementos menores y mayores que \(x\) se encuentran antes de la posición objetivo, luego usar combinatoria para calcualr las disposiciones.

// Solución en C++
const int MODULO = 1e9 + 7;
int tamano, valorBuscado, posicion;

int main() {
    tamano = leer(); valorBuscado = leer(); posicion = leer();
    int izquierda = 0, derecha = tamano, mayores = 0, menores = 0;
    while (izquierda < derecha) {
        int medio = (izquierda + derecha) >> 1;
        if (medio == posicion) izquierda = medio + 1;
        else if (medio > posicion) derecha = medio, mayores++;
        else izquierda = medio + 1, menores++;
    }
    
    int resultado = 1;
    if (menores >= valorBuscado || mayores > tamano - valorBuscado) {
        puts("0"); return 0;
    }
    for (int i = valorBuscado - 1, j = 1; j <= menores; i--, j++) 
        resultado = 1LL * resultado * i % MODULO;
    for (int i = tamano - valorBuscado, j = 1; j <= mayores; i--, j++) 
        resultado = 1LL * resultado * i % MODULO;
    for (int i = 1; i <= tamano - menores - mayores - 1; i++) 
        resultado = 1LL * resultado * i % MODULO;
    printf("%d\n", resultado);
    return 0;
}

Problema D: Bandido en la Ciudad

Dado un árbol con raíz en 1, donde cada nodo tiene \(a_i\) personas, las personas pueden moverse hacia nodos hijos hasta llegar a hojas. Minimizar el número máximo de personas en cualquier hoja. Realizar un DFS para calcular el número de hojas \(cnt\) y la suma total de personas \(sum\) en cada subárbol. La respuesta es el máximo entre todos los \(\left\lceil\dfrac{sum}{cnt}\right\rceil\).

// Solución en C++
void dfs(int nodo) {
    sum[nodo] = a[nodo];
    for (int hijo : grafo[nodo]) {
        dfs(hijo);
        cnt[nodo] += cnt[hijo];
        sum[nodo] += sum[hijo];
    }
    if (grafo[nodo].empty()) cnt[nodo] = 1;
    respuesta = max(respuesta, (sum[nodo] + cnt[nodo] - 1) / cnt[nodo]);
}

Problema E: Computaciones Complicadas

Calcular el MEX de todos los MEX de subsecuencias continuas de una secuencia. Si un valor \(x\) está en el conjunto de MEX, existe una subsecuencia que contiene todos los números de 1 a \(x-1\) pero no \(x\). Dado que el rango de valores es \(10^5\), enumerar respuestas posibles y usar una segment tree para verificar intervalos. Mantener la última posición de aparición de cada número y consultar el mínimo en rangos para determinar si cumple las condiciones.

// Solución en C++
#define HIJO_IZQ (pos << 1)
#define HIJO_DER (pos << 1 | 1)
const int MAX_N = 1e5 + 10, INF = 1e6 + 10;
int ultimaPos[MAX_N], arbol[MAX_N << 2], n, secuencia[MAX_N];
bool visitado[MAX_N];

void actualizar(int pos, int ini, int fin, int idx, int val) {
    if (idx < ini || idx > fin) return;
    if (ini == fin) { arbol[pos] = val; return; }
    int medio = (ini + fin) >> 1;
    actualizar(HIJO_IZQ, ini, medio, idx, val);
    actualizar(HIJO_DER, medio + 1, fin, idx, val);
    arbol[pos] = min(arbol[HIJO_IZQ], arbol[HIJO_DER]);
}

int consultar(int pos, int ini, int fin, int l, int r) {
    if (l > fin || r < ini) return INF;
    if (l <= ini && fin <= r) return arbol[pos];
    int medio = (ini + fin) >> 1;
    int izq = consultar(HIJO_IZQ, ini, medio, l, r);
    int der = consultar(HIJO_DER, medio + 1, fin, l, r);
    return min(izq, der);
}

int main() {
    n = leer();
    for (int i = 1; i <= n; i++) {
        secuencia[i] = leer();
        int minimo = 0;
        if (secuencia[i] > 1) 
            minimo = consultar(1, 1, n, 1, secuencia[i] - 1);
        if (minimo > ultimaPos[secuencia[i]]) visitado[secuencia[i]] = true;
        actualizar(1, 1, n, secuencia[i], i);
        ultimaPos[secuencia[i]] = i;
    }
    for (int i = 2; i <= n + 1; i++) {
        int minimo = consultar(1, 1, n, 1, i - 1);
        if (minimo > ultimaPos[i]) visitado[i] = true;
    }
    for (int i = 1; i <= n; i++) 
        if (secuencia[i] != 1) visitado[1] = true;
    
    int p = 1;
    while (true) {
        if (!visitado[p]) { printf("%d\n", p); return 0; }
        p++;
    }
    return 0;
}

Problema F: Suma Sobre Subconjuntos

Dado un multiconjunto \(S\), encontrar la suma sobre todos los pares de subconjuntos \(A,B\) donde \(B \subseteq A\), \(|B| = |A| - 1\), y \(\gcd(A) = 1\), del valor \(\left(\sum_{x\in A} x\right) \times \left(\sum_{x\in B} x\right)\) módulo 998244353. Usar inversión de Möbius para transformar el problema en términos de divisores. Definir \(g[i]\) como la respuesta para \(\gcd\) múltiplo de \(i\), y luego calcular \(f[1]\) mediante \(\sum g[i] \cdot \mu(i)\). Para cada divisor, acumular contribuciones basadas en conteos y sumas de elementos.

// Solución en C++
int main() {
    n = leer();
    for (int i = 1, val; i <= n; i++) 
        val = leer(), contador[val] = leer();
    
    mu[1] = 1;
    for (int i = 1; i <= MAX_VAL; i++) 
        for (int j = i + i; j <= MAX_VAL; j += i) 
            mu[j] -= mu[i];
    
    long long respuesta = 0, total, suma, sumaCuadrados;
    for (int i = 1; i <= MAX_VAL; i++) {
        total = 0; suma = 0; sumaCuadrados = 0;
        for (int j = i; j <= MAX_VAL; j += i) {
            total += contador[j];
            suma = (suma + contador[j] * j % MOD) % MOD;
            sumaCuadrados = (sumaCuadrados + contador[j] * j % MOD * j % MOD) % MOD;
        }
        if (total < 2) continue;
        long long termino1 = sumaCuadrados * potencia(2, total - 2) % MOD * ((total - 1) % MOD) % MOD;
        long long termino2 = (suma * suma % MOD + MOD - sumaCuadrados) % MOD;
        long long res = potencia(2, total - 2);
        if (total > 2) 
            res = (res + ((total - 2) % MOD) * potencia(2, (total - 3) % (MOD - 1)) % MOD) % MOD;
        res = res * termino2 % MOD;
        res = (res + termino1) % MOD;
        respuesta = (respuesta + res * mu[i] % MOD + MOD) % MOD;
    }
    
    printf("%lld\n", respuesta);
    return 0;
}