Introducción

Desde 1977, año con año la ACM (Asociation for Computing Machinery) ha organizado el ACM International Collegiate Programming Contest. En este concurso participan equipos de estudiantes representando a las universidades de todo el mundo para probar sus habilidades en la solución de problemas, programación y trabajo en equipo.

Este concurso consiste en tres etapas: local, regional e internacional. En la etapa local, cada institución selecciona que equipos lo representarán en el concurso regional. México pertenece a la región México-Centroamérica, en la cual se disputan dos lugares para la participación en el ACM International Collegiate Programming Contest World Finals. En la etapa regional pueden participar hasta tres equipos representativos por universidad.

La Benemérita Universidad Autónoma de Puebla ha participado en los concursos regionales 2002 y 2003. En el 2002 ninguno de los dos equipos representantes, logró resolver algún problema.

En el 2003, después de una mayor preparación y la integración de elementos de Computación y Físico-Matemáticas, se logró un grandioso resultado. La BUAP obtuvo el 3º y 10º lugar en la Sede de Querétaro y 7º en la UDLA, logrando así el 6º, 15º y 25º lugar de entre 106 equipos participantes.

El Capítulo Estudiantil de ciencias de computación ha integrado dentro de sus planes de trabajo, la difusión de este concurso en la BUAP, así como dar apoyo al proceso de entrenamiento para dicho concurso;teniendo como meta principal hacer que la BUAP represente a la región de México y Centroamérica en el concurso de programación internacional ACM.

Las siguientes notas pretenden describir de forma clara el mecanismo de este concurso. En la sección 2 “Reglas del concurso” se describirán cada una de las reglas del concurso. En la sección 3 “Trabajo en equipo” se mostrarán algunos tips para la selección de un equipo, así como técnicas de trabajo en equipo.La sección 4 “Escoge tu lenguaje de programación” mostrará las ventajas y desventajas de los lenguajes de programación que pueden ser empleados en este concurso.La sección 5 “Estilo de programación” explicará lo importante de tomar un estilo de programación propio y preferentemente como equipo para una mayor eficiencia en la programación. En la sección 6 “Entrada y salida estándar o de archivos” se te mostrará como manipular las entrada en los lenguajes de programación de C y Java; por último en la sección 7 “Problemas ACM” se te mostrarán algunos problemas comunes de este concurso para que intentes resolverlo.

Reglas del concurso

A continuación se presenta un listado de todas las reglas que aplican a cualquier concurso de programación ACM.

• Un equipo puede estar compuesto de tres integrantes como máximo de la misma escuela, admitiendo hasta un integrante que esté cursando su primer año de maestría.
• Un instante antes de iniciar el concurso, se le entregará a cada equipo un conjunto de problemas, que tendrán que resolver en un periodo de tiempo determinado.
• Los lenguajes de programación permitidos son C, C++, Java y Pascal (opcional).
• No se permite traer al concurso calculadoras, computadoras portátiles, CD's, diskettes, así como ningún dispositivo electrónico.
• Se permitirá a cada equipo cualquier información impresa de hasta 25 hojas, sin importar el contenido.
• A cada equipo se le asignará un equipo de computo en el cual podrán editar y probar sus códigos durante el concurso de programación.
• Durante el concurso existirán jueces que dictaminarán si los programas resuelven los problemas. Su decisión será inapelable.
• Los jueces pueden responder de las siguientes formas a cada uno de los códigos fuentes enviados:
• Accepted (Yes). El programa enviado resuelve el problema.
• Wrong Answer (No). El programa no resuelve de forma correcta todos los casos.
• No output (No). El programa no proporciona ningún dato de salida.
• Presentation Error (No). El programa resuelve el problema, sin embargo el formato de salida no coincide con la especificación del problema.
• Runtime Error (No).El programa ha tenido un error en tiempo de ejecución y terminó su ejecución.
• Time Limit Exceeded (No). El programa no terminó su ejecución en el tiempo límite para resolver el problema.
• Memory Limit Exceeded (No). El programa requiere de más memoria de la permitida para resolver el problema.
• Compile Error (No). El código del programa no compila.
• El primer criterio de desempate es el número de problemas resueltos.
• El segundo criterio de desempate es la penalización, quién tenga la menor penalización gana. Cada problema resuelto tiene una penalización de (n + 20 p ) puntos, donde n es el tiempo en minutos transcurrido desde el inicio el concurso hasta el momento del envío del programa, y p es el número de intentos previos de solución del problema fallidos antes de que fuera aceptado. Cada problema no resuelto tiene una penalización de 0.
• Desde el inicio hasta una hora antes de terminar el concurso, los equipos participantes podrán observar la tabla de posiciones de los equipos participantes, donde se mostrará la cantidad de problemas resueltos por equipo, así como la descripción de qué problemas fueron resueltos.

