11° competencia de Red de Programación Competitiva (2015)


Esta competencia nos resultó entretenida. Los problemas eran muy lindos!

scoreboard en la posmaratón de la competencia


Link a los problemas

https://drive.google.com/file/d/0ByI9GfoY63_aVlJmbmNPdGJHYWM/view?usp=sharing

Juez modo posmaratón

https://acm.javeriana.edu.co/maratones/2015/11/

Soluciones


A: Alcoholic Pilots



B: Bargaining



C: Cuban Challenge



D: Drinking Game



E: Exquisite Strings



F: File Transmission



G: Greedy Artisan



H: Heavy Luggage



I: Incredulous Ed



J: Jair vs Chadan



K: Keypad Problem



6 comentarios:

  1. hola amigo, para cuando tendrían las soluciones?

    ResponderBorrar
    Respuestas
    1. Están ahí... El próximamente es para el link a las soluciones

      Borrar
  2. Hola!, parece que no estan sirviendo los botones de "mostrar solucion"

    ResponderBorrar
  3. Hola! Perdón por no esperar a su post de la 13º competencia de la RPC para preguntarles lo siguiente:
    Cómo hicieron el problema E. Safe Passage? Yo traté de hacer DP sobre los subconjuntos de {1,...,n}, pero me da TLE. Encontraron una solución mas rápida, o fue una optimización del DP?

    Saludos!

    ResponderBorrar
    Respuestas
    1. Con una DP debería andar fijate si no tenés algún bug o algún ciclo en la dinámica. Este problema aunque suene raro se puede hacer con un greedy en O(n). La idea es que los rápidos me los guardo para el final (así llevo los rápidos con los lentos y vuelve el rápido). En cada paso sólo puedo llevar el más pesado o los dos más pesados (pues el puente lo cruzan a lo sumo dos)
      Entonces en cada paso puedo elegir o bien llevar el más pesado y el más lento. O bien llevo los dos más rápidos, vuelve el segundo más rápido, después llevo los dos más pesados y vuelve el más rápido.
      Si ordenamos el input, la respuesta al problema vendría a ser algo así: http://pastebin.com/3FwFqLnA
      Él porqué funciona queda como ejercicio :P . Desgraciadamente no podemos hacer solucionarios de todas las pruebas que hacemos por falta de tiempo.

      Borrar