Friki Work

Actualizaciones de Intervalos y Arreglos de Diferencias En problemas donde se requiere modificar intervalos de valores y consultar puntos específicos, el uso de arreglos de diferencias es una técnica fundamental. Supongamos un terreno representado por puntos con alturas específicas. La temperatura en cada punto depende de la diferencia de altur ...

Se presentan soluciones para cuatro problemas comunes en competencias de programación, abarcando técnicas como programación dinámica con bitmask, grafos en capas, y estructuras de datos como Mo's algorithm y árboles de Fenwick. Problema A: Cobertura de Petróleo Este problema implica optimizar la colocación de sensores en una cuadrícula para cub ...

Algoritmo de Dijkstra Utilizado para grafos ponderados con pesos positivos sin ciclos. Pasos: Inicializar matriz de adyacencia, arreglo de distancias desde el origen y arreglo de nodos visitados Repetir para todos los nodos: Ancontrar nodo no visitado con mínima distancia Marcar como visitado Actualizar distancias de vecinos no visitados C ...

Introducción En competencias de programación y algorítmica, con frecuencia nos encontramos con problemas que requieren encontrar el camino más corto en grafos. Aunque inicialmente podríamos considerar usar DFS o BFS, estos algoritmos tienen limitaciones significativas: DFS tiene una complejidad temporal demasiado alta para grafos grandes, mient ...

Enfoque basado en Dijkstra: Este método presenta un rendimiento limitado, logrando solo 70 puntos en algunas pruebas, con una complejidad de O(n^3 log m). Es posible optimizarlo a Θ(n^3 log m + n), pero no se detallará aquí. // Versión con Dijkstra #include<stdio.h> #include<queue> #include<vector> #include<cstring> usin ...

Problema A: Navegación en Grafos Dirigidos El desafío consiste en identificar, para cada nodo en un grafo dirigido, el índice del nodo con el mayor valor de "atractivo" que sea alcanzable. Cada nodo posee un valor único. La estrategia óptima implica invertir el grafo original. Al construir un grafo con aristas en sentido contrario, po ...

Camino Más Corto de Fuente Única Algoritmo de Dijkstra (solo para aristas con pesos positivos, fuente única) Su lógica se puede entender como ir al nodo más cercano actualmente alcanzable que aún no hemos determinado si es la ruta más corta, y encotnrar su camino más corto. Leemos todas las aristas y sus pesos, luego inicializamos todas las dis ...