Solucionario Regional Latinoamérica 2015

Primero que nada agradecer a los organizadores de la competencia y al departamento de nuestra carrera que nos apoyaron siempre. Después casi dos años entrenando tuvimos un resultado muy gratificante, logramos ser campeones de nuestra región! (Argentina, Perú, Bolivia, Uruguay, Chile y Paraguay). Estamos muy contentos por haber clasificado a las siguientes World Finals, a realizarse en Tailandia. Felicitaciones a todos los equipos que participaron. Esperamos que en los siguientes años otros equipos vivan lo que nosotros vivimos.

Los tres equipos de Rosario: Flower Power, Caloventor en Dos (con nuestro elefante) y [Listas, Turings y Lambdas]

Scoreboard final

http://bombonera.org/board/

Juez Online y Enunciados 

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=702

Nuestra compu al final de la competencia


Soluciones


A - At most twice



B - Blood groups



C - Cake cut



D - D as in Daedalus



E - Exposing corruption



F - Fence the vegetables fail



G - Galactic taxes



H - Height map



I - Identifying tea



J - Just a bit sorted



K - Keep it energized

10 comentarios:

  1. Uno pregunta, para la pregunta E dicen que cuando "cambio" a uno de las primeras aumento uno, pero que pasaria en el caso
    2 2
    10 100
    5 50
    para la superficie entre las dos filas ambas caras miran al sur (hacia abajo) pero son dos caras no?

    ResponderBorrar
    Respuestas
    1. Estás en lo correcto. En tu caso es como que voy al estado sin cara y vuelvo de nuevo al estado, sumando uno. La condición de que empieze una "nueva cara" es un poco más complicada en realidad. Si yo tengo algo así:
      x z
      y w, con x > y
      entonces me mantengo en el estado(es la misma cara) sii se cumple que z > w, w < x, z > y.

      Borrar
  2. Tienen alguna demostracion para saber que la funcion del problema G es unimodal y se puede hacer busqueda ternaria??

    ResponderBorrar
    Respuestas
    1. Probar unimodalidad suele ser complicado. Lo mejor es aprenderlo intuitivamente: en un plano xy, dibujar muchas rectas. Luego para cada x, marcar el punto (x, y) con menor y tal que (x, y) pertenezca a una recta (este es el lower hull). Lo que te queda marcado es una función compuesta por pedazitos de las rectas originales. Ahora intenta buscar algún caso en donde la función marcada no sea unimodal.

      Borrar
    2. Esa funcion que tu describes es claramente unimodal. Ahora lo acabo de entender, podemos ver cada camino como una recta At + B, ya que es la suma de todas la rectas que lo componen, y entonces nos queda una funcion unimodal para t, gracias y SUERTE para la final mundial en el 2016...

      Borrar
  3. Qué lástima! El E lo pensé exactamente igual, solo que no sabía como encarar le problema de la mochila, no te puedo creer. Gracias por todo!!!!!!

    ResponderBorrar
  4. Podrías explicarme un poco más la solución dinámica del A?

    ResponderBorrar
  5. en el problema K mencionan la existencia de otras soluciones, la verdad la unica que yo vi fue esa misma, podrian por favor mencionar otra(s), y exitos en la final mundial.

    ResponderBorrar
  6. Hola, primero que nada felicitaciones por la clasificación al mundial. Para los que me leen, implemente una solución un poco distinta para el F. Mi solución lo único que utiliza es un set, y es parecido a una simulación un poco fastidiosa, pero it works! :D.

    La idea es la siguiente, los segmentos que nos van a interesar del polígono son los segmentos horizontales. Además ordenamos los segmentos por sus y's.

    En el set (que es un set de pares de enteros) se mantienen qué segmentos con respecto X están "activos", es decir, que si pregunto inmediatamente por un punto que este en una coordenada (x',y') y ese x' está dentro de uno de los segmentos activos, entonces se considerará que esta dentro del polígono.

    Fíjense que inicialmente los segmentos activos obviamente son los segmentos que son, por decirlo de una manera "el piso del polígono", y a medida que hacemos un line sweep en el eje y, pueden pasar varias cosas, o dos segmentos activos se unen, o se borrar varios segmentos activos ya que el polígono empieza a cerrarse. Esta idea es mucho mas fácil verla si dibujamos los casos de pruebas.

    Por otro lado, los puntos que se preguntan si están fuera o dentro del polígono también deben ser ordenados por sus y's e ir haciendo en conjunto con los segmentos el line sweep, pues los segmentos activos, están activos hasta cierto y y luego se sigue modificando el set.

    La idea es un poco difícil de explicar pero si tienen algunas dudas y quieren implementar esta idea, no duden en contactarme,

    Saludos :D.

    ResponderBorrar