ACM Regional 2007 Mexico and Central America

Cuando escribí este post no sabía que los Turing Machines iban a ir al mundial ni tampoco me sabía los nombres de todos ni los de su equipo, por eso no los mencioné, pero Turing Machines tambien son un buen equipo(quedaron en 3° y fueron al mundial).

Sucedió en el ITESO el Domingo 4 de Noviembre del año 2007 cuando luego de 5 horas de concurso el profesor Carlos Fernández Guillot dio a conocer los resultados preliminares del concurso regional ACM. El concurso regional fué realizado simultáneamente en varias sedes, todo parecía indicar que los 3 primeros lugares fueron de la sede ITESO, de los cuales 2 calificarían para participar en el concurso mundial, según cuentan los rumores participaron alrededor de 120 equipos.
El primer lugar según los resultados preliminares fue ACM Problem Solvers de la Universidad de Guadalajara(mi equipo), el segundo lugar fue el equipo Hausdorff de la Universidad de Guanajuato.
Cada año la ACM(Association for Computing Machinery) organiza un concurso de programación a nivel mundial llamado ICPC(International Collegiate Programming Contest) donde participan equipos de muchas universidades, cada equipo está formado por a lo mas 3 integrantes.
Para filtrar a los equipos la ACM organiza concursos regionales, donde se pueden inscribir equipos de universidades de determinadas regiones del mundo y los mejores equipos de cada región son elegidos para participar en el concurso mundial ACM ICPC.
Estos concursos tratan sobre escribir programas que resuelvan algunos problemas. Pueden ser desde problemas simples como calcular impuestos ó sacar el promedio de calificaciones de alumnos hasta problemas mucho mas complejos como optimización de horarios, cifrado ó cálculo del flujo del tráfico en una carretera.
Al inicio del concurso a cada equipo se le asigna una sola computadora y se les otorga un conjunto de problemas(el mismo conjunto a todos los equipos), durante el concurso pueden mandar una solución en cualquier momento y los jueces deben decir si está bien o mal la solución.
El ganador es el equipo que haya resuelto mas problemas y en caso de haber empate el ganador se decide por suma de puntajes(el equipo que tenga menos puntos gana).
El puntaje de un equipo es calculado sumando los puntajes de cada problema que haya resuelto, y el puntaje de cada problema resuelto se calcula sumándole 20 veces el número de soluciones incorrectas enviadas a ese problema más el número de minutos transcurridos a partir del inicio del concurso hasta el momento que fue enviada la solución correcta. Esto les da una ventaja considerable a quienes hacen pocos envíos y a quienes resuelven primero los problemas fáciles.
Luego del concurso puede haber apelaciones de equipos que consideren que sus soluciones fueron mal juzgadas en algún momento, estas apelaciones pueden tomar unas dos semanas en resolverse.
El Domingo 4 de Noviembre los equipos ACM Problem Solvers y el equipo Hausdorff quedaron en 1° y 2° lugar en resultados preliminares con 6 problemas resueltos. Mientras que el 3° lugar se quedó con 5 problemas resueltos y el resto de los equipos resolvió 4 problemas o menos.
Hasta el momento todo parece indicar que los dos primeros lugares de la región México y Centro América se mantendrán de esa manera puesto que el equipo que quedó en 3° lugar no manifestó haber sido mal evaluado en cuanto al número de problemas resueltos.
La Universidad de Guanajuato ya ha llevado otras veces a equipos a los mundiales, pero es la primera vez que la Universidad de Guadalajara llevará un equipo a la competencia mundial; sin embargo, el equipo Veni Programi Victi, también de la Universidad de Guadalajara, fue el primer lugar de la sede ITESO en el concurso regional 2006.
Vale la pena detenerse a analizar la historia de estos dos equipos ganadores.
El primero, mi equipo, ACM Problem Solvers, integrado también por Juan Pablo Marín y Mario Alberto Díaz Torres, quienes eligieron los sobrenombres de Uxos y Cumbias(respectivamente) para la ACM, el sobrenombre que elegí fue Lobishomen.
Uxos participó en la Olimpiada de Informática y fue seleccionado para la IOI(International Olympiad in Informatics) del 2006, regresando de la internacional entró al CUCEI ahí se adaptó a la ACM luego de haber tenido un buen papel en la Olimpiada de Informática.
En el concurso Regional del 2006 jugó un papel muy importante en el equipo Veni Programmi Victi que ganó en el primer lugar en la sede ITESO y el 6° lugar en general.
Cumbias participó en la Olimpiada de Matemáticas y ganó plata en la competencia nacional; no llegó al internacional pero en la Olimpiada de Matemáticas es mucho mas difícil llegar a un internacional, además de eso, Cumbias siguió resolviendo problemas después de haber participado en la Olimpiada de Matemáticas, aprendió a programar hace poco pero su determinación lo ha hecho avanzar muy rápido.
Sobre mí, ya hablé suficiente en el otro artículo(“¿Por qué mi carrera?”).
El equipo Hausdorff está conformado por Miguel Ángel Covarrubias, Juan Francisco Padilla y otro que no conozco su nombre pero le dicen el Copas.
Miguel Ángel Covarrubias, o Macs(el sobrenombre que suele utilizar) participó dos veces en la Olimpiada de Informática, y fue dos veces a la IOI, una en el 2006 y otra en el 2007, en esta última ganó una medalla de bronce bastante cercana a las medallas de plata.
Padilla participó también en la Olimpiada de Informática y fue a la IOI del 2003, y junto con Copas y otro participante llamado Rodrigo(que esta vez estuvo en otro equipo) quedaron en 7° lugar en el concurso regional del 2006, justo abajo de Vini Programi Victi.
De Copas solo sé que fue a la IMO(International Mathematical Olympiad).
Es curioso que en el equipo ACM Problem Solvers, Uxos es de Ameca y Cumbias y yo somos de Guadalajara, mientras que en el equipo Hausdorff, Macs es de Durango y Padilla de Guadalajara(Copas no se de dónde es), y esto es porque el equipo Hausdorff se formó en la Facultad de Matemáticas de Guanajuato, y ahí muchos estudiantes son de otras ciudades.
La formación del equipo ACM Problem Solvers se dió de manera diferente, Uxos y yo ya habíamos participado improvisando equipos como invitados en concursos locales ACM(las universidades a veces organizan concursos para prepararse para el regional) antes de entrar a la universidad, cuando eramos olímpicos. Sin embargo nunca ocupamos el primer lugar en uno de esos concursos improvisando equipos(algunas veces conseguimos el segundo pero el primero no lo obtuvimos sino hasta este semestre que nos preparamos realmente como equipo), por lo que las bases del equipo ACM Problem Solvers vienen formándose desde hace mas de 2 años(no integramos un mismo equipo en el 2006 porque se me pasó la fecha de inscripción a la universidad y tuve que esperarme para entrar hasta el siguiente semestre).
A Cumbias lo conocí en la Olimpiada de Matemáticas, desde ese entonces se mostró interesado en ciencias de la computación y a veces pensaba que tal vez alguna vez estaría en mi equipo ACM, pero me mantuve callado hasta el semestre pasado que me manifestó que le interesaba participar.
A lo largo del tiempo que hemos estado involucrados en estas competencias, los integrantes de estos dos equipos nos hemos encontrado varias veces, a veces como rivales, y otras veces todo lo contrario. En el 2004 Padilla y yo asistimos como competidores de la OMI(Olimpiada Mexicana de Informática) a unos entrenamientos en Piedras Negras, en el 2005 Padilla fue entrenador de Uxos y Uxos y yo ambos fuimos parte de la Selección Jalisco, luego, Padilla también ayudó con los entrenamientos de la preselección nacional de ese año, donde nos encontrábamos Macs, Uxos y yo.
En el 2006, como México fue sede de la IOI, se le permitió llevar 2 selecciones(cada una de 4 integrantes), pero solo una de ellas podía ganar medallas, a la cual se le llamó México A, y a la otra se le llamó México B. En la selección A estaba yo, y en la selección B estaban Uxos y Macs; ese año yo gané medalla de bronce obteniendo un puntaje bastante mayor(en la IOI gana el que tenga mas puntaje, no vale la pena dar detalles de cómo se obtienen los puntos en la IOI) que Macs, y tengo que admitir que en ese momento no sospechaba cuánto iba a mejorar el siguiente año.
En el 2007 yo fui entrenador de la preselección nacional, en la cual se encontraba Macs, ese mismo año se organizó un concurso de programación a nivel nacional abierto(cualquiera podía participar y era individual), ahí el primer lugar lo ocupó Macs y el segundo lugar lo ocupé yo. Ese mismo año, en la IOI yo fui como sublider(algo así como el couch) y Macs ganó su medalla de bronce.
El hecho de que ya no participara en la olimpiada de informática me había hecho perder algo de práctica, así que 3 semanas antes del regional ACM pedí permiso para trabajar desde mi casa(hago mas de una hora de camino entre el trabajo y mi casa, trabajando desde mi casa pude tener como 3 horas extras para entrenar los días que trabajaba) y también pedí permiso en la escuela para faltar. Entrené mucho durante esas 3 semanas para poder recuperar toda la práctica y la agilidad de mi razonamiento para la competencia regional; ya Macs me había ganado en mas de una ocasión debido al duro entrenamiento que estuvo llevando.
Una semana antes del regional, nosotros, el equipo ACM Problem Solvers, fuimos a un concurso en Chihuahua, ahí tuvimos tiempo de entrenar juntos y logramos una victoria que sorprendió a todos(resolvimos 7 problemas y el segundo lugar resolvió solamente uno).
Ya el día del regional ejecutamos la estrategia que tanto habíamos estado depurando y noté cuan efectivo había sido mi entrenamiento de 3 semanas.
Al inicio del concurso nos propusimos olvidarnos de ganar y solamente pensar en resolver el mayor número de problemas, eso para evitar mirar cuántos problemas llevaban los demás equipos y concentrarnos en nuestro trabajo,pero desde el inicio tomamos la ventaja con un envío de Uxos.
Mientras Uxos implementaba la solución del primero, Cumbias y yo leíamos los otros problemas y discutíamos sobre la dificultad de cada problema, luego de conseguir el primer problema aceptado le pasamos otro problema a Uxos que sabíamos que podía saber fácilmente cómo resolverlo; pero cuando envió la solución se la rechazaron.
Mandamos a imprimir el código y yo pasé a implementar otro mientras Cumbias pensaba en un problema y Uxos buscaba su error en las hojas impresas. Terminé de implementar el problema, lo mandé, pero fue rechazado.
Mandé a imprimir el código y dejé a Cumbias implementar. Al poco tiempo de leer mi código comprendí cual era el error y Cumbias dejó que lo interrumpiera unos segundos para corregir el error(en algunos casos el programa intentaba dividir entre 0). Envié la solución corregida y fue aceptada.
Cuando Cumbias terminó de implementar lo suyo envió su solución y también fue aceptada. Comencé a implementar una solución que ya había pensado, no era muy difícil de ver pero era muy propensa a errores, mientras, Uxos y Cumbias intentaban encontrar el error en el código fuente y frecuentemente me encargaban mandar preguntas de ese problema.
Envié mi solución y recibí como respuesta “error de ejecución”(eso significa que el programa en lugar de terminar y dar una respuesta, terminaba de manera anormal, tal como lo hacen algunas aplicaciones que se cierran sin que se lo pidan y luego preguntan si se quiere mandar un informe de error), mandé a imprimir el código.
Al no encontrar error en la solución de Uxos, decidimos no confiar mas en las respuestas a las preguntas que hacíamos sino en el sentido común; así que le hice unos cuantos cambios al código de Uxos del problema que llevaba bastante tiempo revisando, los cambios que le hice iban de acuerdo con la interpretación del problema de acuerdo al sentido común pero era contraria a las respuestas de las preguntas que hicimos. El resultado fue que conseguimos que aceptaran ese problema.
Quedaba hora y media de concurso, llevabamos 4 problemas resueltos estaba ya implementada una solución que escribí que no servía y tenía escrita a mano la mayor parte de otra solución mientras que el único problema que no habíamos intentado parecía muy difícil. La pantalla nos mostraba en 2° lugar, abajo de un equipo de Culiacán por un problema.
Les encargué a Uxos y a Cumbias que revisaran el código del problema que no funcionaba, mientras yo copié la solución que escribí a mano y le arreglé errores que tuve mientras lo hacía a mano. Mandé la solución a este otro problema pero recibí la respuesta de que era demasiado lenta, hice un intento por mejorarle la velocidad y la volví a mandar sin muchas esperanzas, pero fue aceptada.
Quedaba media hora de concurso, habíamos resuelto 5 problemas y uno no servía. Le cambié unos detalles al que no servía para que me dijeran que era muy lento si tenía una posible falla que podía provocar “error de ejecución”, pero en lugar de eso recibimos como contestación “respuesta incorrecta”(el programa funcionaba pero mandaba resultados erróneos), así que concluimos que el “error de ejecución” fue una contestación errónea por parte de los jueces, no tardé mucho en ver por qué daba respuesta incorrecta.
Corregí la solución, la mandé y nos la aceptaron faltando 15 minutos para el final del concurso. Terminamos con 6 problemas resueltos, nos salimos faltando 15 minutos ya que el otro problema que no atacamos se veía demasiado difícil para resolverse en ese tiempo.
Una hora antes de terminar el examen apagaron la pantalla donde se veía cuantos habían resuelto cada equipo, así que no sabíamos en qué lugar quedamos. Tuvimos que esperar hasta la hora de la comida a que el profesor Carlos Fernández Guillot anunciara que eramos los ganadores.
Me dio mucho gusto notar los resultados obtenidos del entrenamiento, y sobre todo, haber llevado a cabo el tan esperado encuentro ACM Problem Solvers vs Hausdorff.