Olimpiada de Informatica Parte II

Olimpiada de Informática Parte II

Seguiré mencionando los aspectos que considero importante de estos concursos, seguiremos con la olimpiada mexicana de informática (OMI).

Los problemas se dividen prácticamente en los siguientes.

Cadenas: Se requiere un conocimiento de manejo de cadenas, prácticamente son simulaciones en las cuales se utiliza un arreglo.

Recursivos: Se resuelve de manera recursiva, alguna búsqueda en profundidad, crear una función que se llama a si misma para resolverse.

Backtraking: Es similar que las funciones recursivas pero cuando no se encuentra la solución retrocede en la recursión y busca mas alternativas.

Programación dinámica: Los problemas de este tipo se puede también resolver por medio de backtraking, solo que el backtraking exploraría todas las posibilidades, y la programación dinámica guarda estados que se repiten en la recursión, y si ya fue procesado dicho estado, no vuelve a re calcular los valores, ya que una recursión previo ya los calculo. Hay que tener cuidado al guardar los valores, por que si existen ciclos en la recursión el resultado puede ser erróneo.

Grafos: Los grafos son una representación matemática de problemas físicos, como representar ciudades y sus conexiones, o las transformaciones que ocurren a una sustancia especial si se le agregan nuevos elementos.

Geometricos: Los geométricos para el caso especia de la olimpiada deben ser sencillos, solo manejar rectas, coordenadas, y no se requiere un conocimiento muy extenso (Como podría ser realizar unos diagramas de voronoi), pero lo difícil de estos problemas es encontrar algoritmos óptimos que resuelvan casos con mas de 100,000 puntos, o un millón de puntos.

Aquí describo a ojo de buen cubero los tipos de problemas que hay, aun que existen otros que no entran dentro de esta categoría, a esos problemas se les denominan Miselaneos.

Ya les había mencionado que yo participe en la olimpiada del conocimiento que fue en Veracruz 2002, en esta olimpiada el primer día de concurso hubo un fallo en los sistemas y causo que los problemas que se iban a utilizar en el primer día fueran inservibles ya que en el mismo instante que nosotros deberíamos iniciar el concurso nuestros delegados estatales ya estaban viendo los problemas.

Uno de esos problemas eran unas palancas mortales, el problema trataba de lo siguiente: Tenías palancas que deberían ser ejecutadas en un cierto orden, si fallabas perdías el juego, en el problema venia el orden que deberías ejecutarlas a partir de la palanca inicial, por ejemplo si accionas la palanca numero 2 en primer instancia, te decía 3 palancas a la derecha (palanca 5), 5 palancas a la izquierda (palanca 0), etc, etc, estas palancas las podrías ver de una manera circular, ya que si te pasabas del numero de palancas volvías al inicio a seguir contando. Por ultimo te daban el numero de una palanca de color rojo, esta palanca debería ser la ultima en accionarse, y tu tarea era ¿dada la secuencia a seguir, que palanca debería ser la primera en accionarse?. En ese entonces lo primero que se me ocurrió fue realizar las operaciones para cada una de las palancas hasta que la ultima palanca fuera la roja, esto quizás me daría algunos puntos, pero nunca se me ocurrió, hasta después de analizar largo rato y por la ayuda de un compañero de mi delegación, que solo necesitaba hacer la simulación una sola vez para resolver el problemas. (Tu tarea es pensar esta solución en el siguiente post daré la solución).

Con los problemas del día siguiente no tuve mucha suerte, conseguí la honrosa puntuación de 0 puntos. Bueno al menos no fue negativo. En ese día solo había que hacer una simulación y un bactracking, pero en esa época no sabia que era un backtracking y mi simulación creo que la hice mal.

El día siguiente como la mayoría de los competidores saco 0 puntos, se decidió que no fueran 2 problemas si no 6, uno que valiera 100 puntos y 5 que cada uno valiera 20 puntos, de los cuales me fue mejor y saque un total de 100 puntos. Si Atinaron, solo saque los fáciles que eran simulaciones sencillas, no me acuerdo bien de los problemas solo me acuerdo que había uno de un jackpot y otro de unos dados.

