Solucionario TAP 2017

Una vez más otra exitosa instancia de esta competencia realizada alrededor de toda Argentina fue llevada a cabo. En esta ocasión Pablo Zimmermann colaboró junto con muchas otras personas en la elaboración de los problemas y a su vez fue coordinador de la sede de Rosario, la cual fue técnicamente posible gracias a Martín Villagra. Como siempre dejamos una foto de nuestra sede (en la que no nos acompañó Mariano por no estar en Rosario) y soluciones a los problemas.



Links útiles



Solucionario

A



B



C



D



E



F



G



H



I



J



K



L



2 comentarios:

  1. Interesante! Mi solución del problema J (en posmaratón lamentablemente) es un poco distinta.

    Primero construyo dos conjuntos, los posibles "primeros nombres" y los posibles "segundos nombres". Evidentemente, si en la lista dada hay mas de 2*m nombres, no es posible.
    Los primeros nombres están en el primer contest, luego creo un grafo bipartito completo entre "primer" y "segundo", ya que al principio cualquier nombre es posible.
    Por cada contest voy eliminando aristas del grafo que estén en conjuntos distintos, es decir si hay un "primer nombre" A y un "segundo nombre" B en la lista, elimino la arista de A a B. Luego lanzo un bipartite matching y si es perfecto, es posible.

    Un pequeño overkill por lo que veo, pero sirve! jejeje

    ResponderBorrar
    Respuestas
    1. Tu idea esta perfecta, hay una de las soluciones oficiales que usa eso y hubo una discusión si eso debía entrar o no. Por las cotas que le pusimos al problema, casi cualquier cosa entra en tiempo así que está bárbaro. :)

      A mi ni se me ocurrió, cuando pensé el problema me vino rápido a la mente la otra y pensé que iba a ser uno de los más fáciles (3ero-5to ponele). Fue mi sorpresa del contest.
      Salut!

      Borrar