Posts
Practicando para la OMI en omegaUp
Si estás practicando para la Olimpiada Mexicana de Informática 2014, omegaUp tiene disponibles los exámenes nacionales desde el 2009 para que intentes resolverlos. Aquí están los enlaces a los concursos de práctica
OMI 2009, día 1 (Karel) OMI 2009, día 2 (Lenguaje) OMI 2010, día 1 (Karel) OMI 2010, día 2, (Lenguaje) OMI 2011, día 1 (Karel) OMI 2011, día 2 (Lenguaje) OMI 2012, día 1 (Karel) OMI 2012, día 2 (Lenguaje) OMI 2013, día 1 (Karel) OMI 2013, día 2 (Lenguaje) Nuevamente agradecemos a Kuko Lopez de la OIEG por ayudarnos a subir los problemas del 2009 al 2011.
Posts
38 nuevos problemas de Karel disponibles gracias a la OIEG!
La Olimpiada de Informática del Estado de Guanajuato (OIEG), liderada este año por José Refugio López (Kuko), han hecho públicos 38 problemas de Karel para que la comunidad en general pueda practicar previo a la Olimpiada Mexicana de Informática 2014.
Pueden resolver los nuevos problemas en los siguientes concursos:
Nivel introductorio:
ORIG2013 Karel PreEstatal Ejercicios 1 Nivel básico
ORIG 2013 Examen PreEstatal Karel Nivel intermedio
Posts
Aventuras en el evaluador, parte 1
Como parte de los propósitos de año nuevo, me dispuse a hacer un refactor masivo del código con el cual se evalúan y ejecutan las soluciones en omegaUp. Habían muchas motivaciones para hacer la actualización: tener un sandbox más moderno, eliminar un montón de código duplicado, mejorar las pruebas, el logging, el paralelismo en los jueces, cómo se despliega el tiempo y la memoria, el desempeño de los envíos, soportar C++11 y más lenguajes.
Posts
Solución a "Químicos"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 6 Autor: Luis Héctor Chávez (lhchavez) Fuente: Ethan Jiménez Vargas
Éste es un problema que tiene una solución elegante y determinística pero requiere algoritmos avanzados bastante complicados. Lo bueno es que es posible aproximar a la solución utilizando fuerza bruta mediante backtracking.
El problema nos pide encontrar una manera de asignar sustancias a los tubos y después mezclarlas con las dos operaciones disponibles (suma y diferencia absoluta) para terminar con un acomodo homogéneo de sustancias: la diferencia entre el tubo con más cantidad y con menos cantidad de sustancia debe ser lo más pequeña posible.
Posts
Solución a "Crucero"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 4 Autor: Saúl Germán Gutiérrez Calderón Fuente: USACO Enero 2009 Gold
Como se puede notar, al trazar la ruta óptima del crucero se está desperdiciando mucho espacio, y daría lo mismo si expandiésemos la isla para que no se desperdiciara espacio entre la ruta y la orilla de ésta.
Si supiéramos cual es la ruta óptima del crucero para expandir la isla bastaría con hacer un Flood Fill para rellenar los espacios con agua que quedan dentro de la ruta.
Posts
Solución a "Mocha Hojas"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 17 Autor: Freddy Román Cepeda Fuente: Alberto José Ramírez Valadez
Para simplificar el análisis, podemos notar que la respuesta que nos piden es igual al total de los pesos de las hojas del árbol menos el total de los pesos de las hojas del árbol ya balanceado. De ahora en adelante, trataremos el problema como si tuviéramos que conseguir este segundo valor, en vez del número de operaciones.
Posts
Solución alternativa a "Decepción"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 8 Autor: Freddy Román Cepeda Fuente: Ethan Jiménez Vargas
Esta es una solución alternativa al problema. La solución pensada originalmente consiste en una búsqueda podada. Sin embargo, esta solución corre en tiempo y memoria $latex O(N^2)$, mucho mejor de lo necesario para obtener todos los puntos.
Podemos dividir el problema a la mitad con una observación simple: la torre más alta debe verse desde ambos lados.
Posts
Solución a "Panoramas"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 17 Autor: Miguel Ángel Covarrubias Fuente: Miguel Ángel Covarrubias
El problema es un Steiner tree problem (un MST pero donde sólo hay que conectar un subconjunto de nodos) pero con costo por nodo en vez de por arista. El grafo de los panoramas es un árbol más un ciclo. Para un árbol una solución es poner como raíz a $latex s_1$ y para cada $latex s_i$ marcar los nodos en su camino hacia la raíz.
Posts
Seguridad: IE en Windows XP
Debido a un reciente cambio para mejorar la seguridad de la conexión a omegaUp, hemos decidido dejar de soportar oficialmente IE en Windows XP, a pesar de que sabemos que aún sigue siendo el segundo sistema operativo más común a nivel mundial[1]. Si aún están obligados a usar Windows XP, por favor utilicen algún navegador moderno (Chrome, Firefox u Opera) o alguna versión portátil.
Para los interesados, el cambio consistió en hacer un par de optimizaciones para nginx[2], para reducir el tiempo de espera al primer byte, y actualizar la configuración de TLS: se quitaron SSLv2 y SSLv3 (que ya se consideran inseguros), se agregaron TLSv1.
Posts
Introducción a omegaUp, parte 0
Hola!
Hemos recibido varias preguntas sobre cómo se envían soluciones a omegaUp. Decidí escribir una introducción a omegaUp, antes de empezar a aprender a resolver problemas. En resumen:
El objetivo de los concursos es acumular más puntos que todos los demás participantes. En caso de empate, se toma en cuenta la suma de los penalties (dependiendo del concurso puede no haber penalties, ser el tiempo desde que inició el concurso hasta que enviaste la solución o el tiempo desde que abriste el problema por primera vez hasta que lo resolviste).