Friki Work

Este análisis detalla las soluciones y estrategias para los problemas A-F de la competición Codeforces Round 699. Los problemas iniciales presentaron un buen contexto, mientras que los posteriores exploraron conceptos más avanzados. A. Navegación Espacial Este problema fue sorprendentemente menos popular de lo esperado al momento de su resoluci ...

Consideremos un árbol enraizado con raíz en el vértice 1, donde un árbol es un grafo conectado sin ciclos ni múltiples aristas. El árbol está orientado con la raíz hacia arriba, lo cual es común en estructuras de datos para programadores. En este árbol, dos manzanas crecerán en vértices específicos (pueden ser el mismo vértice). Después, se sac ...

Arreglos unidimensionales Supongamos que necesitamos almacenar la temperatura promedio de cada mes del año. En lugar de crear doce variables independientes, podemos declarar un arreglo de tipo int que contenga todos los valores: // Almacenando temperaturas promedio mensuales int temperaturas[12] = {12, 14, 18, 22, 27, 32, 35, 34, 29, 23, 17, 13 ...

Probelma A: Conexión de nodos con aristas de peso variable. La solución óptima utiliza el algoritmo de Kruskal para el árbol de expansión mínima. El objetivo es conectar todos los nodos con un costo mínimo, considerando aristas con pesos dados y un costo adicional por arista que conecta componentes desconectados. #include <iostream> #incl ...

—¿Por qué empecé con esto antes de terminar la programación de intervalos... P2664 Juego en Árboles El problema plantea: tenemos un árbol con n nodos, donde cada nodo tiene un color (c_i). Definimos (s(i,j)) como la cantidad de colores distintos en el camino desde el nodo (i) hasta el nodo (j). Además, $$sum_i=\sum_{j=1}^n s(i, j)$$ Necesitamos ...

Problema A: Conteo de números sin una secuencia específica Se requiere determinar cuántos números en el rango de 12345678 a 98765432 no contienen la subsecuencia "2023". "No contener" significa que incluso eliminando dígitos del número, no se puede formar "2023". Por ejemplo, 20322175 y 33220022 no contienen " ...

Problema A: Cammbiar el último carácter Modificar el último carácter de una cadena de entrada a '4'. #include <bits/stdc++.h> using namespace std; void resolver() { string entrada; cin >> entrada; entrada.back() = '4'; cout << entrada << endl; } int main() { ios::sync_with_stdio(false); cin.tie( ...

Este artículo detalla una solución eficinete mediante programación dinámica para el problema de control de ira en un aula, referenciado como P14169 en Luogu. El enfoque inicial implica definir un estado tridimensional para capturar la ira acumulada según el minuto, posición del profesor y energía consumida. Definimos \( dp_{i,j,k} \) como el va ...

Modelamos cada arma como una arista que conecta dos nodos (atributos). Así, el problema se reduce a analizar componentes conexas en un grafo. Si la componente conexa forma un árbol (es decir, teine exactamente n-1 aristas para n nodos), no es posible seleccionar todos los nodos. En este caso, basta con no elegir el nodo de mayor valor. Si la co ...

El diámetro de un árbol es la lnogitud del camino más largo entre dos nodos. Existen enfoques eficientes para calcularlo, como la programación dinámica en árboles y el algoritmo de doble búsqueda en amplitud (BFS). Programación Dinámica en Árboles Puede manejar aristas con pesos negativos. Complejidad temporal: O(n). Sea distancia[x] la máxima ...