C. Factoriales y Potencias de Dos

Problema: Dado un entero n (n ≤ 1012), se define una colección "buena" como un conjunto de números donde cada número es un factorial o una potencia de 2. Se busca el menor tamaño k de un subconjunto de esta colección cuya suma sea exactamente n.

Solución: Los factoriales menores o iguales a n son muy pocos (menos de 20). Por lo tanto, es factibel enumerar todas las posibles sumas de factoriales que no excedan n. Para cada suma parcial m obtenida de factoriales, la cantidad mínima de potencias de 2 necesarias para alcanzar n es igual al número de bits en la representación binaria de (n - m), es decir, popcount(n - m). Basta con explorar recursivamente todas las combinaciones de factoriales y tomar el mínimo de (cantidad de factoriales + popcount del remanente).

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll objetivo, respuesta = LLONG_MAX;
vector<ll> factoriales;

void explorar(int idx, ll suma, int cnt) {
    respuesta = min(respuesta, cnt + __builtin_popcountll(objetivo - suma));
    for (int i = idx; i >= 0; --i) {
        if (suma + factoriales[i] <= objetivo)
            explorar(i - 1, suma + factoriales[i], cnt + 1);
    }
}

int main() {
    cin >> objetivo;
    ll f = 1;
    for (int i = 1; f <= objetivo; ++i) {
        factoriales.push_back(f);
        f *= i;
    }
    explorar(factoriales.size() - 1, 0, 0);
    cout << respuesta << endl;
    return 0;
}

D. Asignación de Pesos en un Árbol

Problema: Dado un árbol con n vértices (n ≤ 2·105), un vértice se considera "bueno" si su peso es igual a la suma de los pesos de todos sus vecinos. Se deben asignar pesos enteros positivos a cada vértice para maximizar la cantidad de vértices buenos, y entre todas las asignaciones que logran ese máximo, minimizar la suma total de pesos.

Solución: Observar que en un árbol con al menos dos vértices, dos vértices adyacentes no pueden ser ambos buenos simultáneamente. Por lo tanto, el problema se reduce a encontrar un conjunto independiente máximo con ciertas condiciones aidcionales. Se puede resolver con programación dinámica en árboles. Definamos dos estados para cada vértice u: el estado cuando u no es bueno (f0[u]) y cuando u es bueno (f1[u]). Cada estado almacena el número máximo de vértices buenos en el subárbol y la suma mínima de pesos correspondiente. La transición combina los estados de los hijos y se elige la opción óptima. La reconstrucción de los pesos asignados se realiza posteriormente.

vector<vector<int>> grafo;
vector<pair<int, ll>> estado[2]; // estado[0] para no bueno, estado[1] para bueno

void dfs(int u, int padre) {
    estado[0][u] = {0, 1};
    estado[1][u] = {1, (int)grafo[u].size()};
    for (int v : grafo[u]) {
        if (v == padre) continue;
        dfs(v, u);
        estado[1][u].first += estado[0][v].first;
        estado[1][u].second += estado[0][v].second;
        if (estado[0][v].first > estado[1][v].first || 
            (estado[0][v].first == estado[1][v].first && estado[0][v].second < estado[1][v].second)) {
            estado[0][u].first += estado[0][v].first;
            estado[0][u].second += estado[0][v].second;
        } else {
            estado[0][u].first += estado[1][v].first;
            estado[0][u].second += estado[1][v].second;
        }
    }
}

E. Tabla de Potencias

Problema: Dada una tabla de n filas y m columnas (n, m ≤ 106), donde el elemento en la fila i y columna j es ij, determinar cuántos números distintos aparecen en la tabla.

Solución: Los números repetidos ocurren cuando diferentes pares (i, j) producen el mismo valor. Esto sucede cuando i y j son potencias de un mismo número base. Agrupemos las filas por su "raíz" más pequeña. Para cada grupo de filas que son potencias de un mismo base, contamos la cantidad de exponentes distintos que aparecen en la tabla. La suma de estos conteos para todos los grupos da el total de números distintos. Es necesario precomputar, para cada longitud de grupo (cantidad de filas que son potencias de un mismo base), cuántos exponentes distintos hay en la tabla de potencias correspondiente.

const int MAX = 1e6 + 5;
vector<int> cnt_por_longitud(21, 0);

void precomputar(int m) {
    vector<bool> visto(m * 20 + 1, false);
    for (int base = 1; base <= 20; ++base) {
        cnt_por_longitud[base] = cnt_por_longitud[base - 1];
        for (int exp = 1; exp <= m; ++exp) {
            int val = base * exp;
            if (!visto[val]) {
                visto[val] = true;
                cnt_por_longitud[base]++;
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    precomputar(m);
    vector<bool> es_potencia(MAX, false);
    ll distintos = 1; // 1^j = 1
    for (int i = 2; i <= n; ++i) {
        if (!es_potencia[i]) {
            int longitud = 0;
            for (ll j = i; j <= n; j *= i) {
                es_potencia[j] = true;
                longitud++;
            }
            distintos += cnt_por_longitud[longitud];
        }
    }
    cout << distintos << endl;
    return 0;
}

F. Juego de Cartas en Mesa Circular

Problema: Hay n jugadores sentados en una mesa circular (numerados de 1 a n, con el jugador n a la derecha del 1). Inicialmente hay n2 cartas: para cada i, hay n cartas con el número i. En cada operación, cada jugador elige una carta de su mano y la pasa al jugador de su derecha. El objetivo es que al final el jugador i tenga exactamente n cartas con el número i. Se debe construir una secuencia de operaciones que logre esto en a lo sumo (n2 - n) pasos (2 ≤ n ≤ 100).

Solución: Un enfoque constructivo es transformar la configuración inicial en dos etapas. Primero, transofrmamos la mano de cada jugador en una permutación de [1, 2, ..., n] (es decir, cada jugador tiene exactamente una carta de cada número). Para lograrlo, cada jugador pasa todas las cartas que le sobran (las que no corresponden a su posición en la permutación) a su derecha. Luego, transformamos esta configuración en la deseada: cada jugador pasa todas las cartas que no son de su propio número a su derecha. Se puede demostrar que el número total de operaciones en este proceso es exactamente n2 - n, lo que cumple con el límite requerido.