Problema D: Mediana de Medianas

Para resolver este problema, se aplica búsqueda binaria sobre la posible mediana. Se verifica si el candidato actual es la mediana contando cuántas medianas de subconjuntos son menores. Transformamos cada elemento de la secuencia original en 1 si es mayor que el valor candidato, o -1 en caso contrario. Usamos un Árbol de Fenwick para gestionar sumas de prefijo, acumulando conteos donde las sumas anteriores sean menores o iguales a la suma actual.

bool verificar(int valor, int n, vector<int>& arreglo) {
    vector<int> arbol(2 * n + 2, 0);
    int suma_actual = 0;
    long long total_pares = 1LL * n * (n + 1) / 2;
    long long cuenta_menores = 0;
    for (int i = 0; i < n; i++) {
        actualizar_arbol(arbol, n + suma_actual, 1);
        if (arreglo[i] > valor) {
            suma_actual--;
        } else {
            suma_actual++;
        }
        cuenta_menores += consultar_arbol(arbol, n + suma_actual - 1);
    }
    return cuenta_menores >= total_pares / 2 + 1;
}</int></int>

Problema E: Cintas en Árbol

Este problema requiere cubrir todos los caminos en un árbol mediante emparejamientos. Se modela con programación dinámica en los subárboles. Definimos dp[nodo][i] como el número de formas válidas donde el subárbol del nodo tiene i vértices no emparejados. La transición combina estados de hijos, y se ajusta para evitar emparejamientos propios que no usen el borde hacia el padre. La solución final se obtiene del estado raíz.

void agregar_arista(vector<vector>>& grafo, int u, int v) {
    grafo[u].push_back(v);
    grafo[v].push_back(u);
}

void ajustar_modulo(int &x, int y, int mod) {
    y = (y % mod + mod) % mod;
    x = (x + y) % mod;
}

void dfs(int nodo, int padre, vector<vector>>& grafo, vector<vector>>& dp, vector<int>& tamano, vector<long long="">& auto_emparejamientos, int mod) {
    tamano[nodo] = 1;
    dp[nodo][1] = 1;
    for (int hijo : grafo[nodo]) {
        if (hijo == padre) continue;
        dfs(hijo, nodo, grafo, dp, tamano, auto_emparejamientos, mod);
        vector<int> temp(tamano[nodo] + tamano[hijo] + 1, 0);
        for (int i = 0; i <= tamano[nodo]; i++) {
            for (int j = 0; j <= tamano[hijo]; j++) {
                long long contribucion = 1LL * dp[nodo][i] * dp[hijo][j] % mod;
                ajustar_modulo(temp[i + j], contribucion, mod);
            }
        }
        for (int i = 0; i <= tamano[nodo] + tamano[hijo]; i++) {
            dp[nodo][i] = temp[i];
        }
        tamano[nodo] += tamano[hijo];
    }
    for (int i = 2; i <= tamano[nodo]; i += 2) {
        long long resta = 1LL * dp[nodo][i] * auto_emparejamientos[i] % mod;
        ajustar_modulo(dp[nodo][0], -resta, mod);
    }
}

int main() {
    int n, mod = 1e9 + 7;
    cin >> n;
    vector<vector>> grafo(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        agregar_arista(grafo, u, v);
    }
    vector<vector>> dp(n + 1, vector<int>(n + 1, 0));
    vector<int> tamano(n + 1, 0);
    vector<long long=""> auto_emparejamientos(n + 1, 0);
    auto_emparejamientos[0] = 1;
    for (int i = 2; i <= n; i += 2) {
        auto_emparejamientos[i] = auto_emparejamientos[i - 2] * (i - 1) % mod;
    }
    dfs(1, 0, grafo, dp, tamano, auto_emparejamientos, mod);
    int resultado = (mod - dp[1][0]) % mod;
    cout << resultado << endl;
    return 0;
}</long></int></int></vector></vector></int></long></int></vector></vector></vector>

Problema F: Robots y Salidas

El problema se reduce a contar caminos en una cuadrícula tras una transformación de coordenadas. Cada robot se mapea a un punto (x, y) representando distancias a salidas izquierda y derecha. Movimientos incrementan x o y, y se cuenta el número de formas de trazar una línea divisoria. Se optimiza con un Árbol de Fenwick para calcular sumas acumuladas sobre puntos ordenados.

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> robots(n), salidas(m);
    for (int i = 0; i < n; i++) cin >> robots[i];
    for (int i = 0; i < m; i++) cin >> salidas[i];
    vector<pair int="">> puntos;
    for (int i = 0; i < n; i++) {
        if (robots[i] <= salidas[0] || robots[i] >= salidas[m - 1]) continue;
        auto it = lower_bound(salidas.begin(), salidas.end(), robots[i]);
        if (*it == robots[i]) continue;
        int idx = it - salidas.begin();
        int izquierda = robots[i] - salidas[idx - 1];
        int derecha = salidas[idx] - robots[i];
        puntos.push_back({izquierda, derecha});
    }
    sort(puntos.begin(), puntos.end(), [](auto a, auto b) {
        return a.first < b.first || (a.first == b.first && a.second > b.second);
    });
    vector<int> compresion;
    for (auto& p : puntos) compresion.push_back(p.second);
    sort(compresion.begin(), compresion.end());
    compresion.erase(unique(compresion.begin(), compresion.end()), compresion.end());
    for (auto& p : puntos) {
        p.second = lower_bound(compresion.begin(), compresion.end(), p.second) - compresion.begin() + 1;
    }
    vector<int> dp(puntos.size() + 1, 0);
    vector<int> arbol(compresion.size() + 2, 0);
    dp[0] = 1;
    actualizar_arbol(arbol, 1, dp[0]);
    for (int i = 0; i < puntos.size(); i++) {
        dp[i + 1] = consultar_arbol(arbol, puntos[i].second - 1) + 1;
        dp[i + 1] %= mod;
        actualizar_arbol(arbol, puntos[i].second, dp[i + 1]);
    }
    int total = 0;
    for (int i = 0; i <= puntos.size(); i++) {
        total = (total + dp[i]) % mod;
    }
    cout << total << endl;
    return 0;
}</int></int></int></pair></int>