Archive for the 'programación' Category

Concurso de Mictlan: TJU Contest #10

Posted Abril 26, 2008 * Comments(3)

Publico mis soluciones a los problemas del pasado concursito en el sitio de la Universidad Tecnológica de la Mixteca - Mictlan: TJU Contest #10, en el orden en que los resolví. En general me gustó el torneo, los problemas estuvieron variados y bien escogidos. Lástima que al final se cayó el servidor y no pude terminar el problema que me quedó faltando.

  • El primer problema que resolví fue el 2772 - Parallelogram. Consiste en determinar si 4 puntos dados podrían ser las esquinas de un paralelogramo. Utilicé la ecuación canónica LaTeX - ax + by + c = 0 de una recta para resolverlo.
    Este es el código: 2772.cpp
  • Después hice 2189 - The key stations: Hallar los puntos de articulación de un grafo no dirigido. Hay un problema casi idéntico en el sitio de la Universidad de Valladolid. Ya lo había hecho, así que conocía el algoritmo y reciclé código. El algoritmo está en el libro “Introduction to Algorithms” de Thomas Cormen y otros.

    No me gustó el formato de entrada de este problema. Me dio Accepted al segundo intento, por un estúpido Presentation Error.
    Este es el código: 2189.cpp

  • 2028 - Excuses, excuses!. Un problema ad-hoc de strings. Utilicé un mapa para el diccionario y un stringstream para dividir una frase en palabras.
    Otro Presentation error más estúpido todavía me dio otros 20 minutos de penalización.
    El código: 2028.cpp
  • Finalmente resolví 1058 - Lifting the stones. Para mi gusto el mejor problema del set. Se resume así: Dado un polígono simple (es decir, que no se intersecta a sí mismo) que representa una lámina de densidad superficial constante, encontrar las coordenadas del centro de masa de la lámina.

    Resolví este problema aplicando el Teorema de Green, que relaciona la integral doble de una región con la integral de línea de la curva que la encierra. En otras palabras:

    LaTeX - \int_{C} \vec{F} \cdot \, d\vec{r} = \iint_{R} \left( \frac{\partial Q}{\partial x} - \frac{\partial P}{\partial y} \right) \, dA donde LaTeX - \vec{F} es un campo vectorial de la forma LaTeX - \vec{F} = < P(x,y) , Q(x, y) > .

    Ahora bien, la coordenada LaTeX - X centro de masa de una lámina plana está dada por:

    LaTeX - \bar{C}_{x} = \frac{ \iint_{R} \rho \, x \, dA }{M} donde LaTeX - \rho es la función de densidad (en este problema una constante que podemos considerar LaTeX - \rho = 1 ) y LaTeX - M es la masa neta de la lámina.

    Similarmente, la coordenada LaTeX - Y es:
    LaTeX - \bar{C}_{y} = \frac{ \iint_{R} \rho \, y \, dA }{M} .

    La parte crítica del problema es ver que las integrales dobles que aparecen en los denominadores se pueden expresar como una integral de línea, y esta se puede evaluar conociendo los puntos del polígono porque un polígono simple es una curva cerrada suave a trozos donde cada trozo es una recta.

    Sea LaTeX - \vec{F} un campo vectorial con la forma LaTeX - \vec{F} = < P(x,y) , Q(x,y) > = < 0, \frac{x^2}{2} >

    Derivando parcialmente obtenemos que:
    LaTeX - \frac{\partial Q}{\partial x} - \frac{\partial P}{\partial y} = x

    Que es justamente la función que queremos integrar.

    Aplicando el Teorema de Green llegamos a que:
    LaTeX - \iint_{R} x \, dA = \iint_{R} \left( \frac{\partial Q}{\partial x} - \frac{\partial P}{\partial y} \right) \, dA

    LaTeX - = \int_{C} \vec{F} \cdot \, d\vec{r} = \int_{C} P \, dx + Q \, dy

    pero como el polígono es una curva suave a trozos podemos expresar esta última integral como la suma de una integral por tramo:

    LaTeX - = \int_{C_1} P \, dx + Q \, dy +\, \cdots \, + \int_{C_n} P \, dx + Q \, dy

    LaTeX - = \sum_{i=1}^{n} \int_{C_i} P \, dx + Q \, dy

    Ahora sólo hace falta parametrizar la curva LaTeX - C_{i} para evaluar esta integral de línea.
    Dado que LaTeX - C_i es una recta que va de los puntos LaTeX - (x_{i}, y_{i}) a LaTeX - (x_{i+1}, y_{i+1}) la parametrizamos con la función vectorial LaTeX - \vec{r} = < t , \, m (x - x_i) + y_i > donde el parámetro LaTeX - x_{i} \leq t \leq x_{i+1} La primera coordenada de esta función es lo que hemos llamado LaTeX - x y la segunda es lo que hemos llamado LaTeX - y , y LaTeX - m es la pendiente de la recta LaTeX - C_i . Derivando estás funciones vemos que LaTeX - dx = dt y LaTeX - dy = m \, dt .

    Entonces nuestra integral de línea en cuestión queda

    LaTeX - \int_{C_i} P \, dx + Q \, dy = \int_{x_i}^{x_{i+1}} 0 \, dt + \frac{x^2}{2} m \, dt

    LaTeX - = \int_{x_i}^{x_{i+1}} \frac{x^2}{2} m \, dt

    Una integral fácil de evaluar cuyo resultado es

    LaTeX - = \frac{1}{6} m\, \left( x_{i+1}^3 - x_{i}^3 \right)

    Teniendo en cuenta que LaTeX - m = \frac{y_{i+1} - y_i}{x_{i+1} - x_{i}} y aplicando un poco de álgebra, vamos a llegar por fin a la solución:

    LaTeX - \bar{C}_{x} = \frac{ \iint_{R} x \, dA }{M} = \frac{1}{6M} \sum_{i=1}^{n} (y_{i+1} - y_{i}) (x_{i+1}^2 + x_{i+1} x_{i} + x_{i}^2)

    Para la coordenada LaTeX - Y es un proceso casi idéntico, pero me da mucha pereza escribirlo acá.
    La respuesta es:

    LaTeX - \bar{C}_{y} = \frac{ \iint_{R} y \, dA }{M} = \frac{1}{6M} \sum_{i=1}^{n} (x_{i} - x_{i+1}) (y_{i+1}^2 + y_{i+1} y_{i} + y_{i}^2)

    Sólo faltan dos detalles para poder codificar una solución aceptada por el juez: Para efectos de este problema, la masa es directamente proporcional al área del polígono. El área se encuentra con el algoritmo explicado en el libro Programming Challenges de Miguel Revilla. El otro detalle es que el teorema de Green nos exige que la curva cerrada esté orientada en sentido antihorario, así que si el polígono original está en sentido horario hay que reversarlo antes de correrle este algoritmo.

    Tengo que decir que gran parte de esto salió de la cabezota de Arcila.

    De cualquier modo, aquí está el código: 1058.cpp

    Ahh por cierto, pudieron ahorrarse el trabajo de leer toda esta vomitadera matemática leyendo esto (Tal vez debí poner este anuncio arriba).

