Solucionario Regional Latinoamérica 2016

Pese a algunos percances con el problema E, podemos decir que la prueba fue entretenida y satisfactoria. Solamente un equipo logró resolver todos los problemas (nuestras felicitaciones al equipo de Cuba). Mariano y yo (Martín) colaboramos en la sede de Buenos Aires durante la competencia, mientras que Pablo tomó el rol de coach de los equipos de nuestra universidad (Universidad Nacional de Rosario).

Caloventor, junto a los equipos de la UNR que participaron en el Regional


Links Útiles



Soluciones

Aquí les dejamos el solucionario, el cual es una traducción mas o menos fiel del realizado por FFAO (Fernando Fonseca) en su blog: https://algorithmmarch.wordpress.com/2016/11/15/final-brasileira-da-maratona-2016/. Incluimos una solución detallada del problema E que aunque no fue parte de la prueba oficial, nos parece un problema muy interesante.

A



B



C



D



E



F



G



H



I



J



K



16 comentarios:

  1. Pueden compartir los enunciados? gracias.

    ResponderBorrar
  2. Respuestas
    1. No tenemos a mano los códigos. Por otro lado, es preferible que hagas tus propios códigos una vez que entiendas la solución. Si se usa alguna estructura o técnica específica (como en el E o el K) que tiene un código complicado podes buscar material sobre eso en Internet. Pero en este contest la dificultad no estuvo tanto en la complejidad de los códigos, por lo que es mucho mejor hacer una solución propia desde cero para afianzar el entendimiento de la idea, así cuando tengas que hacer un problema sin ayuda ya estés acostumbrado. Esto es especialmente cierto para los greedies, cuya implementación suele ser muy fácil en relación a la idea detrás de él. Aprender mirando códigos de soluciones no suele ser tan bueno como parece (salvo que se quiera aprender macros o "truquitos" del lenguaje, en tal caso podes mirar códigos del top 100 de codeforces.com).

      Por si acaso dejo el notebook de nuestro equipo (que tiene implementaciones de los algoritmos usados en ICPC): https://github.com/mvpossum/eldiego .

      Borrar
  3. Gracias gente. Sus solucionarios son siempre muy útiles.
    Esta bueno saber que al menos hay dos problemas que con mi equipo los estabamos encarando bien.

    ResponderBorrar
  4. ¿Estan seguros que la I pasa en O(n^2 logn)? Durante el contest intentamos varias veces y nos daba TLE. 6000*6000*log(6000) es mucho.

    ResponderBorrar
    Respuestas
    1. Muchos equipos lo resolvieron así. Hay un pequeño detalle en la implementación del divide & conquer que puede emporar el tiempo. De hecho si buscás tutoriales algunos cometen ese error (que solamente se aprecia cuando hay un tiempo estricto). Vamos a intentar hacer un tutorial de ese algoritmo en un futuro.

      Borrar
    2. Hola, ¿podrías darnos una corta explicación sobre cuál es ese detalle? Pues no hemos podido encontrar ninguna mención sobre esto en internet.

      Borrar
  5. solo un comentario sobre el problema A, no es necesario calcular todas las combinaciones basta con (max + min) - (los del medio) y retornar el valor absoluto, incluso los entregan en orden
    Saludos

    ResponderBorrar
  6. Hola, no me queda claro el greedy de la B. Como demuestro que el nodo de mayor grado, cuyo grado es > N - B, no será parte de alguna solución optima luego que todos cumplen con grado >= A. El método descrito me va llevar a una solución óptima, pero podría haber otras. Y en alguna de ellas podría estar dicho nodo que tu algoritmo descarta. Lo que usualmente se hace es demostrar que quitando este podría de todos modos alcanzar la solución óptima, pero es algo que no me la termino de creer.

    ResponderBorrar
    Respuestas
    1. No, el nodo que se quita NUNCA podría formar parte de una solución. Si v tiene grado > N-B significa que es incompatible con menos de B nodos, lo cual contradice lo condición del enunciado. Ahora porqué es óptimo sacarlo? Ponele que lo dejo, entonces tendría que arreglar la solución para que el nodo v cumpla con la condicion. Pero lo único que puedo hacer es quitar nodos, y si lo hago lo único que puede pasar es que el nodo v sea incompatible con AÚN menos nodos, osea la condición de que tiene que tener por lo menos B incompatibles nunca se va a cumplir.

      Borrar
  7. hola no me queda claro como modificar el kmp de el ejercicio G

    ResponderBorrar
  8. Hola Martin, si llegaron a hacer el tutorial de divide & conquer en dp??
    Si es así, podrían pasar el link, muchas gracias

    ResponderBorrar
  9. Buenas tardes, estuve leyendo el solucionario y me sirvió mucho. El K no me termina de quedar claro cómo armar el grafo donde se calcula el flujo máximo.

    saludos

    ResponderBorrar
  10. Este comentario ha sido eliminado por el autor.

    ResponderBorrar