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



14 comentarios:

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:

Introducción de cero a la programación competitiva

Escribo esta entrada porque varios me han pedido consejo de por dónde empezar a introducirse a la programación competitiva.


Voy a suponer que tienen conocimientos de programación básicos. Quizás más adelante agregue alguna referencia de dónde pueden aprender a programar pero creo que hay muchísimo más material de esto que de programación competitiva en sí.

Recomiendo seguir los siguientes tres puntos para empezar de 0. No están hechos para hacerse en orden sino a la par. Esto puede llevar tiempo, así que a no desmotivarse. Más abajo listo material útil. Y por último doy algunos tips que se me fueron ocurriendo a medida que escribía esto.

Introduciéndose:

        1. Si nunca submiteaste un problema, create una cuenta en USACO (ver link del compilado) y ver la primer seccion para ver como es la dinámica, el formato que tenés que respetar, de como submitear una solución en un juez online.

        2. Ver el libro de Steven Halim. La sección introductoria y de problemas ad hoc es un buen punto de partida. Otro portal por el que se puede empezar es URI que tiene problemas ordenados por dificultad y podemos elegir los más fáciles.

        3. Crearse una cuenta en Codeforces. Podés empezar haciendo problemas A de Div2 (los más fáciles y tratar de hacerlos). Si tu respuesta es incorrecta te permite ver por qué y cómo debería ser la respuesta correcta del programa.

        4. Seguir el libro Halim en secciones posteriores (como Greedy, Programación Dinámica, Grafos) para incorporar conocimientos teóricos nuevos que nos van a permitir resolver un espectro más amplio de problemas. Siempre es importante no quedarnos con los problemas fáciles que se nos ocurren rápidamente ni tratar sólo los tan difíciles que debamos ver siempre la solución, sino ir ampliando de a poco nuestro horizonte y dejar un tiempo razonable el problema en el tintero. Ojo, que también es importante que si no salió el problema, buscar la solución tratar de implementarla por uno mismo y entender por qué no me salió (tal vez algo teórico que no sabía y deba aprender, o quizás alguna manera de enfocarlo distinto), incorporar este nuevo conocimiento y pensar cómo podría ayudarme a resolver otros problemas distintos.

Material útil:

USACO: http://train.usaco.org/usacogate
Es una página de entrenamiento para competencias (IOI) de secundario de los norteamericanos.
Muy amena introducción. Recomendable para hacer la primer sección como introducción a la dinámica de la progrmación competitiva.
Recomiendo seguir la guía si estás entrenando para el secundario pero sino no sugiero hacerlo, creo que hay lugares mejores orientados a la ICPC.
Es motivante el hecho de que necesitás hacer los problemas de una sección para pasar a la siguiente pero a veces traba un poco, en estos casos recomiendo buscar alguna solución en internet y submitearla.

Codeforces: http://codeforces.com/
Es una comunidad muy piola que organiza competencias online periódicamente. También hay algunas guías de temas teóricos desde básicos hasta muy avanzados.
Súper recomiendo crearse una cuenta acá y empezar a ver problemas. Los problemas están clasificados en dos divisiones (Div2, fáciles y Div1 avanzados). Además en las competencias suelen estar ordenados por dificultad creciente.
La página tiene una sección llamada Gym, muy útil para practicar con tu equipo competencias oficiales anteriores ya que simula el scoreboard como si estuvieras compitiendo con las personas que participaron antes.

Training Camp Argentina: https://sites.google.com/site/trainingcampargentina2016/
De los training camps argentinos da para hablar mucho, pero en resúmen es un evento HIPER recomendable (diría que hasta escencial!) para participar. Organizado por gente muy buena onda y copada, con mucho trabajo solidario aporta para que este tema de las competencias se extienda en todo el país.
Siempre decimos que sin ayuda de estos eventos nunca hubiéramos clasificado a nuestra primer mundial. Se hacen en junio generalmente y consiste en un curso donde todos los días tener clases teóricas a la mañana y simulacro de competencia por las tardes. Es muy intensivo pero re vale la pena hacerlo!!
Acá puse la página de la edición 2016 pero si googlean por año, aparecen todos lo anteriores. Tiene slides de teoría que se dio y links a las competencias que se simularon.

Live Archive https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8
Uno de los tantos jueces en línea. Acá tenemos, por ejemplo, los regionales de años anteriores. Aunque particularmente no recomiendo quemarse problemas de estos así pueden simularlos después con sus equipos.

UVa Online Judge: https://uva.onlinejudge.org/
Otro juez en línea. El libro de Halim tiene referencias a problemas que se encuentran acá.