Nota del autor: Buah, acabo de leer todo lo anterior y me parece sumamente aburrido. Necesito bailar un rato.

DOMjudge: Un sistema para hacer torneos de programación

Posted Abril 16, 2008 * Comments(0)

DOMjudge es un un sistema para montar torneos de programación bastante parecido al más comúnmente usado PC^2.

Algunas ventajas sobre PC^2:

  • Genera scoreboards más bonitos (por ejemplo este)
  • Interfaz web; sólo hay que instalar el programa en el servidor.

Algoritmo para encontrar un camino de Euler en un grafo no muy complicado

Posted Septiembre 25, 2007 * Comments(3)

En una entrada anterior prometí publicar la solución al problema 291 - The House of Santa Claus. Aquí está:

El problema

Teniendo el siguiente grafo, el problema consiste en encontrar todos los caminos posibles en que se pueden recorrer todas las aristas del grafo una única vez, partiendo de la esquina inferior izquierda. Esto en matemática de grafos es conocido cómo un camino de Euler.

 El grafo

Cada nodo está numerado como se muestra en la figura y cada arista es bidireccional, es decir, se puede ir del nodo 1 al 5 si y sólo si se puede ir del nodo 5 al 1.

The House of Santa Claus - Graph

 La solución

El algoritmo que se me ocurrió para solucionar el problema fue crear una función recursiva que se llamara cada vez que se visite un nodo, y que a su vez vuelva a llamarse con los próximos nodos a visitar, usando cómo parámetro la lista de los nodos ya visitados en el orden de visita. Me explico: la primera vez la función se llamará con los nodos visitados, es decir, [1], y se llamará a ella misma para cada nodo que sea posible visitar a partir del nodo actual. En nuestro caso, la llamada anterior llamará a la misma función 3 veces: una para cada posible siguiente nodo, a saber, se llamará nuevamente con los parámetros [12], [13], [15]. Puede verse que si se tiene la lista de nodos visitados en el orden de visita, se sabrá que aristas ya han sido visitadadas. Por ejemplo, para saber si ya se visitó la arista que conecta los nodos 4 y 5, bastará con fijarse si en la lista están dichos números en posiciones adyacentes. De esta manera, la llamada recursiva de la función sólo se generará sobre los nodos destino a los que sea posible visitar (o sea que no se repita arista). La recursividad se detendrá o bien cuando no es posible moverse a otro nodo sin repetir arista o bien cuando se han recorrido 8 aristas.

La implementación

Mi solución está escrita en C++.

Read more »

Nos vamos para la maratón nacional de programación

Posted Septiembre 22, 2007 * Comments(3)

Hoy sábado fue la eliminatoria en mi universidad para escoger a los tres equipos que la representarán en la XXI Maratón Nacional de Programación. Nuestro equipo participó y quedamos en segundo lugar, resolviendo 2 de los 4 problemas planteados en 2 horas 19 minutos.

Los problemas fueron sacados el Archivo de problemas de la Universidad de Valladolid, y los problemas en cuestión fueron:

Los problemas que mi equipo resolvió fueron Chess y Quirksome Squares. La implementación de The House of Santa Claus que hicimos no fue aceptada por el juez :( . Más adelante explicaré la solución a este problema.

Programa en C para resolver sudokus

Posted Septiembre 16, 2007 * Comments(0)

Sudoku Solver es un programa escrito en el lenguaje de programación C que es capaz de resolver cualquiera de estos famosos rompecabezas japoneses y además informa si el reto tiene una única solución. Es asombrosamente rápido, según el autor:

On a 333 MHz Pentium II Linux box it solves typical medium force puzzles in approximately 620 microseconds or about 1,600 puzzles per second, give or take. On an Athlon XP 3000 it solves about 10,800 puzzles per sec.

El algoritmo se ve muy interesante. Definitivamente vale la pena ensayarlo, pues sobra escribir que el código fuente esta disponible. Acá hay una captura sacada de la página oficial que muestra el programa en funcionamiento:

Sudoku Solver en funcionamiento




« Entradas anteriores