El camino rumbo a la IOI 2014

Después de varios meses de preparación y selección, México está listo para participar en la IOI 2014 a celebrarse en Taiwán del 13 al 20 de Julio.

De izquierda a derecha, nuestros seleccionados son:

  1. Carlos Galeana Hernández del Distrito Federal
  2. Daniel Talamás Cano de Coahuila
  3. Diego Alonso Roque Montoya de Nuevo León
  4. Jordán Alexander Salas de Coahuila

Nuevamente, nuestra selección cuenta con 3 ganadores absolutos de la Olimpiada Mexicana de Informática: Jordán ganó la OMI 2014, Talamás ganó la OMI 2013 y Diego Roque ganó la OMI 2012. Les deseamos la mejor de las suertes!

Todos los concursos de selección y la gran mayoría de las prácticas usadas durante el proceso están disponibles en omegaUp. Estos fueron los concursos y problemas usados:

Etapa 1
Durante esta etapa le pedimos a los olímpicos que lean el libro de Problemas y Algoritmos de Luis Vargas como mínimo como guía para resolver los problemas.

Temas introductorios: variables, cadenas, arreglos, matrices, ciclos, mcd, mcm:
Pilas, colas y búsqueda binaria
Búsquedas, árboles y acotamiento y poda
Recursión y backtracking
Búsquedas con espacios de estados
Divide y vencerás
Programación dinámica
Teoría de Grafos
Etapa 2 
 Esta etapa consistió de entrenamientos presenciales y prácticas externas.
Etapa 3

Material de lectura

Como parte del proceso, recomendamos a nuestros olímpicos revisar a profundidad los siguientes sitios con material de estudio y problemas para practicar:

  1. Temario oficial para la IOI.
  2. El libro en español de Luis Vargas sobre Problemas y Algoritmos. Básicamente el objetivo de la Etapa 1 es que dominen los contenidos de este libro, por lo que su lectura (y práctica) es casi obligatoria. Les recomendamos no esperar a que inicie el preselectivo para empezar a leerlo.
  3. Libros recomendados para la IOI, a estas alturas su lectura es casi obligadasi desean llegar y tener buenos resultados en la IOI:
    1. Introduction to Algorithms 3rd Edition, Cormen et. al.
    2. Competitive Programming 1, 2 y 3, Steven & Felix Halim. La versión electrónica del Libro 1 ya es gratis.
    3. Otro libro introductorio: Algorithms Unlocked de Cormen. Más prosa y menos profundidad en las demostraciones que el Introduction al Algoritmos. Recomendado para quienes están en su primer año de concursos.
  4. omegaUp 🙂
  5. El blog de Pier Paolo, sección Algoritmos: http://pier.guillen.com.mx/
  6. El blog de Rodrigo Burgos: http://algorithmmx.blogspot.com/
  7. Topcoder Contenido educacional (altamente recomendado!)
  8. Preguntas omegaUp –  Cualquier duda técnica que tengan, la pueden publica en nuestro sitio de preguntas. También pueden leer nuestras respuestas a preguntas pasadas.
  9. Guía rápida para el ACM ICPC. Muy buena para repasar pero no todos los temas aplican para la IOI, chequen el temario primero.

Otros sitios para practicar

  1. Croatian Open Competition in Informatics (COCI). Varios meses antes de la IOI, el comité de la Olimpiada de Croacia hace exámenes en línea. Los exámenes son de muy buen nivel y todos los problemas con sus soluciones están publicados en la misma página, les recomendamos darles un vistazo y practicar con todos ellos. Noten que los problemas de la COCI están en inglés y no son traducidos al español, por lo que es bueno que estén preparados. Afortunadamente Google Translate típicamente hace un buen trabajo con estos enunciados.
  2. USA Computing Olympiad (USACO)   Estos problemas sí son traducidos al español. Otro detalle importante sobre la USACO/COCI es que sus futuros competidores en la IOI también participan en estos concursos, por lo que les servirá para medir su nivel.
  3. USACO Training Gate. Plataforma paso-a-paso para entrenar con problemas para la IOI. Incluye muy buenas explicaciones de la construcción de soluciones a varios problemas y tutoriales. Este blog tiene varias soluciones para el USACO training gate. Úsenlas sólo cuando estén completamente atorados en un problema, después de haberlo intentado.
  4. Topcoder.com/tc
  5. Codeforces: http://codeforces.com/
  6. ACM UVa Online Judge
  7. Codechef: http://www.codechef.com/

Esperamos que esta información le sirva a las próximas generaciones que participarán por un lugar en la Selección Mexicana de Informática.

Yeah, science b#$ch!: Entre más omegaUp, mejores resultados