Trabajo en equipo

Trabajar en equipo es algo muy difícil, y en este tipo de concursos lo es aún más, ¿por qué? Porque únicamente hay una computadora para los tres (a la mayoría de los programadores nos gusta tener siempre la computadora), existe la presión del tiempo aunado con la presión de que existen otros equipos que nos llevan la delantera.

El primer paso para participar en este tipo de concursos es elegir tu equipo, para ello es recomendable que entre tus compañeros de equipo exista una buena relación y confianza, además que compartan el deseo de ganar.

Un buen equipo de programación debe tener conocimiento de los algoritmos estándares, así como la habilidad de encontrar el algoritmo apropiado para resolver cualquier problema y la capacidad de codificar cualquier algoritmo, claro, sin olvidar el sentirse cómodos como miembros de ese equipo.

Los problemas presentados durante los concursos de programación generalmente caen en unas de las siguientes categorías: búsquedas, teoría de grados, problemas geométricos, programación dinámica, problemas fáciles y problemas no estándares. Dentro de los problemas fáciles están aquellos problemas que pueden ser resueltos sin mucho conocimiento de algoritmos, mientras que los no estándares incluyen aquellos problemas de simulación, así como problemas donde se indican cómo resolver el problema, entre otros.

Cómo llegar a ser un buen equipo

No existe magia que los haga ser un buen equipo, sin embargo existen formas que les ayudará a mejorar. Primero, traten de que todos los miembros del equipo sepan escribir pseudocódigos, programar, depurar y compilar. Dado que no es muy común que exista una persona que sepa resolver cualquier tipo de problema, se recomienda que cada miembro del equipo se especialice en cada uno de las clasificaciones de los problemas. Todos los miembros deben saber las habilidades y defectos en el ámbito de resolución de problemas de los demás integrantes del equipo, esto se logra a través de trabajar juntos y la buena comunicación; con lo anterior, cualquiera podrá decidir cual es el miembro de equipo más indicado en resolver cierto problema. Cuando un problema es muy difícil es bueno intentar resolverlo en equipo, en caso contrario es mejor hacerlo solo debido a los diferentes estilos de programación que cada uno tiene

Como en cualquier competencia, entrenarse bajo circunstancias similares de un concurso, es de gran ayuda. Durante las simulaciones traten de entender realmente cuál es el problema, y tratar de clasificarlos en problemas fáciles, medianos y difíciles. Intentar primero los fáciles es una muy buena idea, ver en los standings que problema ha sido el más resuelto e intentar resolverlo. Si algún problema fue rechazado por el juez piensa sobre tus errores antes de empezar a depurar el código. No te quedes mucho tiempo con un problema, siempre es bueno cambiar de problema. En un concurso de 5 horas, tienen 15 horas de análisis (5 horas por cada miembro del equipo) y 5 horas máquina (donde codificarán, depurarán y compilarán todos los programas), por tal razón las horas máquina son muy valiosas, una forma de ahorrar tiempo máquina es escribir a papel las partes más importantes del código. Y por último todos deben de tener en mente que resolver un problema, implica que debe resolver al 100% todas las entradas que los jueces den a tu programa, por tal razón durante el análisis haz que tu programa sea capaz de resolver incluso los casos extremos, esto evitará tiempo de depuración, e incluso evitará que programen códigos que no resuelvan el problema.

