Posts
Introducción a omegaUp, parte 1
Estamos iniciando una serie de 10 posts para ayudar a nuestros nuevos usuarios a navegar con facilidad entre la gran cantidad de problemas de omegaUp, en forma de mini-tutoriales con los conceptos básicos, temas y fuentes. Esta colección de tutoriales y ligas te ayudarán a resolver muchos de los problemas de omegaUp y aumentar tu nivel de programación.
Posts
Introducción a Omegaup, parte 2 - Problemas básicos
Hola de nuevo. Continuando con la serie Introducción a Omegaup, esta vez vamos a hacer referencia a los problemas más sencillos de la plataforma a la fecha. Aquí se encuentra la parte 1 de esta serie.
Para estos problemas, no se requiere conocer una técnica o un algoritmo en específico: simplemente requieren implementar (o simular) lo que se describe en el problema o hacer una o dos observaciones relativamente sencillas que permiten simplificar la implementación o acortar el número de operaciones que tu programa tendría que hacer y con ello poder resolver el problema dentro de los límites.
Posts
Solución a "Mapas de bits"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 12 Autor: Jorge Alberto González Martínez Fuente: Jorge Alberto González Martínez
En el problema se describen dos formas de representar un mapa de bits.
La forma bidimensional es simplemente utilizar una matriz para representar los bits. La forma por descomposición consiste en agrupar los bits similares y solo escribir el valor de los bits similares. En caso de que no sean similares todos los bits en un mapa de bits dado, se procede a dividir en cuatro secciones, imprimir la letra D y procesar cada uno de los cuartos de la misma manera, tal como se lee en la descripción del problema.
Posts
Solución a "Pista"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 14 Autor: Miguel Covarrubias Fuente: Codeforces
Este problema es una ligera modificación del Let’s Play Osu! que apareció en la ronda 146 en Codeforces. La solución explicada la pueden encontrar en el editorial.
Para $latex N \le 10$ se pueden checar todas las $latex 2^N$ configuraciones de pistas. Para $latex N \le 1000$ funciona una dinámica $latex O(N^2)$, donde los estados son (posición, altura/profundidad que se lleva hasta el momento).
Posts
Solución a "Super Nieves Bros"
**Concurso: **Preselectivo para la IOI 2014, Etapa 1, Problemset 6 Fuente: Topcoder
Este problema es una adaptación del problema ArcadeManao que apareció en el SRM 576 (Abril 2013) de Topcoder. Los detalles de la solución explicada la pueden en el respectivo Match Summary.
La idea general de este problema es muy sencilla: En base a los límites, la primera observación es que el mapa no es muy grande y en el peor caso, la escalera más alta es de tamaño 50.
Posts
Solución de "El Concierto de Dr. Lira"
**Concurso: **Preselectivo para la IOI 2014, Etapa 1, Problemset 13 Fuente: Topcoder
El Concierto de Dr. Lira es una adaptación al problema Changing Sounds que apareció en el SRM 366 (2007, ya llovió) en TopCoder. La solución explicada la pueden encontrar en el Match Summary (necesitan registrarse en omegaUp para verlo).
Les dejo la implementación de spleensarethebest como un muy bien ejemplo de solución a este problema. Cualquier duda, déjenos un comentario.
Posts
Solución a "DP Genérica"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 13 Autor: Freddy Román Cepeda Fuente: Project Euler
Podemos tratar este problema de varias maneras distintas, 3 de las cuales discutiré en esta solución.
Análisis 1 Primero, una idea que hubiera obtenido 50 puntos.
Podemos observar que el problema es equivalente a encontrar de cuántas maneras se le puede asignar un número $latex n_i$ del conjunto $latex \{0,1,2\}$ a cada potencia de 2 tal que $latex \sum_{i=0}^{\infty} n_i 2^i = x$.
Posts
Solución a "Comesolo"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 8 Autor: lhchavez Fuente: Félix
Este problema es especial porque es el primero en omegaUp de solo salida! Usualmente lo que debes esperar cuando te enfrentes con uno de esos problemas es que sea un problema NP que no tiene una solución rápida, y usualmente te pedirán que te aproximes lo más posible a la solución óptima. Esto significa que te vas a tener que valer de técnicas ad-hoc y heurísticas para sacar puntos.
Posts
Solución a "Colección"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 5 Autor: Alexis Cervantes / César Cepeda Fuente: Alexis Cervantes / César Cepeda
_Estructura de la solución: _¿Qué nos están pidiendo? El problema nos esta pidiendo que encontremos un subconjunto de las tarjetas tal que la suma de todos los puntajes de las tarjetas de ese subconjunto sea la maxima posible, y la suma de sus precios sea menor o igual al dinero con el que cuentas.
Posts
Solución a "Ubongo 3D"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 8 Autor: Miguel Covarrubias Fuente: Miguel Covarrubias
La solución pone piezas de manera recursiva mientras quepan en el tablero y no se empalmen.
resuelve(pieza) si pieza > P regresa “Si” para cada rotación de la pieza para cada casilla g del tablero para cada cubo c de la pieza si al poner c sobre g, la pieza queda dentro de los primeros 2 niveles del tablero y no se empalma con otra pieza ya puesta entonces marca las posiciones de los cubos de la pieza como ocupados resuelve(pieza + 1) desmarca los cubos de la pieza Para rotar una pieza se puede rotar por $latex 0^o$, $latex 90^o$, $latex 180^o$ o $latex 270^o$ alrededor de cada eje.