Friki Work

Optimización de Distancia en Ascensores Para determinar el piso óptimo donde ubicar un ascensor y minimizar la distancia total de recorrido, se evalúa el costo de establecer el ascensor en cada uno de los pisos disponibles. El costo se calcula sumando las distancias de ida y vuelta para cada persona, considerando su piso de origen, el piso del ...

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 ...

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 ...

T1: Conectividad en Gráficos Dirigidos Análisis del Problema Consideramos un grafo dirigido donde cada nodo tiene exactamente dos aristas entrantes y dos aristas salientes. El objetivo es determinar el número de formas de seleccionar nodos de tal manera que ninguna de las aristas internas de un ciclo se elija consecutivamente. La estructura de ...

El Concurso Internacional de Programación Colegiada (ICPC) 2023 en la sede de Jinan presentó un conjunto de problemas de alta exigencia técnica. A continuación, se detalla el análisis algorítmico y las implementaciones optimizadas para los problemas más destacados de la competencia. Problema D: Búsqueda del Dígito Máximo Este problema actúa com ...

El concurso ICPC 2023 Hangzhou presentó una cantidad generosa de medallas de oro, pero el umbral para obtener una se centró en la resolución de cinco problemas. Más allá de ese punto, todos los problemas restantes fueron considerados de nivel de medalla de oro, con cuatro de ellos (A, B, E, F) siendo accesibles para la mayoría de los competidor ...

Descripción del problema Se nos presenta un problema de cooperación entre dos jugadores en un laberinto representado por una cuadrícula de n×m. Cada casilla puede ser terreno libre (.), trampa (#) o portal de salida (@). Ambos jugadores comienzan en la misma posición y deben moverse simultáneamente en direcciones opuestas. Si uno de ellos alcan ...

El Sr. Kitayuta posee un grafo no dirigido compuesto por n vértices y m bordes. Cada borde, identificado por un índice, tiene un color asignado y enlaza dos vértices específicos. Se requiere responder a una serie de consultas donde, dados dos vértices u y v, se debe determinar la cantidad de colores que permiten conectarlos ya sea directa o ind ...

La búsqueda en amplitud (BFS, por sus siglas en inglés) es un algoritmo fundamental para explorar estructuras de datos como grafos o árboles. Su principio central consiste en visitar todos los vecinos directos de un nodo antes de avanzar al siguiente nivel de profundidad, expandiéndose de manera horizontal como las ondas en el agua. Contextos d ...

Fundamentos del Ordenamienot Topológico El ordenamiento topológico es una secuencia lineal de los vértices de un grafo dirigido acíclico (DAG), tal que para cada arista dirigida u -> v, el vértice u aparece antes que v en la ordenación. Si el grafo contiene ciclos, no es posible obtener un ordenamiento topológico. Implementación Estándar de ...