Del 1 al 6 de Mayo pasados, se llevó a cabo la Olimpiada Mexicana de Informática 2014 en Pachuca, Hidalgo. Más de 100 participantes de toda la república concursaron y omegaUp fue la plataforma de evaluación oficial (el examen del Día 1 lo puedes encontrar aquí y el de el Día 2 aquí).

Por primera vez, durante el periodo 2013-2014 varios Estados, como Morelos, Chihuahua y Guanajuato  empezaron a promover omegaUp entre sus olímpicos y usar nuestra plataforma para correr sus concursos locales estatales.

Dentro de los resultados, la estadística que más nos llamó la atención en omegaUp fue la tabla de posiciones por Estado. Minutos antes de la OMI 2014, ya habíamos predicho el Top 10 de Estados basados en las visitas a omegaUp.com durante los 6 meses anteriores a la OMI:

 

Los resultados finales por Estado fueron:

Si bien, el orden no es exactamente el mismo, 9 de los 10 mejores Estados en la OMI también estuvieron dentro del Top 10 de visitas a omegaUp.com. Entendemos que usar más omegaUp no es el único factor para tener buenos resultados en la OMI, pero esta estadística es una buena muestra de que omegaUp funciona!

Recomendamos a todos los Estados promover omegaUp entre sus alumnos y usarlo para correr sus concursos locales. Entre más temprano en el proceso lo usen, será mejor – tendrán más visitas y la probabilidad de tener un mejor lugar en la OMI será más alta.

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

Nuevamente agradecemos a Kuko Lopez de la OIEG por ayudarnos a subir los problemas del 2009 al 2011.
Que se diviertan!

 

 

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:

Nivel básico

Nivel intermedio

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.

Material de estudio

Antes de pasar a la lista de problemas, quiero empezar con las lecturas recomendadas para empezar a resolver problemas en omegaUp:

Problemas directos
Estos concursos fueron diseñados para familiarizarse con la programación competitiva en general. Son excelentes para empezar y su solución generalmente no requiere dominar una técnica en específico, más bien requieren saber usar las construcciones (ciclos, condiciones, etc…) del lenguaje correctamente:

Tienes más sugerencias de problemas o dudas sobre los existentes? Escríbelos en los comentarios.

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. Hay que notar que no nos piden la ruta más corta para capturar la moneda, más bien cuál es el menor tamaño con el que podemos llegar.

La idea principal es ir probando los tamaños de escalera, empezando desde 0 hasta 50, y para cada tamaño probar si es posible llegar a la moneda o no. Si empezamos probando los tamaños de menor a mayor, la primer escalera que lo logré será el resultado.

Para probar que se puede llegar a la moneda, se puede usar búsqueda en amplitud o búsqueda en profundidad. Dado que el tamaño del mapa es relativamente pequeño, es posible usar búsqueda en profundidad y pararla en cuanto “pisemos” la moneda (de nuevo, no nos interesa saber si la ruta que la búsqueda siguió para dar con la moneda fue la menor de todas las posibles, con llegar a ella basta).

Este par de observaciones son suficiente para resolver el problema. Si el lector quiere más reto, hay otra observación que permitiría reducir el número de búsquedas que hay que hacer de 50 a 6…

Esta es la solución de charlyhlms usando búsqueda en profundidad.

Esta es la solución de spleensarethebest usando búsqueda en amplitud y optimizando la cantidad de pruebas de tamaños de escaleras que hay que hacer.

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.

Solución a Las Cartas del Dr. Lira

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 1
Autor: Joemmanuel Ponce Galindo
Fuente: Topcoder

Básicamente lo que nos pide el problema es encontrar el número de cartas que son distintas entre la configuración que es dada como entrada y una configuración donde las cartas estén alternadas.

Cómo se explica en el problema, sólo hay 2 estados posibles en los que una carta puede estar: negro (B) y blanco (W). En otras palabras, la observación clave para resolver el problema es darse cuenta que sólo existen 2 configuraciones que cumplen con las reglas que necesita Dr. Lira: Una configuración donde la primer carta es W, la siguiente B, la siguiente W y así sucesivamente. La otra configuración posible es donde las cartas empiezan con B, forzando la siguiente carta a ser W y esta a su vez forzando la siguiente carta a ser B.

Contar el número de caracteres diferentes entre una cadena y otra sólo requiere de un ciclo, por lo que la complejidad es lineal con respecto al tamaño de la cadena. Lo único que tenemos que hacer es entonces comparar la cadena dada como entrada con las configuraciones BWBW.. y WBWB…, contar el número de diferencias y dar como salida el mínimo de estos números.