Problema 1: Evaluación de Coprimidad en Conjuntos de Enteros

Planteamiento y Estrategia

Para determinar si un conjunto de números enteros es coprimo dos a dos (pairwise coprime), coprimo en conjunto (setwise coprime) o no coprimo, podemos utilizar un enfoque basado en la frecuencia de los dviisores. Dos números son coprimos si su único divisor común es 1. Al extender esto a múltiples números, podemos iterar a través de todos los posibles divisores y contar cuántos números en el conjunto son múltiplos de cada divisor. Si algún divisor mayor que 1 divide a más de un número, el conjunto no es coprimo dos a dos. Si el divisor divide a todos los números, no es coprimo en conjunto.

Implementación en C++

#include <iostream>
#include <vector>

using namespace std;

const int MAX_VAL = 1000005;
int frequency[MAX_VAL];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int total_numbers;
    if (!(cin >> total_numbers)) return 0;

    vector<int> numbers(total_numbers);
    for (int i = 0; i < total_numbers; ++i) {
        cin >> numbers[i];
        frequency[numbers[i]]++;
    }

    bool is_pairwise_coprime = true;
    bool is_setwise_coprime = true;

    for (int divisor = 2; divisor < MAX_VAL; ++divisor) {
        int multiples_count = 0;
        for (int multiple = divisor; multiple < MAX_VAL; multiple += divisor) {
            multiples_count += frequency[multiple];
        }
        
        if (multiples_count > 1) {
            is_pairwise_coprime = false;
        }
        if (multiples_count == total_numbers) {
            is_setwise_coprime = false;
        }
    }

    if (is_pairwise_coprime) {
        cout << "pairwise coprime\n";
    } else if (is_setwise_coprime) {
        cout << "setwise coprime\n";
    } else {
        cout << "not coprime\n";
    }

    return 0;
}

Problema 2: Cálculo de Rutas Mínimas en Árboles con Portales

Planteamiento y Estrategia

En un grafo en forma de árbol con $N-1$ aristas, la ruta entre dos nodos $s$ y $t$ es única. Sin embargo, al introducir $K$ portales de teletransportación, la distancia mínima puede reducirse. La solución óptima implica comparar la distancia directa en el árbol con la suma de las distancias desde $s$ y $t$ hacia sus respectivos portales más cercanos. Para calcular la distancia en el árbol, utilizamos el algoritmo de Mínimo Común Ancestro (LCA) con elevación binaria. Para las distancias a los portales, aplicamos una Búsqueda en Anchura (BFS) multiorigen.

Implementación en C++

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

const int MAX_NODES = 2000005;
const int LOG = 22;

vector<int> adj[MAX_NODES];
int depth[MAX_NODES];
int up[MAX_NODES][LOG];
int dist_to_portal[MAX_NODES];

void build_lca(int node, int parent, int current_depth) {
    up[node][0] = parent;
    depth[node] = current_depth;
    for (int i = 1; i < LOG; ++i) {
        up[node][i] = up[up[node][i - 1]][i - 1];
    }
    for (int neighbor : adj[node]) {
        if (neighbor != parent) {
            build_lca(neighbor, node, current_depth + 1);
        }
    }
}

int get_lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    int diff = depth[u] - depth[v];
    for (int i = 0; i < LOG; ++i) {
        if ((diff >> i) & 1) {
            u = up[u][i];
        }
    }
    if (u == v) return u;
    for (int i = LOG - 1; i >= 0; --i) {
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}

long long get_tree_dist(int u, int v) {
    int lca_node = get_lca(u, v);
    return (long long)depth[u] + depth[v] - 2LL * depth[lca_node];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, q;
    if (!(cin >> n >> m >> q)) return 0;

    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    build_lca(1, 0, 0);

    queue<int> bfs_q;
    for (int i = 1; i <= n; ++i) dist_to_portal[i] = -1;
    
    for (int i = 0; i < m; ++i) {
        int portal_node;
        cin >> portal_node;
        dist_to_portal[portal_node] = 0;
        bfs_q.push(portal_node);
    }

    while (!bfs_q.empty()) {
        int curr = bfs_q.front();
        bfs_q.pop();
        for (int nxt : adj[curr]) {
            if (dist_to_portal[nxt] == -1) {
                dist_to_portal[nxt] = dist_to_portal[curr] + 1;
                bfs_q.push(nxt);
            }
        }
    }

    while (q--) {
        int s, t;
        cin >> s >> t;
        
        long long tree_path = get_tree_dist(s, t);
        long long portal_path = LLONG_MAX;
        
        if (dist_to_portal[s] != -1 && dist_to_portal[t] != -1) {
            portal_path = (long long)dist_to_portal[s] + dist_to_portal[t];
        }
        
        cout << min(tree_path, portal_path) << "\n";
    }

    return 0;
}

Problema 3: Minimización de Costos en Asignación de Días de Estudio

Planteamiento y Estrategia

Este problema requiere minimizar una función de penalización basada en la diferencia entre los días reales de estudio y un número objetvio de días. Dado que aplicar un costo menor es siempre preferible cuendo la diferencia es positiva, podemos iterar sobre todos los posibles valores de días objetivo. Para cada valor, calculamos el costo acumulado utilizando sumas prefijas y sufijas, lo que nos permite evaluar todas las configuraciones en tiempo lineal respecto al rango de días.

Implementación en C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    unsigned long long cost_A, cost_B, cost_C;
    if (!(cin >> cost_A >> cost_B >> cost_C)) return 0;

    int n, m;
    cin >> n >> m;

    const int MAX_DAYS = 100005;
    vector<unsigned long long> count_a(MAX_DAYS, 0), count_b(MAX_DAYS, 0);
    unsigned long long sum_a = 0, sum_b = 0;

    for (int i = 0; i < n; ++i) {
        unsigned long long days;
        cin >> days;
        count_a[days]++;
        sum_a += days;
    }

    for (int i = 0; i < m; ++i) {
        unsigned long long days;
        cin >> days;
        count_b[days]++;
        sum_b += days;
    }

    unsigned long long min_penalty = ULLONG_MAX;
    
    unsigned long long prefix_count_b = 0, prefix_sum_b = 0;
    unsigned long long suffix_count_a = n, suffix_sum_a = sum_a;

    for (int target = MAX_DAYS - 1; target >= 1; --target) {
        prefix_count_b += count_b[target];
        prefix_sum_b += (unsigned long long)target * count_b[target];
        
        suffix_count_a -= count_a[target];
        suffix_sum_a -= (unsigned long long)target * count_a[target];

        if (prefix_count_b == 0) continue;

        unsigned long long current_penalty = 0;
        
        unsigned long long diff_b = prefix_sum_b - prefix_count_b * target;
        if (cost_A < cost_B) {
            unsigned long long use_A = min(diff_b, suffix_count_a * target - suffix_sum_a);
            current_penalty += use_A * cost_A;
            current_penalty += (diff_b - use_A) * cost_B;
        } else {
            current_penalty += diff_b * cost_B;
        }

        unsigned long long diff_a = suffix_count_a * target - suffix_sum_a;
        current_penalty += diff_a * cost_C;

        min_penalty = min(min_penalty, current_penalty);
    }

    cout << min_penalty << "\n";

    return 0;
}