Friki Work

Este documento presenta un aálisis y soluciones para los problemas D, E, F, G y H del concurso ABC227. D. Planificación de Proyectos Se nos proporcionan \(N\) números enteros positivos, \(A_i\). En cada operación, seleccionamos \(K\) de estos números y les restamos \(1\). El objetvio es determinar el número máximo de operaciones que se pueden r ...

Problema 1: Probabilidades en Estructuras de Bosques Este problema requiere modelar la probabilidad de que un bosque de $i$ nodos contenga exactamente $j$ nodos en su primera subtree. Definimos prob_bosque[i][j] para representar este estado. La transición considera si el $i$-ésimo nodo se integra en la primera subtree o no. La ecuación de recur ...

En competencias de programación, se presentan problemas que requieren estrategias algorítmicas específicas. A continuación, se describen soluciones para varios problemas comunes. Problema A: Sumas de Dígitos Inversas Este problema se resuelve precalculando el triángulo de Pascal y aplicando búsqueda en profundidad (DFS) para explorar secuencias ...

C. Factoriales y Potencias de Dos Problema: Dado un entero n (n ≤ 1012), se define una colección "buena" como un conjunto de números donde cada número es un factorial o una potencia de 2. Se busca el menor tamaño k de un subconjunto de esta colección cuya suma sea exactamente n. Solución: Los factoriales menores o iguales a n son muy ...

En el concurso CSP-S 2019, se presentaron problemas algorítmicos variados. A continuación, se detallan las soluciones para varios de ellos, con implementaciones en C++ y explicaciones técnicas. Día 1, Problema 1: Código de Gray El código de Gray es una secuencia cíclica de cadenas binarias de n bits donde cada elemento consecutivo difiere en ex ...

La resolución de problemas de conteo es una habilidad fundamental en la programación competitiva, a menudo requiriendo una combinación de técnicas de combinatoria, teoría de números y algoritmos dinámicos. A continuación, se exploran diversas estrategias aplicadas a problemas que involucran conteo y permutaciones, destacando enfoques como la pr ...

El problema de encontrar la subcadena común más larga (Longest Common Substring) consiste en identificar la secuencia de caracteres de mayor longitud que aparece de forma idéntica y continua en dos cadenas de texto dadas. A continuación, se presentan dos anfoques comunes para resolver este problema: Programación Dinámica y Fuerza Bruta. Enfoque ...

Implementaciones en C++ para Codeforces Round 912 (División 2) Este artículo presenta soluciones optimizadas en C++ para los problemas del concurso Codeforces Round 912 (División 2), con enfoque en estructuras de código eficientes y explicaciones técnicas concisas. Problema A: Cajas de Halloumi Se requiere determinar si un arreglo puede ordenar ...

Problema 1: Optimización de Posicionamiento de Postes En este problema, se nos presentan $n$ postes ubicados en una línea numérica en posiciones $p_i$. Cada poste tiene una altura $h_i$. Un poste puede permanecer vertical (ocupando solo el punto $p_i$), caer hacia la izquierda (ocupando el intervalo $[p_i - h_i, p_i]$) o caer hacia la derecha ( ...

Conceptos Básicos de DP en Árboles La programación dinámica (DP) en estructuras de árbol es una herramienta esencial para resolver problemas de optimización. Al trabajar con árboles, su naturaleza recursiva permite descomponer el problema en subproblemas más pequeños, facilitando el uso de memorización para calcular soluciones óptimas de manera ...