Competitive Programing (Libro de Halim)
https://sites.google.com/site/stevenhalim/
Este libro lo compramos nosotros. No se comercializa acá y hay que esperar algunos meses a que llegue acá en Argentina, pueden intentar buscar alguna versión por Internet.
Yo creo que está bueno para empezar, de hecho nosotros empezamos por acá y le debemos mucho mucho a Steven Halim. Tuvimos la oportunidad de agradecerle personalmente y sacarnos una foto con él! (siempre asiste como invitado a las finales)
Está bueno que presenta un panorama general de las categorías de problemas existentes y cada sección tiene un desarrollo que llegua a conceptos avanzados, dando código de ejemplo y referencias a problemas de jueces online.
También existe el libro Programming Challenges de Steven Skiena, que tiene un approach un poco menos centrado a las competencias pero más claro en cuánto a las introducciones a los temas.

URI online Judge (https://www.urionlinejudge.com.br/judge/en/login)
Es un juez brasilero. Cada vez más está incorporando y traduciendo problemas al español. Una de las ventajas de URI frente a otros portales es que tiene los problemas clasificados por dificultad.
Ésto esta muy bueno, entre muchas varias otras cosas porque cuando uno empieza no tiene la capacidad de discernir cuando un problema es complicado y no está a su alcance ó cuando simplemente le tiene que dedicar más tiempo. Y está bueno empezar con problemas fáciles, especialmente si uno aprendió a programar hace poco es probable que tenga muchos errores las primeras veces.

e-maxx.ru: http://e-maxx.ru/algo/
Es una página con muchísimo material avanzado en ruso. Los rusos son la vanguardia en esto así que es común ver material en ruso. Yo siempre usé Google para traducir pero quizás Yandex sea mejor.


Tips:
  • Qué es un Juez en Línea? Es un sitio donde hay problemas y puedes submitear código para que checkee si resuelve el problema.

    Es muy importante que a la hora de hacer problemas no sólo los pienses, sino programes y submitees. Es muy común al principio tener errores en los que nuestro programa anda bien en CASI todos los casos pero hay alguno que falla porque no lo contemplamos. De hecho no cometer errores implementando el problema, aún teniendo una idea correcta es una gran parte de la competencia. Por eso creo que es escencial que para mejorar hagan problemas que ESTEN SEGUROS que van a poder submitear el código en algún juez y verificar que sea correcto.
  • Los jueces corrigen MUY ESTRICTAMENTE como van a ver si hacen la primera sección del USACO. Son máquinas, así que una mayúscula en vez de minúscula, un espacio o un salto de línea de más hará que nuestra solución este MAL.
  •   Programar en C++: siempre escoger el lenguaje, dentro de los que permiten las competencias, es una cuestión de gustos. Pueden elegir Java si prefieren. Yo recomeidno C++ por varias razones:
    1. Creo que hay más material en C++ que en Java.
    2. Python creo que fue introducido para incentivar la participación ya que se está enseñando mucho en primeros años. En la ICPC se lo está comenzando a adoptar pero aún tiene varios problemas que genera que NO todos los problemas puedan ser resueltos en python. Esto se debe a que usa los tiempos límite de ejecucción de Java y no tiene tiempos límite propios, puede que muchas veces Python sea más lento y un programa que resuelve satisfactoriamente y en la complejidad requerida el problema y aún así el veredicto sea Time Limit Exceeded .
    3. Por sobre C, C++ tiene la STL con muchas estructuras ya hechas que aporta mucha ventaja (set, map, priority_queue, etc).
  • Considerar ir al training camp es una excelente idea. Si sos alumno de la FCEIA, año a año se ha tratado que los gastos de traslado sean cubiertos con apoyo del departamento de Computación. A veces el evento cuenta con sponsors que cubren gastos de alojamiento.  El respeto y relevancia que la ICPC inspira así como los resultados que hemos logrados han hecho tomar conciencia a los profesores de REPROGRAMAR fechas de examenes. No sólo en Computación sino desde la Escuela de Ciencias Exactas hay una voluntad de hacer prosperar esto. Así que si de algún modo es impedimento para su participación algún compromiso académico, esto se puede llegar a ver y tratar razonablemente.
  •  Rodeate de gente con la que puedas compartir y apoyarte. La idea que surgan talleres, entrenadores y materias optativas sobre Programación Competitiva es para satisfacer la necesidad de estos espacios. En nuestro inicio tuvimos la suerte de formar el equipo y apoyarnos entre nosotros fue muy importante para seguir avanzando.


       

3 comentarios:

Un sueño hecho realidad, somos LATAM Champions!!

Un proyecto que empezó en Febrero de 2014, cuando armamos el equipo con el único objetivo de viajar a Marruecos.

Tras dos años entrenándonos duramente, compartimos muchísimas experiencias con toda la comunidad a la cual le debemos tanto, aprendimos un montón y llegamos acá para disputar el Latam en nuestra última competencia juntos.
Sabíamos lo difícil que era pero también que era posible.

Las 5 horas de competencia pasaron como relámpago. Tuvimos un momento de inspiración en la mitad de competencia y en menos de media hora metimos 3 problemas quedando 2 problemas arriba de los equipos Brasileros con quienes estábamos disputando.


Las dos últimas horas fueron muy duras, llenas de tensión, especulación y nervios. Todo lo que habíamos aprendido nos lo jugábamos en ese momento, ahí se definía todo.
Finalmente terminamos viviendo un sueño. Fue la perfecta culminación del proyecto en conjunto que venimos llevando durante estos dos años.
Proyecto que nos llevó a conocer lugares y personas maravillosas y a ocupar muchos de nuestros ratos libres.

Queríamos agradecer a todos los que nos han acompañado en todo este camino.

con Leo y Nico (escondido)

Primero de todo, agradecer a toda la comunidad de Argentina, que hicieron posible nuestra primera clasificacion. Especialmente a Nico Álvarez y Leopoldo Taravilse, nuestros coaches y precursores de los training camps de Argentina, que nos ayudaron a encaminarnos en nuestro entrenamiento a la primera Regional y siempre estuvieron con nosotros.

Empezamos sin saber mucho por donde empezar y decidimos comprar el libro "Competitive Programming" de Steven y Felix Halim (https://sites.google.com/site/stevenhalim/). Este libro nos sirvió una banda como guía y lo seguimos durante todo nuestro primer año a rajatabla. Es un honor para nosotros habernos encontrado en persona con Steven y haber podido saludarlo en persona durante nuestra última World Final en Tailandia.

con Steven Halim y sus hijos

También a los organizadores del training camp de Campinas, especialmente a Rodolfo Azevedo que le pone muchas energías para que éste se realize y nos invitó estos dos años. Este training tiene un nivel increíble y nos ayudó mucho en nuestras participaciones para los dos mundiales.
Un agradecimiento a todos los entrenadores que allí acudieron, especialmente a Tomasz Idziaszek, por su gran didáctica, a quién le agarramos mucho cariño.

en el Training Camp de Brasil 2015

Por otro lado a toda la comunidad latinoamericana en general, en especial a los organizadores de la Red de Programacion Competitiva, es un placer contar con una comunidad donde prima la buena voluntad, donde más allá de la competitividad siempre hay un ambiente de compañerismo y solidaridad.
También queremos agradecer al Ministerio de Ciencia y Tecnología de la Nación que apoya económicamente esta actividad para que año tras año los equipos de Argentina estemos en la mundial representando a la Argentina, así como a Irene Loiseau, la directora de nuestra región, que genera que todo esto sea posible. Por nuestra parte queremos agradecer a la Universidad Nacional de Rosario por apoyarnos y permitir que sea posible viajar para entrenar a Brasil. Sin ese apoyo nos hubiera sido imposible sortear las dificultades económicas.

También agradecer al departamento de Computación de nuestra facultad. Son los que primero nos apoyaron pagando algunos pasajes a pesar del poco presupuesto que poseen. Especialmente queremos agradecer el eterno apoyo del profesor Dante Zanarini que siempre se movió para darnos una mano, a Exequiel Rivas que organizó por primera vez el TAP en Rosario laburando a pulmón junto a Gabina Bianchi que siempre nos estuvo acompañando con muchísimo entusiasmo. También queremos agradecer el apoyo constante de Ana Casali, la directora de departamento que siempre nos apoyó y nos escuchó.

Por último, a nuestros familiares y amigos que nos han acompañado a lo largo de estos años, aguantando a veces nuestros aburridos monólogos sobre los problemas que hacíamos, je.

con nuestras familias antes de irnos a Brasil

Ojalá nuestra experiencia sirva para dar impulso a futuras generaciones de competidores del interior del País, tenemos intención de publicar alguna guía sobre lo que fuímos haciendo nosotros durante estos años para que los estudiantes nuevos que aparezcan no estén tan perdidos como estuvimos nosotros los primeros meses.

Probablemente nos despedidamos como competidores (quién sabe?), pero esperamos impulsar la participación dentro de nuestra universidad.


Mariano Crosetti
Martín Villagra
Pablo Zimmermann

0 comentarios:

3° competencia de la Red de Programación Competitiva (2016)


Aquí va el solucionario. Recordar que si no conocen algún término o algoritmo mencionado es recomandable que dejen de leer la solución y aprendan sobre ese algoritmo antes de seguir.

Juez Online y Enunciados 

https://acm.javeriana.edu.co/maratones/2016/03/




Soluciones


A. Acronyms



B. Tobby Bones



C. Tobby and Query



D. Standard Deviation



E. Tobby and the LED display



F. Triangular Test II



G. Tobby and the line game



H. Painting the Wall



I. Tobby on Tree



Problem J. Tobby Stones



K. Tobby and Seven



L. Tobby and Prime Sum

11 comentarios: