Problemas de programación dinámica

Posted Mayo 2, 2008 * Comments(0)

Algunos problemas de programación dinámica recomendados por Jesús Federico:

Los anoto aquí para recordarme a mí mismo que los tengo que solucionar. Los problemas tachados son los que ya solucioné.

Concurso de Mictlan: TJU Contest #10

Posted Abril 26, 2008 * Comments(2)

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.

Jimi Hendrix - Little Wing

Posted Noviembre 29, 2007 * Comments(1)

Me gusta mucho esta canción, en especial la versión tocada por Stevie Ray Vaughan.

(Necesitas Macromedia Flash para escucharla).

Las 3 canciones anteriores:

  1. Leo Maslíah - Naranjo en flor
  2. Soda stéreo - Un millón de años luz
  3. The Pixies - Where is my mind?

Ventiladores de techo

Posted Noviembre 25, 2007 * Comments(0)

Farreys.com

Farreys es una empresa que vende “ceiling fans“, o ventiladores de techo. También vende accesorios para estos ventiladores de más de una docena de populares marcas como Casablanca, Ellington, Fanimation, NuTone, Quorum y Westinghouse.

Los visitanates pueden buscar el ventilador que desean comprar organizándolos por marca o por estilo. Tienen un sistema de asistencia en a la hora de personalizar el pedido, para configurar y comprar un ventilador de techo a la medida con las especificaciones exactas y los accesoros adecuados. También tienen un buscador de ventiladores para encontrar fácilmente lo que estamos buscando. Tienen precios bastante variados que oscilan entre menos de 100 y más de 1000 dólares.

Entradas siguientes »