Posts

Solución a "Pulseras"

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 10 **Autor: **Alain Acevedo Mejía Considero este problema como un buen ejemplo para quienes desean comenzar a trabajar con problemas de programación dinámica. Se nos pide calcular la cantidad de pulseras diferentes que se pueden construir bajo ciertas condiciones. Podemos comenzar preguntándonos, ¿qué sucede si la primera cuenta es negra? La siguiente podrá ser sólo blanca. Y si comenzamos con una blanca, la siguiente puede ser negra o blanca.
Posts

Solución a "Los Bloques de Link"

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 8 **Autor: **Alain Acevedo Mejía Es claro que no es posible probar todas las sucesiones posibles de movimientos de los bloques para encontrar la solución (a excepción de casos muy simples). El número de tales sucesiones puede ser infinito en caso de que se puedan formar ciclos de movimientos (lo cual sucede en muchos de lo casos de prueba), y aún en casos donde el número sea finito puede suceder que no se tenga tiempo para probarlos todos.
Posts

Solución a "Problema"

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 10 **Autor: **Hugo Dueñas Primero, dado una secuencia $latex A$ denotaremos por $latex s(A)$ a la suma de los elementos de A. Entonces podemos replantear el problema como: Dada una secuencia $latex S$ debemos de econtrar una subsecuencia $latex A$ de $latex S$ tal que $latex s(A) - (s(S) - s(A))$ sea la minima posible. Ahora, como $latex s(A) - (s(S) - s(A)) = 2 \times s(A) - s(S)$, entonces tenemos que minimizar $latex 2 \times s(A) - s(S)$ que es lo mismo que minimizar $latex s(A) - s(S)/2$.
Posts

Solución a "Alfiles"

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 7 **Autor: **Hugo Dueñas Lo primero que se debe de notar es que en cada una de las $latex 2n-1$ diagonales principales, las cuales mostradas en la imagen de abajo, habrá máximo 1 alfil. Lo mismo se cumple para las diagonales invertidas, mostradas también en una imagen abajo. Ahora, cada diagonal principal se cruza con ciertas diagonales invertidas. Entonces se plantea una solución de tipo Backtracking que corre sobre las diagonales principales marcando diagonales invertidas a cada paso (representando que se ha colocado un alfil en el cruce de esas dos diagonales).
Posts

Solución a "Mario Reloaded"

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 8 **Autor: **Pavel Herrera Dominguez) Observaciones Lo primero es ver como se modelan los estados del problema sin pensar en que Mario puede tomar los atajos, únicamente pensar en las llaves, claramente existen $latex n\times2^m$ estados, pues no importa el orden en que se toman las llaves solo las llaves que se tienen al llegar a cada puerta. A partir de aquí nos referiremos como estado a la puerta y las llaves que trae Mario.
Posts

Solución a "El collar de perlas"

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 10**  Autor: **Félix Rafael Horta Cuadrilla

En una bosque habitan dos clanes de enanos: los enanos rojos y los enanos verdes. Durante sus expediciones en las cuevas cercanas, un grupo de enanos rojos y verdes encontraron un collar formado por perlas blancas y negras que no tienen ningun valor, pero al final del collar hay un valioso diamante. Los dos clanes de enanos quieren apoderarse del diamante.

Para resolver el problema de manera pacifica deciden jugar el siguiente juego: a cada uno de los N enanos se le asigna un numero del 1 al N (un numero diferente para cada enano) y dos listas de numeros, una negra y una blanca (las listas pueden ser diferentes entre si). Cada lista contiene una cantidad diferente de numeros, cada numero i en cualquier lista representa al enano i.

Durante el juego, el collar se pasa de un enano a otro de acuerdo con las siguientes reglas: cuando un enano recibe el collar, el quita la primer perla en el collar y si la perla es blanca, entonces pasa lo que quedo del collar a cualquier enano que este en su lista blanca (al que el quiera), pero si la piedra es negra, entonces pasa lo que quedo del collar a algun enano de su lista negra. Para empezar el juego, el collar se le da a un enano aleatoriamente.

En algun momento el collar solamente va a tener el diamante, el enano que recibe el collar en este estado gana el diamante para su clan y el juego termina.

Posts

Iniciando milestone en OmegaUp: Karate Kid

Después de año y medio de desarrollo (en nuestros tiempos libres) y de finalmente ser la plataforma de concurso en 3 de los eventos de programación más importantes de México ( Olimpiada Mexicana de Informática OMI, Concurso Nacional de Programación CONACUP y el Concurso Universitario de Programación de Aguascalientes CUPA) hemos decidido graduar nuestro motor de evaluación y concursos para invertir más tiempo en la usabilidad del sitio como plataforma de aprendizaje en un nuevo milestone: Karate Kid.
Posts

CONACUP 2012 - Todo un éxito

Los días 3 y 4 de Noviembre del 2012, 80 de los mejores programadores de México se dieron cita en el ITESO de Guadalajara, Jalisco para participar en el 2do Concurso Nacional Abierto de Programación CONACUP, organizado por la Sociedad Latinoamericana de Ciencia y Tecnología SOLACyT. El equipo organizador del CONACUP 2012El equipo organizador del CONACUP 2012 Nos da mucho gusto que Omegaup fue la plataforma oficial para la evaluación de los problemas y estamos completamente comprometidos con el proyecto para los años venideros.
Posts

CUPA 2012 - Resultados

El pasado 20 de Octubre se llevó a cabo el Concurso Universitario de Programación de Aguascalientes CUPA. Participaron 26 equipos de 3 personas en un examen de 9 problemas. Los problemsetters oficiales fueron la Dra. Aurora Torres (Plano Estropeado), David Esparza Alba (Traductor, Display Descompuesto, Puntos imantados, Primos juntos siempre y Santas bombillas ) y Óscar Dávalos (Cadenas de Potencias de 2, Múltiplos y Cubos.). Omegaup fue la plataforma de evaluación del CUPA.
Posts

Solución a "Teclado Roto"

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 2** Autor: **Jorge Alberto González Martínez Los temas para el examen donde apareció este problema eran pilas, colas y búsqueda binaria. Después de haber estudiado los temas, es buena idea combinar la teoría aprendida. El problema del teclado roto describe una serie de operaciones en las que es necesaria una estructura en la que sea posible agregar elementos por ambos lados (izquierda y derecha).