Solucionario TAP 2016

Aquí un solucionario respectivo al contest del Torneo Argentino de Programación (TAP) 2016. El solucionario NO es oficial. (Los enunciados pueden encontrarlos aquí). Los resultados finales de todo el país se encuentran aquí. Este año tuvimos la oportunidad de organizar el TAP en nuestra sede.

Éste es el orden de dificultad (creciente) de los problemas que pensé aún antes del TAP (fui problemsetter!):


Pienso que en general ha sido una muy bella prueba con problemas muy divertidos y creo que podría hablar por todos los problemsetters si digo que todo salió bastante bien.

Los equipos compitiendo en la sede de Rosario

A continuación el solucionario, que hicimos junto a Martín.

Problema A



Problema B



Problema C



Problema D



Problema E



Problema F



Problema G



Problema H



Problema I



Problema J



Problema K



Problema L

12 comentarios:

  1. Gracias genio. Te hago dos consultas, el L como era? y el B no termine de entender la parte de la funcion (i,j,flag) y como se podria prescindir de esa ultima variable. Saludos

    ResponderEliminar
    Respuestas
    1. Ahí agregué la solución del L. Para el B, el isomorfismo entre los estados sería:

      (i,j) --> (j,i,0) si j pertenece a A
      (i,j) --> (i,j,1) si j pertenece a B

      Ver si un índice pertenece a A o B es O(1).

      Eliminar
  2. Hola, ¿alguien conoce casos de borde para el problema D (dibujando triángulos)? Mi solución sigue la misma idea que la explicación (llegué a la misma solución de forma independiente), los 4 casos de prueba + todo los ejemplos que yo me hecho me salen todos bien. Aquí está mi código: https://github.com/PabloMessina/Competitive-Programming-Material/blob/master/Solved%20problems/Red%20de%20Programaci%C3%B3n%20Competitiva/2016-Competencia-12/D_DibujandoTriangulos.cpp
    Muchas gracias
    Saludos

    ResponderEliminar
    Respuestas
    1. Update: accepted, en vez de usar intersección entre círculos usé trigonometría, y en vez de usar el método de newton para sacar raíz cuadrada entera usé sqrt() con redondeo.

      Eliminar
  3. Gracias por las explicaciones :) Una consulta para el I. Seguros que es Prim y no Dijkstra lo que hay que hacer? tiene más sentido encontrar la distancia mínima desde la rana 1 hacia todas las demás, que hacer un árbol de cobertura.

    Saludos!

    ResponderEliminar
    Respuestas
    1. Antes que nada quiero volver a recalcar que el algoritmo no es exactamente Prim por lo ya explicado. Tal vez la palabra simulación sea más acertada.

      Respuesta corta:
      Si te resulta más fácil pensarlo como Dijkstra, hacelo así y va a andar si lo hacés bien, pero no es exactamente un Dijkstra.

      Respuesta larga:
      Un primer detalle es que en el solucionario los pesos de las aristas (es decir los tiempos de encuentro) son absolutos, es decir cuantos segundos pasaron desde el tiempo t=0. Por otro lado en una solución pensada con Dijkstra los tiempos son relativos al tiempo de encuentro de uno de los extremos (de esta forma la distancia es la suma de las aristas del camino).

      Dicho de otra forma el peso de las aristas dependen de la distancia que tienen sus extremos (desde la rana 1). En el Dijkstra estamos calculando las distancias, por lo que, a medida que hacemos el Dijkstra, se van a ir agregando/cambiando aristas al grafo (al menos imaginariamente).
      Podes verlo como que al grafo lo vas "construyendo" a medida que hacés el Dijkstra, en ese caso sí, es Dijkstra, pero medio raro. En cambio si lo vemos como Prim, el grafo ya está fijo de antemano y sólo lo exploramos inteligentemente. Por esta razón se optó Prim para explicar la simulación.

      Eliminar
  4. Van a subir un solucionario de la Regional?
    Van a seguir subiendo solucionarios?

    ResponderEliminar
    Respuestas
    1. Recién subí el solucionario! Ya lo venía preparando de hace unos días. Vamos a intentar seguir subiendo, en la medida que nos de el tiempo.

      Saludos

      Eliminar
  5. What's the expected complexity for I (Insect invasion)? I don't know what to do to improve my solution. It is O(R log R + R^2 * K * log N).

    ResponderEliminar
    Respuestas
    1. Hello. Your log N comes from doing gcd right? I believe the expected complexity can be reduced to O(R^2 * (log N + K)), by calculating the required inverse to solve the equation just once for all K.

      Eliminar
    2. You're right, it worked! Thanks a lot.

      Eliminar
  6. Hay algún juez online donde estén los problemas?

    ResponderEliminar