Friki Work

En este problema, se consideran n estudiantes en un aula. Cada estudiante (excluyendo al monitor principal, asignado con identificador 0) supervisa a otro estudiante específico. El objetivo es seleccionar el mayor número posible de estudiantes para una tarea, garantizando que para cada estudiante seleccionado, al menos uno de sus supervisores d ...

P8435 【Plantilla】Componentes Biconectos por Nodos #include <iostream> #include <vector> #include <stack> #include <algorithm> using namespace std; const int MAXN = 500005; vector<int> grafo[MAXN]; vector<int> componentes[MAXN]; int orden[MAXN], bajo[MAXN], tiempo; int pila[MAXN], tope, numComponentes; int ...

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

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

Problema 1: Segmentación de Cadenas y Optimización El objetivo de este problema es procesar una cadena binaria y encontrar el valor mínimo entre la mitad del segmento más largo de unos consecutivos y el segundo segmento más largo. La estrategia implica recorrer la cadena para identificar y almacenar las longitudes de todos los bloques contiguos ...

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

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