Este artículo analiza la resolución de dos ejercicios clásicos de programación competitiva. El primero, identificado como Zero Path (Codeforces 1695C), trabaja sobre una rejilla de valores +1 y -1 y plantea si existe un camino monótono de la esquina superior izquierda a la inferior derecha cuya suma sea exactamente cero. La clave reside en la paridad: como el camino tiene longitud n+m-1, la suma solo puede ser nula si esa longitud es par, es decir, si n+m es impar. En ese caso basta calcular mediante programación dinámica el valor mínimo y máximo posibles de cualquier ruta y comprobar que min ≤ 0 ≤ max; un argumento basado en intercambios de pasos adyacentes (R-D por D-R) demuestra que entre el camino de suma mínima y el de suma máxima pueden obtenerse todos los valores intermedios con saltos de 2 en 2, garantizando así la alcanzabilidad del cero. La implementación en C++17 utiliza dos vectores de tamaño m para minimizar memoria y procesa cada celda en O(nm). El segundo problema, llamado Numbers, pide contar cadenas numéricas de longitud 1 a n (sin cero inicial) en las que cada dígito i aparece al menos a[i] veces, módulo 10^9+7. La solución combina técnicas de estrellas y barras con combinatoria de permutaciones con repetición: para cada distribución de conteos c_i que cumpla las restricciones, el número de cadenas válidas se obtiene como permutaciones totales del multiconjunto menos las que comienzan por cero, calculado con factoriales precomputados. La complejidad resultante es tratable para n y a[i] hasta 100. En conjunto, las notas ilustran cómo combinar análisis de paridad, programación dinámica y combinatoria para resolver problemas con restricciones estructurales.
Noticias agregadas con IA