Estrategia

¿Por qué es tan importante la estrategia? En primera instancia porque existe una única computadora que tiene que ser compartida, en segundo, porque los problemas tienen que ser distribuidos de alguna forma, y la última porque en un equipo siempre existe diversidad en todo aspecto lo cual tiene que aprovecharse.

A continuación se te mostrará algunos de los estrategias más comunes entre los equipos de programación:

• Rookie Team. Es la más fácil de todas, y muy útil para los equipos que no se conocen entre sí, o aquello que no quieren practicar juntos, pero sin embargo no es óptima. La idea es trabajar de forma individual, cada quien elige el problema que más le gusta lo resuelve y así consecuentemente para cada problema a resolver. Las ventajas en primera instancia es que no requiere de mucha práctica, el tiempo de penalización es generalmente mínimo debido a que siempre se resuelven los problemas más fáciles al inicio. Sin embargo tiene algunas desventajas: ya que los problemas más fáciles tienen el mismo nivel de complejidad, todos terminarán sus problemas al mismo tiempo, de esta forma la computadora requerirá de una sobredemanda en las primeras horas, pero una vez acabados los fáciles generalmente se ven estáncados en la resolución de los problemas más difíciles. Generalmente esta estrategia falla porque los más fáciles siempre son resueltos, sin embargo nunca da tiempo de resolver alguno de los más difíciles, por tal razón no es recomendable para un equipo que tiene el verdadero interés de ganar.
• Hombre máquina. La estrategia de hombre máquina es aquella donde sólo un miembro del equipo (denominado como T) usa la computadora, mientras que los otros dos miembros del equipos analizan los problemas, escriben en papel los algoritmos y las partes más importantes de código. Una vez que algún algoritmo es terminado, T escribe el código y si es necesario ayuda en el proceso de depuración, si el error es difícil de encontrar, el autor original auxiliar a encontrar el error. Las ventajas de esta estrategia son que T nunca tendrá que esperar a que le presten la computadora, y las tareas de la resolución de problema recae en aquellas personas que son mucho más especializadas en el este proceso. La principal desventaja es que no se aprovecha las habilidades de T, que al final de cuenta actúa como una secretaria. Si existe sólo una persona que conoce bien el entorno de programación es una buena estrategia.
• Think Tank. Primero los dos mejores analizadores de problemas dentro del equipo (denominados TT) leen todos los problemas, mientras que el tercero hace las rutinas de lectura de datos de entrada para cada uno de los problemas; todo lo anterior en un periodo de 15 minutos.Los TT discuten los problemas brevemente y eligen el problema más adecuado para el tercero (generalmente el más fácil) y le dan la idea global del problema para que comience a programar de inmediato. Mientras el tercero programa, los TT discuten sobre todos los problemas, y ponen las ideas principales de los algoritmos a papel. Después de una hora generalmente los TT tienen un buena perspectiva de todos los problemas a resolver, mientras que el tercero ya ha resulto al menos un problema. La siguiente decisión es elegir que problemas se resolverán. Los más fáciles y que requieran menor cantidad de programación son asignados al tercero, mientras que los TT se dividen el resto y colaboran entre sí (sucede siempre que si dos personas analizan en conjunto problemas difíciles, dan origen a soluciones creativas).En esta estrategia la computadora es únicamente utilizada para escribir código a partir de papel, y otra técnica adicional empleada es que si un programa es rechazado por el jurado y no se encuentra rápidamente el error (generalmente máximo 15 minutos de depuración) se descarta y se intenta otro; se vuelve a retomar en la última hora del concurso. Esta estrategia tiene como principal objetivo que en las primeras 4 horas se escribe el código de todos los programas que se propusieron resolver, mientras que en la última es depurar los códigos que no fueron aceptados por los jueces durante el transcurso de las primeras 4 horas. La principal ventaja de esta estrategia es que se aprovecha mucho más el tiempo máquina, y la probabilidad de resolver los problemas más difíciles se incrementan debido que los TT trabajan en ellos desde un inicio. Una clara desventaja es que comenzarán siempre por debajo de los demás equipos, y la penalización no es óptima, lo cual para ganar tendrán siempre que resolver al menos un problema más que los demás.