Después de esa experiencia que les puede decir, que antes de ir a un concurso investiguen los problemas de los años pasados, si tienen algún conocido que hayan participado en alguno pregúntenle como lo vivió, cual fue su experiencia. Después de perfeccionar sus codificación es recomendable tratar de resolver problemas difíciles, es posible que no los resuelvan pero al intentarlos la experiencia que se aprende de ellos es mucha, por que resolver problemas que ya sabes como resolverlos solo mejora tu habilidad para escribir a computadora y no te deja ideas nuevas para problemas nuevos.

-----

Uno de los problemas que mas me recuerda mis primeros días de programación es el problema de Josephus, este problema te dice que tienes en un cirulo a una cantidad de N personas, numeradas del 1 a N, también te dan un numero K. Tu tarea es simular una eliminación de personas de este circulo, primero empiezas por el 1, 2, 3, ... hasta el elemento numero K, esta persona es eliminada del circulo. Con la persona K + 1 (la persona siguiente que fue eliminada) sigues contando de nuevo desde 1 hasta K, y vuelves a eliminar a esa persona. Como es un círculo cuando te pases de N la siguiente persona deberá ser 1. Nota: No tienes que volver a contar a las personas eliminadas. Tu tarea es determinar ¿Cual es la última persona que queda en el circulo?.
Leemos las dos variables n, k, y utilizando un arreglo podemos representar a las personas que se encuentran en el círculo. El arreglo lo marcamos todas las posiciones como 0 para indicar que sigue en el círculo la persona y 1 para indicar que ya fue eliminado. (Para nuestro algoritmos no tomaremos los valores de 1 a N para las personas si no de 0 a N - 1)


# include
# include

# define ENCIRCULO 0
# define NOCIRCULO 1
# define MAX 1000

int circulo[MAX + 1];


main(){
int n, persona, numpersonas, posicion, k, conteo;
scanf("%d %d", &n, &k);
for(persona = 0; persona < n; persona++)
circulo[ persona ] = ENCIRCULO;


Inicializamos nuestras variables en 0 con excepción de la variable numpersonas esta variable nos indicara cuantas personas aun continúan en el circulo, posición nos indica la posición en la cual estamos contando y conteo nos indica el numero que llevamos, si conteo llega al valor de k entonces esto nos indicaría que la persona que esta en la posición de “posición” tiene que ser eliminada del circulo y ser marcada como 1. ( Hago un pequeño paréntesis para aclarar que como el arreglo es declarado global, en C los arreglos globales por default contienen 0, pero por buena costumbre es recomendable inicializarlo de todos modos)


numpersonas = n;
posicion = conteo = 0;
while( numpersonas > 1 ){
if( circulo[ posicion ] == ENCIRCULO ){
conteo++;
if( conteo == k ){
circulo[ posicion ] = NOCIRCULO;
conteo = 0;
numpersonas--;
}
}
posicion = (posicion + 1) % n;
}



Para los que no están muy acostumbra a los modulos (%) el porcentaje, esta operación da el valor que sobra de la división, en otras palabras el residuo de la división. ¿Para que nos sirve eso? Este pequeño truco nos evita poner un if, por ejemplo si la posición llega a n, el residuo de la división entre n es 0, y si le incrementamos uno seria 1, y asi asta llegar de nuevo a n, y si es n, entonces la división vuelve a ser 0.


for( persona = 0; persona < n; persona++ )
if(circulo[ persona ] == ENCIRCULO ){
printf("La persona finalista es: %d\n", persona + 1);
}
return 0;
}


Al final solo nos resta buscar el único elemento que continua siendo 0. Que pasa cuando N es muy grande, por ejemplo 100,000, bueno esto se les puede dejar de tarea, una solución es utilizando una estructura de datos avanzada para eliminar a la persona con una complejidad de log N. pero esto lo tocaremos después.







No profundizo mas en ciertos problemas ya que hay que ir por partes primero vamos a resolver problemas no tan complicados para subir de tono con el paso del tiempo, hasta llegar a los que nunca me han salido, espero que cuando lleguemos a esa parte ya me hayan salido. Jejej.
Si tienen algún comentario, sugerencia o crítica, no duden en escribirla. Ya que yo ando en aprendizaje en esto de los blogeo y entre mas sea criticado mas rápido aprenderé.
Recuerden que si un león los persigue en la selva, no tienen que ser mas rápido que el león, solamente tienen que ser más rápido que su compañero.



Saludos.