Translate

lunes, 8 de agosto de 2011

Olimpiada de Informatica Parte I



Me he retirado un poco de la algoritmia, no soy una persona experta pero eh aprendido algunos trucos al pasar de los años. Una de las cosas que me gusta de la programación es que aprendes muchas cosas nuevas e interesante, y una de las cosas que me a faltado hacer es dejar este pequeño conocimiento adquirido a las nuevas generaciones, que van a superarnos a nuestra generación, este blog lo creé hace tiempo para poder transmitir mi conocimiento pero como han notado no eh logrado ni hacer mas que un par de post y de los cuales ni uno me gusta, por ello ahora voy a tratar de retomar esta costumbre, espero les sirva de algo y mas aun a los que inician en esto de la algoritmia espero no les parezca muy aburrido mi redacción.





Vamos a iniciar con cosas que se de oído y luego vamos a meternos mas a fondo en cada uno de los siguientes concursos. Primero a mi me gusta los concursos de ACM universitarios, pero iniciemos primero por las Olimpiadas de Conocimiento, la OMI en particular.


¿Que es la OMI?



La OMI es la Olimpiada Mexicana de Informática, iniciaré escribiendo como conocí la OMI, la OMI yo la conocí gracias a mi hermano, que concursaba en otra olimpiada (Olimpiada de química), el fue el que me comento sobre este concurso ya que vio en mi una curiosidad mas allá del simple estudio de mis materias. Mi primer acercamiento fue un poco extraño, por que en ese entonces el conocimiento que se tenía en mi estado sobre ella era realmente vago, en los entrenamientos estatales nos enseñaron bastante teoría de grafos, aun que nunca aplicada, y los ejercicios fueron de ordenación, y de representación de grafos. Cuando llegue al nacional y me tocaron ver los problemas reales de esta competencia me di cuenta que mi nivel no era el suficiente y como solo pude ir esa ocasión me quede un poco frustrado por que ya no volvería a concursas en este tipo de concursos (Bueno o eso pensé) .
< Las características de los problemas de la OMI son los siguientes:


Los problemas tienen que estar pensados para que los estudiantes con conocimientos básicos de ciclos, recursividad, matrices y cadenas puedan resolver el problema, la idea del concurso es premiar la creatividad de encontrar la mejor solución, y aun que el concursante no encuentre la mejor solución la forma de evaluar los problemas permiten diferenciar a los concursantes que estuvieron cerca de encontrar esta solución de aquellos que no lo estuvieron.

¿Cómo logran esto?



Esto lo logran calificando con casos de prueba, crean 10, o 20, o 100 casos de prueba, a cada caso de prueba le asignan un puntaje, regularmente una tercera parte de los casos de prueba son por lo regular casos pequeños y que son simple de ver, la siguiente tercera parte son casos de tamaño moderado y empiezan a poner los casos de truco (Estos casos por la definición del problema solo se observan si el concursante esta atento a todo lo que puede afectar a la solución), los casos restantes son casos grandes, para medir la velocidad del algoritmo, y a veces también adicionan casos de truco en esta parte.

La velocidad que esperan que corran los programas varia dependiendo del problema, pero por lo regular son 10 segundos. En estos diez segundos tu algoritmo debe leer el archivo de entrada, realizar todos los cálculos y escribir la solución.
Hay varias formas de atacar los problemas, y eso depende de la habilidad de cada uno de los concursantes y como si soporta la presión de estar en un concurso en vivo enfrentándose a los mejores de su estado o si es el nacional, a los mejores del país.
Lo poco que les puede decir del como atacar los problemas es lo siguiente, Lean el problema, compréndanlo completamente por que es común programar cosas que no se te están pidiendo (Creo que ya me queme). Ya que el problema esta bien definido, y se conocen las cotas superiores e inferiores de los datos de entrada, uno ya puede saber si conoce las técnicas suficientes para resolverlo o no, si uno ya conoce la forma de cómo resolverlo entonces “láncese sobre la presa!!” esto esperarían que dijera no???, pues bueno si lo que se te ocurrió es fácil de programar y estas completamente seguro que resuelve el problema, adelante, a programar, pero si no, si el código que se te ocurre es muy complicado ó largo, mejor piensa un rato mas, por que hay formas de optimizar el código.

¿Optimizar el código?



Si, optimizar el código, también una parte importante de estos concurso es optimizar no solo el tiempo de ejecución si no también el tiempo de codificación, y aun mas importante es optimizar el tiempo de debugeo, es bien sabido que el tiempo de debugeo es el tiempo mas largo en los concursos de programación. Como optimizar código, esto se puede realizar practicando antes de las competencias, pero una practica constructiva, no solo resolver problemas por resolverlos, si no también después de resolverlos pensar si existe una manera mejor de codificar el mismo algoritmos, también uno puede ver códigos de otros competidores , por ejemplo en www.topcoder.com/tc o en www.codeforces.com. Como optimizar el tiempo de debugeo, pues bien esta es la tarea que se necesita practicar más, les contare como veía las cosas yo antes:

Pues cuando era joven y tenia ilusiones veía mis códigos y decía que chingones estaban, veía mis variables a = 2; b = a * z * aaa; printf(“El tamaño de la pirámide es %d”, a + aaa*b); , después de un mes de ver el mismo código pensaba que estaba bien chido, pero no sabia que resolvía ni como se me había ocurrido la solución , y lo mas importante que &$|@##@|@# significaba la variable aaa. Bueno creo que después de este ejemplo solo les puede decir que las variables pónganle un nombre que tenga que ver con su significado, aun que sea muy grande (No exageren) no importa, ya que el tiempo que pierdan escribiendo la variable mas grandes ( 5 min, 10 min) lo ganaran en tiempo de debugeo ( 30 min, 1 hora).

Vamos a ir parte por parte en este blog, en los siguientes blogs espero ver a detalle algunos problemas nacionales, y como atacarlos.

Si no les gusta el blog háganmelo saber, para mejorarlo, si me falto cosas en este blog también seria bueno que me lo dijeran y así publicarlas después en otro blog. Y pues solo les puede decir que primero programo y luego existo.

Saludos que tengan un buen inicio de semana.


2 comentarios:

Lesthack dijo...

Muy bien, seguiré al pendiente de los post's consecuentes, a mi también me gusta mucho programar aunque no participe en muchos concursos pero adoro la optimización.

-- dijo...

Qué bien que vuelves a escribir, y felicidades por tu bonita familia.

Wen