Algunos otros tips

Podrá ser que se entrenen mucho para el concurso de programación y tu estrategia se muy buena, sin embargo a la mera hora las circunstancias del concurso puede echar abajo todo lo anterior. Una cosa de la que debes estar conciente es que la suerte es un factor muy común en estos concursos, ya que generalmente dependiendo de los problemas unos tienen más probabilidades que otros, así que se les recomienda que al menos disfruten del concurso y participen como lo saben hacer, para lograrlo se recomienda lo siguiente:

• No prestes extremada atención al standing, excepto si algún equipo ha resuelto de forma rápida un problema que se consideró difícil.
• Si un programa fue rechazado por el jurado, no entres en pánico. Busca el error (ten por seguro que existe uno), considera las limitaciones de tu programa mientras te preguntas a ti mismo bajo que circunstancias esos limites son pasado.
• No envíes un programa a los jueces, que únicamente resuelve los casos que tienen como ejemplo los problemas.
• Trata de que tus programas sean fáciles de entender y leer (para más detalle al respecto ve a la sección 5 “Estilo de programación”)

Por último, trata siempre de mantener la calma y la concentración, tratando de disfrutar y divertirte en estos concursos de programación.

Escoge tu lenguaje de programación

Los lenguajes de programación oficiales para los concursos de programación ACM son C, C++, Java y Pascal, este último generalmente opcional.

• Pascal. Quizás el lenguaje más popular en el mundo educacional. Un lenguaje fácil de aprender y diseñado de tal forma que el programador aprenda buenos hábitos hacia la programación estructurada, sin embargo sus programas resultan en códigos muy largos debido su propia estructura y la principal razón para no fijarse mucho en este lenguaje es que muchos concursos de programación no soportan este lenguaje de programación.
• C. También conocido como ANSI C, un compiladorcuya principal ventaja es el manejo de apuntadores, casting, rapidez, extrema flexibilidad y muchas formas de abreviar código.
• C++. Una versión orientada a objetos de C, incluye muchas librerías muy útiles como son las pilas, colas, etcétera, además que ofrece una mejor flexibilidad en el área de la declaración de variables.
• Java. El lenguaje de programación de moda, ofrece todo lo que los demás compiladores ofrecen y muchas cosas más, se puede decir que lo tiene todo, sin embargo debido a su naturaleza que requiere de una máquina virtual para la ejecución de sus programas, es extremadamente lento. No recomendable para muchos problemas donde se requiere velocidad. Es muy eficaz en el proceso de depuración debido al manejo de excepciones que tiene integrado.

No importa que lenguaje de programación elijas, recuerda que el compilador no resuelve el problema, tú eres en realidad quien lo hace.

Debido a que la estructura de los códigos en C, C++ o Java son muy similares, aprender uno casi implica que has aprendido los demás. Sin embargo para obtener practicas sanas de programación, es recomendable que iniciescon C, continúes con C++ y termines en Java. Al final, las circunstancias del problema definirán cual sería el compilador más adecuado para codificar el programa que lo resuelve.

Estilo de programación

Muy pronto estará esta sección.

Entrada y salida estándar o de archivo

Muy pronto estará esta sección.

Programación ACM

Las páginas más populares donde puedes encontrar problemas que se presentan en este tipo de concurso son:

• http://acm.uva.es/problemset, contiene una colección de problemas de concurso de programación ACM que se han realizado en línea a través de esta página.
• http://acm.uva.es/archive/nuevoportal/, contiene una colección semicompleta de todos los problemas de concursos regionales pasados que se realizaron en todas las diferentes regiones del mundo (entre ella México-Centroamérica, donde México pertenece).

Las dos anterior tienen un jurado automático a quien le puedes enviar tus códigos, y te responderá si está bien o está mal. En la sección de problemas tu podrás encontrar una colección de problemas resueltos que puedes tomarlo como referencia para tu beneficio.