Ayer se realizó otra exitosa instancia del Torneo Argentino de Programación. Debido a la pandemia la competencia fue virtual lo que sin duda representa un cambio de paradigma para los equipos ya que a pesar de estar físicamente separados podían usar tres computadoras y disponían acceso al scoreboard de todas las regiones. La sede de Rosario tuvo 11 equipos, de los cuales cuatro fueron clasificados a la siguiente instancia a realizarse probablemente en marzo. La foto es el podio de nuestra sede durante una pequeña revelación virtual post-contest. Gracias Brian Morris por la organización y felicitaciones a todos los equipos por dejar nuestra sede bien en alto!

Enunciados

Siguiendo el siguiente link: https://drive.google.com/file/d/1zoiepxGBT1QSGHYv8RBrFQyxG-vk-SGl/view

Solucionario

Este año el solucionario lo tenemos gracias al canal de nuestro amigo bonaerense Agustín Santiago Gutiérrez.

No se olviden seguirlo y activar las notificaciones porque está haciendo contenido muy copado si les interesa entrenar en ICPC!

Scoreboards finales

Disponibles temporalmente por aquí: https://placar.naquadah.com.br/boca/Argentina/

Sede Rosario

Toda Argentina

Me dieron muchas ganas de escribir cosas que fuimos pensando, analizando y descubriendo en nuestros dos años como competidores a lo cuál, personalmente, le dediqué mucho tiempo. Todas estas cosas que voy a intentar volcar acá son producto de miles de errores, choques contra una pared y consejos de otras personas (entre las cuáles debo mencionar si o si al genio de Nico Alvarez), pero sobre todo producto de mi fascinación por poder lograr que el Caloventor funcione lo mejor posible.

En este posteo, voy a intentar relatar la World Finals 2016 desde adentro, sobre todo desde mi punto de vista. Creo que es una competencia ejemplificadora ya que nos preparamos mucho para ella y tuvimos casi todos los errores que podíamos llegar a tener. Voy a intentar ser lo más detallista posible, porque nunca encontré una guía detallada que nos ayude, pero seguro me voy a comer varios detalle.

Foto en el Warm Up

En esta competencia, nosotros íbamos a buscar el premio de campeón latinoaméricano, el cuál nosotros creíamos estar disputando (como finalmente pasó) contra las universidades de Pernambuco y Campina Grande. Las decisiones que fuimos tomando fueron en base a ese objetivo, aunque en algún momento pensamos que podíamos llegar a pelear alguna que otra medalla.

00:00
Arranca la competencia. Cada uno tiene su rol inicial bien definido y pensado. Esto es importante, porque al principio los nervios y la ansiedad te comen vivo y cuesta pensar si no estás organizado. Los tres sabíamos en que condiciones estába cada uno, yo en particular no había dormido un carajo y estaba con algo de fiebre pero estaba muy motivado, el Marian estaba hiper-nervioso, y Martín... Martín nunca sabe como está, ja. Pero ambos habían dormido bien que no es poco. Los 3 con muchas pilas ya que nos habíamos motivado 15 minutos antes de que nos íbamos a comer vivo a los Brasileros, je. Esas cosas que uno sueña y la mayoría de veces no pasa.

Nuestra tablita final luego de las 5 horas

Martín arrancó codeando el template, que es un archivo base que copiamos solo una vez al principio para no hacer 10 veces lo mismo (y que sobre todo sirve para menguar los nervios), y a ordenar todas las cosas necesarias en la compu, yo me puse a copiar la tablita (ver imagen) y Mariano a leer desde el A.

Yo soy el que busca el trivial y leo E+. Pegué una ojeada, descarte F,G,H,I y me puse a leer primero el J y como parecía hard volví al E.

Llega el primer solve del C, y lo mandamos a Mariano a pensarlo. En eso Martín me cuenta el L diciendo que parecía de mi onda, lo pienso y me pareció idéntico a un problema que ya había pensado, por lo que me puse a codear algo "esperando a ver si entraba". Mando y metó un TLE completamente ilógico. Releó el código y veo que había cerrado mal una llave, que pajero. Lo arreglo, mando y metemos el L!

Brasil festejando nuestro RTE

Marian tenía el C y entra a codearlo, Tin estaba leyendo el K y yo me pongo a pensar el E. Me pareció que era para el Marian, vuelvo a pensar el J pero no llego a nada, anotó que es Hard y lo dejo. A todo esto el Marian producto de sus nervios iniciales mando un RTE por hacer algo con complejidad exponencial, con la presión de que la gente lo metía.


Resumen (a la 0:30) - (45avos - 5tos LATAM)
A: Math-Bardo.
B: No leído.
C: Codeando/Debugueando (Marian) (40 AC)
D: No leído.
E: Math-a la espera de Marian (3 AC)
F: No leido
G: No leído
H: No leído
I: No leído
J: Pensando (Pablo).
K: Pensando (Tin).
L: AC
M: La idea está pero hay que codearlo y es una paja (Tin)

Por suerte se ordenó, y sumado a que nadie lo molestaba porque no se nos ocurría una puta idea, metió el AC con lo que subimos momentaneamente a la zona de medallas. So, entra el C. Yo me había puesto a leer el D, y Tin el K. Le cuento al Marian el E, y se me ocurre la idea del D. Como la máquina estaba vacía me la iba a poner a codear, pero yo no soy el coder así que le pregunto a Tin si estaba con alguna idea o le contaba el D. Estaba bloqueado con el K, por lo que le cuento la solución del D por arriba pero le digo que se lo ponga a ver él porque no lo había leído completo. A todo esto el Marian me cuenta su idea del E pero era una fruta que en el podía tardar 10^18. Nos lo ponemos a pensar juntos (que es algo que no solemos hacer antes de la primer hora mucho pero dado la presión inicial valió la pena) y se me ocurre una idea pero que había que codear algo del diego que podía llegar a tardar como 20 minutos. El Marian me da el visto bueno y cómo la máquina estaba desocupada, Marian me deja el E y se pone a pensar el G que lo venían metiendo. Yo me pongo a copiar lo que teníamos en el diego (ese nombre le ponemos a los algoritmos que llevamos impresos en papel) hasta que termino y Tin estaba pseudocodeando el D.

Resumen (a la 1:00) - (27avos - LATAM Champions)
A: No leído bien, parece para Pablo.
B: No leído. (1 AC)
C: AC
D: Pseudocodeando (Tin)
E: Codeando el Diego (Pablo) (18 AC)
F: No leido
G: Pensando (Marian) (5 AC)
H: No leído
I: No leído
J: Dejado, Med/Hard.
K: Leído. (2 AC)
L: AC
M: La idea está pero hay que codearlo y es una paja (Tin)

Cuando termino de codear, Tin se pone a codear el D, mientras yo imprimo lo del diego y Marian entra a revisarme el código (cosa clave que otro revise lo del diego, en este caso me arreglo mínimo como 5 errores de tipeo) y yo a pseudocodear la otra parte del E. A todo esto Marian tenía la idea del G, me la cuenta diciendome que es algo que nunca habíamos codeado. Yo le dije que no había apuro porque teníamos dos problemas , y como la máquina de repente estaba a full se pone a pseudocodear la idea en papel. Muchas veces es más rápido escribir en papel que frente a una computadora y es algo que no muchos equipos hacen.  

Estar frente a la compu te pone presión de que tenés que hacer cosas útiles porque la estás ocupando. Nuestro método de laburo era generalmente cooperativo: Siempre que se podía se pseudocodeaba los detalles finos en papel, la máquina solo se usa para codear y si alguien quiere debuguear lo hace en papel salvo que nadie más necesite codear. Meter los problemas rápido siempre fue sólo de prioridad baja. Nuestra regla número 1 siempre fue no dejar la máquina sin uso.

Por mi parte, yo me pongo a codear lo que queda del E, intermitentemente con Tin que iba codeando partes del D (que era de implementación) entonces codeaba un rato cada uno mientras el otro revisaba su código y pseudocodeaba nuevas partes. Esto estuvo bueno porque yo estaba ansioso y desordenado y no podía codear bien mis ideas del E. Las salidas esporádicas me ayudaban a repensar que tenía que ir haciendo. Mariano termina de pseudocodear el G, y como la máquina estaba a full se pone a pensar el K que era el próximo por subs.

Resumen (a la 1:30) - (39avos - LATAM Champions)
A: No leído bien, parece para Pablo. (2 AC)
B: No leído. (4 AC)
C: AC
D: Codeando/Debugueando (Tin) (1 AC)
E: Codeando/Debugueando (Pablo) (45 AC) 
F: No leido
G: Pseudocodeado (Marian) (15 AC)
H: No leído
I: No leído
J: Dejado, Med/Hard.
K: Pensando (Marian). (7 AC)
L: AC
M: La idea está pero hay que codearlo y es una paja (Tin)


Este momento fue clave en la competencia, porque estábamos con 3 ideas y una sola computadora, Martín estaba luchando con el D y yo con el E hacía ya un tiempito. Mi programa ya estaba todo codeado pero yo estaba trabado sinceramente porque no entendía que estaba haciendo (el problema E tenía sus vueltitas en el medio de los nervios de la competencia) entonces salí y lo deje a Martín mientras volvía a repensar todo. Ordené mis ideas, y cuando Martín salió a pensar, cambié una línea y de repente todo dio. Lo mande con mucho miedo ya que había muchos WAs y no confiaba en mi overkill pero dio AC! Gol de media cancha y entró el Marian porque Martín estaba viendo porque no le daban los ejemplos. Mientras tanto yo me puse a leer el A que Marian dijo que parecía Matemático y Martín encuentra un errorcito en el D pero no entra a codear porque el Marian estaba en la compu y se pone a leer el K que era el próximo.

Resumen (a las 2:00) - (39avos - LATAM Champions)
A: Leyendo/Entendiendo (Pablo) (4 AC)
B: No leído. (9 AC)
C: AC
D: A la espera (Tin) (3 AC)
E: AC
F: No leido
G: Codeando (Marian) (26 AC)
H: No leído
I: No leído
J: Dejado, Med/Hard.
K: Pensando (Tin) (16 AC)
L: AC
M: La idea está pero hay que codearlo y es una paja (Tin)

Mientras Mariano codeaba el G, a mi se me ocurre una idea del A pero que necesitaba una mano de los pibes, por lo que me pongo a pseudocodear mi parte (en papel). Mientras analizo el código, me doy cuenta que ni siquiera necesito ayuda de los pibes, porque el problema parecía trivial. A todo esto seguíamos punteros y con 3 ideas así que veníamos bárbaro. Marian se traba con el G y entra el Tin que en 5 minutos arregla el D, manda y otro AC! Festeja Calove y entro yo a pseudocodear mi parte del A alternadamente con el Marian. Martín vuelve a pensar el fatídico K.

Resumen (a las 2:30) - (34avos - LATAM Champions)
A: Codeando (Pablo) (6 AC)
B: No leído. (15 AC)
C: AC
D: AC
E: AC
F: No leido
G: Codeando (Marian) (44 AC)
H: No leído
I: No leído
J: Dejado, Med/Hard.
K: Pensando (Tin). (28 AC)
L: AC
M: La idea está pero hay que codearlo y es una paja (Tin)

Yo termino de codear el A, lo mando y me como un WA completamente desmotivante. Mientras Mariano seguía viendo el G, me llega la impresión (Regla de Oro: Cada vez que se manda un problema se imprime y recién se ve el resultado cuando llega la impresión), releo el enunciado y descubro un detallecito, por lo que vuelvo a entrar, cambio una constante, mando y llega el AC! Alto grito metí acá. Marian también termina de codear y manda y otro AC! Miro a Latinoamérica: Pernambuco y Campina Grande estaban con 4 y después todos 3 para abajo y nosotros teníamos 6. Estábamos 14avos y podíamos llegar a pelear medalla! Estuvimos 2 minutos congelados en un estado de shock hasta que finalmente nos sentamos a analizar.

Caloventor mete el G y queda arriba

El K no salía, me lo cuentan y no era mi onda. Martín se pone a leer el B que era el otro que alguien había metido y el resto de los problemas no tenían ningún AC. El B no lo entendíamos, Marian sigue pensando el K, Martín se lee el I y lo anota como EL HARD y yo el H. Acá la máquina no estaba siendo usada. Terminamos de entender el B y se me ocurre la parte trivial y lo mando a codear a Martín. Esta creo fue una decisión erronea, tendríamos que haber codeado el M que ya lo teníamos pensado y sabíamos como salía. Creo que nos asustó que nadie lo haya metido y me parece que nos apuramos por tener la máquina ocupada en lugar de analizar mejor. Ahí le cuento el problema B al Marian, me dijo que conocía el problema pero que no sabía como se resolvía, malísima noticia. Se nos ocurren una ideas para optimizar y lo dejo porque el me dijo que ya tenía una idea.

Resumen (a las 3:00) - (18avos - LATAM Champions)
A: AC
B: Codeando (Tin), Pensando (Marian). (24 AC)
C: AC
D: AC
E: AC
F: No leido
G: AC
H: Leyendo (Pablo)
I: Dejado, HARD.
J: Dejado, Med/Hard.
K: Leyendo/Pensando (Pablo). (38 AC)
L: AC
M: La idea está pero hay que codearlo y es una paja (Tin).

Mientras los pibes estaban con el B, yo me pongo a ver un panorama general de la prueba, ya que el B y el K no nos estaban saliendo y nadie había metido nada más. Leo el H y se me ocurren unas ideas que le cuento a Tin y definimos dejarlas por ser Geométrico y re bardero. Vuelvo y me pongo a pensar el K desganado (no es el tipo de problema que yo suelo hacer). Pruebo un par de casos y se me ocurre una idea loca y extraña! Los pibes estaban laburando en el B y le cuento mi idea a Tin que no me entiende nada (producto de mi quemadez, estuvimos como 1 o 2 minutos), entonces me enojo y me pongo a codearla yo. Los pibes mientras tanto buscaban como arreglar la segunda parte del B, que tenía que salir porque lo metían toooodos (error). Llega el primer AC del F, pero ya es tarde... No tenía sentido leer ese problema.

Resumen (a las 3:30) - (22avos - LATAM Champions)
A: AC
B: Pensando como codear una parte (Tin y Marian). (28 AC)
C: AC
D: AC
E: AC
F: No leido, dejado. (1 AC)
G: AC
H: Dejado por Geometría HARD
I: Dejado, HARD.
J: Dejado, Med/Hard.
K: Codeando (Pablo). (46 AC)
L: AC
M: La idea está pero hay que codearlo y es una paja (Tin).

Faltando una hora y media, y sin muchas ideas concretas, redujimos la prueba a B,K,M, lo cuál es bueno porque no tiene sentido pensar tantos problemas al final (3 sería lo máximo en hora y media). Mi análisis de la situación es que había que meter 8 para ser Latam porque teníamos buena penalidad y 9 para la medalla, entonces estaba apurado para meter B y K.

Acá yo me pongo a codear la parte borde del K y le pido ayuda al Marian para codear la parte de la simulación trivial. Le cuento mi solución así no más y lo que él tenía que hacer que parecía una boludés pero yo no podía hacer ni un for. Marian se lo pone a hacer. Mientras tanto mandamos las primera subs del B que nos dan WA (que estábamos seguros que era error en la idea del Marian). Desgraciadamente había un error en el Dijkstra pero no se porque no nos dimos cuenta y nadie releyó el código. Yo estaba casi seguro que la idea del Marian estaba bien pero no dije nada porque estaba con el K, desgraciadamente también estaba mal. Cuestión, priorizamos meter el K.

Resumen (a las 4:00) - (28avos - LATAM Champions)
A: AC
B: WA (-2) Debugueando (Tin). (39 AC)
C: AC
D: AC
E: AC
F: No leido, dejado. (2 AC)
G: AC
H: Dejado por Geometría HARD
I: Dejado, HARD.
J: Dejado, Med/Hard. (1 AC)
K: Codeando (Marian y Pablo). (55 AC)
L: AC
M: La idea está pero hay que codearlo y es una paja (Tin). (1 AC)

El equipo en los últimos momentos

Mandamos por primera el K y WA. Marian se pone a recodear su parte mientras Martín se pone a intentar arreglar el B. Acá pasamos un tiempito debugueando ambos códigos. Yo pruebo un par de casos en el K y dan mal. Mandamos el K con la nueva parte del Marian y otro WA. Vuelvo a probar los mismos casos. Daban mal, y estábamos tan en cualquiera que ni habíamos probado los casos. Mientras tanto Martín entraba a ver cosas del B.

A las 4:30, luego de casi 2 horas sin meter ningún AC, charlamos 10 segundos y metemos una buena decisión y dejamos el B bajando nuestras espectativas (nunca repensadas) de 9 y medalla que teníamos hace 2 horas y apuntando a, al menos, meter 7. Yo encuentro un error en mi parte, puteo, la arreglo y con el nuevo código del Marian daba cualquier cosa. Pruebo con el viejo y da bien. Mando y WA!!! Marian me putea y dice que usemos su nueva parte, nos ponemos a debuguear y era una boludés, arreglamos, mandamos y AC!!!!
Otro grito de gol pero que no se grita para que nadie de latinoamérica sepa que metimos el 7mo y especule. Quedaban 16 minutos donde teníamos que meter el B para asegurar el Latam Champions. Nunca nos pusimos a ver el dijkstra del B. Nos pusimos a codear una idea fruta y mandamos 13 submissions probando cosas. Todas WA en la parte trivial del Dijkstra, ja.


Terminamos con 7 problema sobre 13, 32avos del mundo y Campeones Latinoamericanos (42avos quedo también con 7 el equipo de Pernambuco que si no metíamos el K nos hubiese ganado y Campina Grande quedó con 6).

http://myicpc.icpcnews.com/World-Finals-2016/scoreboard

Caloventor recibiendo el Latam Champions

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

• Info de la competencia http://torneoprogramacion.com.ar
• Enunciados http://torneoprogramacion.com.ar/wp-content/uploads/2017/10/tap2017.pdf
• Scoreboard http://torneoprogramacion.com.ar/2017/10/05/resultados-tap-2017/
• Juez online para enviar soluciones http://redprogramacioncompetitiva.com/contests/2017/11/

Solucionario

A

Mostrar Solución

Si ponemos simplemente las notas en un arreglo [do, do#, re, re#, mi, fa, fa#, sol, sol#, la, la#, si], podemos encontrar la respuesta encontrando la nota actual y restando S posiciones. Si la respuesta queda negativa, simplemente sumamos 12. Otra opción es copiar el arreglo una 2da vez para evitar este caso borde o trabajar con el módulo.
Código: https://pastebin.com/gFzPsdbL

B

Mostrar Solución

Consideramos los Pi en orden creciente ( Pi <= Pj , i0). Podemos ubicar el primer pirata que no es satisfecho por cada cofre buscando el upper bound de Ci en P (luego de ordenar P). Esto tiene una complejidad de NlogN (logN por cada upper_bound).
Con el procesamiento que hicimos podemos saber cuantos cofres podríamos asignar a cada pirata. Analicemos los Pi de derecha a izquierda (comenzando por el más grande) y empecemos a asignar cofres. La cantidad de opciones que barajamos para asignarle cofre al pirata i es la cantidad de cofres mayor o igual a sus requerimientos menos la cantidad de cofres ya asignados a los piratas de su derecha (n-i-1).
Complejidad: O(NlogN)
Código: https://pastebin.com/YrU2PS6G

C

Mostrar Solución

*g[i] es lo que quiere cada amigo.
*a[i] es la cantidad usada en cada cebada.
Las diferencias g[i] - g[i-1] determinan cuánto debe valer a[i] - a[i-k(mod N)].
Sea D = gcd(N,K), como sabemos las diferencias cada K elementos, podemos seguir ese ciclo (i, i+k, i+2k, …. (módulo N)) hasta saber todas las diferencias entre elementos de diferencia D.
Elegimos el ciclo que empieza en 0, con diferencia D. Con lo dicho antes podemos encontrar el más pequeño de ese ciclo y suponer que es 0. De esta manera ninguno de todo el ciclo puede ser menor ya que todos los a[i] deben ser positivos. Lo único que podemos hacer es sumarle una cantidad entera a cada elemento de ese ciclo. Hacemos lo mismo con cada ciclo.
Como ya sabemos las diferencias, solo tenemos que ver si es posible cumplir las necesidades de alguno de los amigos y ahí cumpliríamos todas. Para esto vemos algún amigo en particular. Si la suma de los a[i] mínimos supera lo que quiere ese amigo, requeriríamos cebadas negativas, IMPOSIBLE. Si da justo, es posible (cada ciclo tiene un elemento mínimo en 0.
Si es menor, necesitamos aumentar los valores de los ciclos. Sea C = K/D, la cantidad de elementos del mismo ciclo que hay cada K elementos. Si lo que necesitamos aumentar es múltiplo de C, es POSIBLE, modificando cualquiera de ese ciclo. Si no, tendríamos que hacer cebadas fraccionarias, lo cual es IMPOSIBLE.
Código: https://pastebin.com/Xq6TPWsB

D

Mostrar Solución

El primer paso es observar cuál va a ser la estrategia para ganar dinero. Lo que se debe hacer es comprar dólares en una ciudad y venderlos en otra, COMPLETAMENTE. La estrategia consiste en hacer este paso repetidas veces de forma de tener cada vez más. En segunda instancia hay que ver el carácter binario del problema (en este caso es ver que con menos de lo mínimo no voy a poder pero con más de lo mínimo siempre se va a poder), esto siempre es un fuerte indicio de que hay que aplicar búsqueda binaria. Por esta razón realizamos búsqueda binaria para encontrar el mínimo. Ahora, como es la función de evaluación? Es decir, cómo evaluamos si al iniciar con x cantidad de pesos podemos volvernos infinitamente ricos?
Para hacer esto se tiene que tomar en cuenta la estrategia mencionada al principio, esto limita considerablemente las posibilidades a tener en cuenta. Resulta que modelar esta estrategia se vuelve simple creando un grafo ‘especial’ con las ciudades, recorrer una arista en este grafo será equivalente a hacer un paso de nuestra estrategia.

Es recomendable hacer un Floyd-Warshall para pre-calcular la distancia mínima entre dos ciudades cualesquiera, utilizando estas distancias nuestro algoritmo tiene en cuenta rutas entre ciudades indirectas.

El grafo es ‘especial’ porque los pesos de las aristas no son distancias sino que guardan cuánto podemos aumentar nuestro dinero actual. Si en la ciudad X el cambio está 1 a 20 y en la Y 1 a 17, y nuestro dinero es Z, entonces recorrer la arista X->Y modificaría nuestro dinero a Z*20/17-dist(X, Y). Una vez construido el grafo, la función de evaluación consiste en aplicar Bellman-Ford desde nuestro nodo inicial, para encontrar ciclos infinitos. Notar que no es necesario buscar explícitamente el ciclo, basta con ver si luego de N-1 iteraciones el nodo inicial tiene más dinero que con el que se comenzó.

E

Mostrar Solución

Este problema tiene dos soluciones. Una es probar, a cada momento, todas las combinaciones posibles de cartas a jugar con el objetivo de maximizar la cantidad de manos a ganar de cada uno de los jugadores. La fuerza bruta no tarda mucho tiempo.
Y la otra es hacer los casos a mano.
* Si Eduardo no tiene el 1, excepto el caso 2-3-4, su abuelo (como puede tener el 1 y una del {2,3,4}) puede dejarle ganar posiblemente la primera mano para encajar {2,3,4} con la carta débil de Eduardo y ganar la otra mano con el 1 en las dos últimas.
* Si Eduardo tiene el 1, tiene que ganar alguna otra mano más. No es difícil ver que le conviene tirar la más baja para tener la mayor cantidad de chances de jugar su 2da mejor carta contra la que le convenga de su abuelo una vez que este le gane la 1er mano. Y hay que analizar los distintos casos.
Hubo soluciones aceptadas que solo contenían 3 ifs.
Código: https://pastebin.com/1gHDXh2X
https://pastebin.com/ADCi0UhJ

F

Mostrar Solución

Existen distintas soluciones a este problema pero la que considero más simple es calculando el complemento. Es decir en lugar de calcular cuánta felicidad hay dentro del intervalo pedido llamémosle [S, E], mejor cálculo la felicidad total y le resto la que queda afuera de ese intervalo. Resulta que esto último es ligeramente más simple: lo que ‘queda afuera’ se puede subdividir en dos conjuntos DISJUNTOS: los recitales que terminan antes que S, y los recitales que empiezan luego de E. Si voy manteniendo un contenedor con sólo los comienzos de los recitales y otro para los finales de los recitales esto debería ser fácil. Tal contenedor podría implementarse con un segment tree o un árbol balanceado.

G

Mostrar Solución

A primera vista el problema tiene pinta de ser una combinatoria resuelta a partir de programacion dinamica. Podemos pensar que si tuviéramos una dinámica de la forma: f( x , p1, p2 ) que sea la cantidad de formas de que se obtenga un resultado p1,p2 con x rondas tendríamos la solución al problema en f(N,P1,P2). Esto lo podríamos calcular en O(M) por estado. Pero la complejidad total seria O(P^2*N*M) lo cual es demasiado. Notar que en esa dinámica p1 y p2 son bastante independientes. Podemos calcular g(x, p1) la cantidad de formas de obtener p1 en x rondas no nulas para un solo jugador. Esto lo haríamos en O(M) en cada paso, con una complejidad total de O(P*N*M).
Luego podemos contar el total de juegos con resultados P1, P2 en N rondas (la respuesta al problema) analizando los casos con x rondas no nulas para el jugador 1 e y rondas no nulas para el jugador 2 y sumar todas (son disjuntas evidentemente) con x+y<=N. Para saber cómo las distribuimos en N formas las x e y tenemos comb[N][x]*comb[N-x][y], teniendo un total de g(x,P1)*g(y,P2)*comb[N][x]*comb[N-x][y]. Con una complejidad O(N^2) pre calculando los combinatorios en O(N^2) también.
Complejidad: O(P*N*M + N^2)
Código: https://pastebin.com/1i7JwYtg

H

Mostrar Solución

Si no hubiera números consecutivos iguales se puede ver que podemos garantizar que existe una montaña con la presencia de una cúspide (es decir un numero v[i] que es mayor que su predecesor y sucesor). Entonces eliminamos (como si comprimiéramos) consecutivos repetidos y contamos la cantidad de cúspides. Para qué predecesor y antecesor este definido en caso de que solo haya un número podemos considerar 0 auxiliares en los extremos.
Complejidad: O(N)
Código: https://pastebin.com/jiqn0v02

I

Mostrar Solución

Para determinar si son similares hay que notar que los puntos pueden llegar a lo sumo ser una rotación de los originales (o una rotación invertida). Podemos probar con cada una de las rotaciones posibles (y su rotación invertida) chequeando si se corresponde con la original. Para hacer el chequeo basta con comprobar que los ángulos internos son iguales y que los lados son proporcionales.

J

Mostrar Solución

Lo primero que hay que notar es que por cada nombre N, como no es compartido y cada jurado tiene sólo 2 nombres, tiene que tener un opuesto N’ (N’ esté presente en cada edición si y solo sí no esté N).
Entonces si le podemos asociar a cada nombre un posible opuesto (con el caso especial de los nombres que estén siempre), claramente es posible que siempre hayan sido los mismos (lo probamos constructivamente). Caso contrario no.
Para esto, podemos guardar para cada nombre una lista de apariciones y simplemente buscar un posible opuesto y eliminar ambos hasta que no quede ningún nombre disponible.
Código: https://pastebin.com/r5pPqGXT

K

Mostrar Solución

Sea M la cantidad de elementos impares en el arreglo.
*Para M = 0 la respuesta es 0. Supongamos M >= 1.
- Se pueden convertir a todos los elementos en pares haciendo M + 1 operaciones de la siguiente forma:
* Si M = 1: dividimos el único número impar a[i] y multiplicamos alguno de los pares a[j] (existe porque N >= 2). Después dividimos a[j] y multiplicamos a[i].
* Si M > 1: Seleccionamos 2 impares, uno se divide, otro se multiplica. Nos queda un impar menos gastando una operación. Repetimos esto hasta que M <= 1.

Lema.: la respuesta es <= M si y sólo si existe algún a[i] (par o impar) y un k (1 <= k <= M) tal que el k-ésimo bit de a[i] es 0.
Dem (super resumida):
* (=>) Supongamos que no existen a[i] y k como se describen arriba. Supongamos que aplicamos M operaciones o menos. Necesitamos multiplicar cada impar (las divisiones no generan pares) plus una extra previa para el último número que dividimos. Contradicción, necesitamos más de M.
* (<=) Sea i el índice descrito, y k el bit. Aplicamos M-k veces el protocolo de tocar otros dos impares (uno lo dividimos, otro lo multiplicamos). Finalmente dividimos k veces el a[i] mientras que multiplicamos impares. Luego de a lo sumo M operaciones (dependiendo de si a[i] era impar) se obtienen todos pares.

Ahora que sabemos que la rta <= M, a cada impar se le asigna un valor g[i] que es la cantidad mínima de divisiones que necesita para hacerse par.

Se puede demostrar que, dada R la respuesta, el algoritmo que “parifica multiplicando” R impares y “parifica dividiendo” los M-R restantes es posible si y sólo si la sumatoria de los g[i] (de los M-R) es menor o igual a R.
* Por lo tanto se puede aplicar el algoritmo greedy para encontrar la solución que “parifica dividiendo” los de menor g[i].
Código: https://pastebin.com/VSTUxsDY

L

Mostrar Solución

Este problema consta de dos partes. Una es encontrar las 6 combinaciones posibles de bolsitas que se pueden armar, a las que enumeramos:
1. LLLL
2. OOOO
3. TTTT
4. LLSS
5. LSTT
6. LLOO

Podemos suponer greedymente que los paquetes 5 y 6 están a lo sumo una vez, puesto que si no también existe una solución usando los paquetes (3,4) y (1,2) respectivamente por cada parcito de los anteriores que da lo mismo.
A partir de ahí, es fácil ver que si seguimos el orden 4-3-2-1 encontramos la solución óptima. Por lo tanto solo es necesario probar los 4 casos sobre la paridad de bolsas hechas con p5 y p6 y seguir con el algoritmo.
También hay una solución sin probar los 4 casos que sigue un orden greedy particular de eliminación que se la deja al lector como ejercicio.
Código: https://pastebin.com/cFVUDHBH

Sigue los equipos latinoaméricanos filtrados: http://bit.ly/2rhxAI6

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

• Enunciados: http://maratona.ime.usp.br/resultados16/contest.pdf
• Juez para submitear: https://www.urionlinejudge.com.br/judge/es/problems/origin/136 (al menos hasta que se suban los problemas a live archive)
• Standings: https://icpc.baylor.edu/regionals/finder/southamerica-south-2016/standings

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

Mostrar Solución

Trivial

Basta con probar todas las posibilidades e imprimir la mejor de ellas.

B

Mostrar Solución

Greedy

Considere un grafo donde dos elementos están conectados si son compatibles. Si un vértice posee grado menor que $A$, es imposible que forme parte de la respuesta (no importa que otros vértices elijamos, el vértice nunca cumple la condición de tener al menos $A$ vecinos), por lo que podemos removerlo.

De la misma forma, si nuestro grafo posee $N$ vértices y uno de ellos tuviera grado mayor que $N-B$, es imposible que forme parte de la respuesta, y podemos removerlo.

Continuamos quitando vértices hasta que ningún vértice precise ser removido. Lo que nos queda es un conjunto válido, por definición, y debe ser el mayor posible, pues solamente removimos vértices que nunca iban a ser parte de la respuesta.

Resta pensar sobre como implementar esto eficientemente: el truco es mantener un set de vértices ordenados por su grado, posibilitando identificar rápidamente los vértices de menor y mayor grado. Cuando un vértice es removido, el grado de todos sus vecinos es actualizado en el set.
En C++ la forma más fácil de implementar esto es usar un arreglo gr[i], que guarde el grado de $i$ y un set< pair< int, int > > que guarde pares de la forma (gr[i], i). El orden por defecto del set va a priorizar la primera coordenada (el grado), por lo cual podemos usar begin() y end() para obtener los vértices de menor y mayor grado. Para decrementar el grado de un vértice $i$ puedo quitar (gr[i], i) del set, hacer gr[i]-- y luego agregar (gr[i], i) al set.

C

Mostrar Solución

Geometría/Combinatoria

Este es uno de esos problemas tramposos: el enunciado lo hace parecer más difícil de lo que es.

Es intuitivo que si un conjunto de puntos cumple con la propiedad de que al rotarse vuelva a ser el mismo, este conjunto puede ser dividido en varios polígonos regulares (por ejemplo, si $\alpha = 120º$, para que al rotar el conjunto vuelva a ser él mismo, el conjunto debe formar varios triángulos equiláteros, y el centro de rotación debe ser el centro de los triángulos).

Ahora viene la parte crucial del problema: las coordenadas son enteras, por lo que (quitando los cuadrados) los polígonos regulares no existen! (prueba, para los curiosos: http://hrcak.srce.hr/file/2836)

Teniendo en cuenta esto, las únicas cosas que pueden rotarse y volver a ser lo mismo son puntos (exactamente sobre el punto de rotación) y segmentos de recta (rotadas $180º$, con centro de rotación en el punto medio). Sabiendo esto, la única posibilidad que necesitamos considerar es cuando el $\alpha = 180º$.

El resto es combinatoria: cada par de puntos puede ser rotado a partir de su punto medio, entonces podemos tomar todos los pares y calcular sus puntos medios, que son los posibles centros de rotación. Para cada posible centro, si este tiene $P$ pares que pueden ser rotados por él, para cada $0<=p<=P$ existen $\binom{P}{p}$ subconjuntos de tamaño $2p$ que utilizan ese punto como centro de rotación.

D

Mostrar Solución

Greedy/Geometría

El área del diagrama es la suma de las áreas de los triángulos formados por dos atributos adyacentes. Si existen $n$ atributos, el área de un triángulo adyacente a los atributos $P_i$ y $P_{i+1}$ puede ser dada calculada por la fórmula $\frac{1}{2} \sin(\frac{2 \pi}{n}) P_i P_{i+1}$. Los dos primeros términos son constantes para todos los triángulos, por lo que basta escoger el orden de los valores de P que maximizen la suma de los productos $P_i$ $P_{i+1}$.

Intuitivamente, queremos que el mayor valor de $P$ contribuya lo máximo posible para la respuesta, entonces lo mejor sería multiplicarlo con los siguientes dos mayores valores de P. Continuando el razonamiento, si $P$ está ordenado de forma que $P_1$ es el mayor y $P_n$ es el menor, el mejor orden es $..., P_7, P_5, P_3, P_1, P_2, P_4, P_6, ...$.

E

Mostrar Solución

Estructura/Wavelet Tree o Segment Trees

Solución 1

Este problema requiere conocimiento de una estructura llamada Wavelet Tree. Permite responder a la pregunta "cual es el $k$-ésimo menor elemento en el intervalo $[i,j]$ de un arreglo dado?" en $O(\log{}n)$.

Esta estructura puede ser usada para resolver el problema "Batata Quente" de la primera fase de la maratona de Brasil (http://maratona.ime.usp.br/prim-fase16/maratona.pdf) en $O(n\log{}n)$ (La solución oficial tenía complejidad de $O(n \sqrt{n}\log{}n)$, usando sqrt decomposition.)

Hay una explicación disponible en Quora: https://www.quora.com/How-can-you-build-a-data-structure-on-an-array-that-returns-kth-order-statistics-on-subarrays-in-logarithmic-time.
También se encuentra descripta en el paper de los autores, que también explican como hacer la actualización de intercambiar dos elementos adyacentes (es muy simple): https://www.dcc.uchile.cl/~jperez/papers/ioiconf16.pdf.

Solución 2

Existe otra solución posible para responder la misma query de los Wavelet Trees en $O(\log^2{}n)$, que consiste en construir un segment tree sobre el rango de valores. Por ejemplo, si el arreglo $V$ es $V[0]=2, V[1]=0, V[2]=1, V[3]=2, V[4]=3$, entonces en la hojas guardaremos $hoja[0]=\{1\}, hoja[1]=\{2\}, hoja[2]=\{0, 3\}, hoja[3]=\{4\}$ (una especie de inversión del arreglo). La operación del segment tree va a ser la unión (sobre multiset) y para responder las queries debemos usar búsqueda binaria sobre cada nodo.
Nota: No es necesario codearse un árbol balanceado, podemos usar la STL (ver: http://codeforces.com/blog/entry/11080)

Solución 3

Es posible hacer otra solución utilizando segment trees persistentes y contestar la query en $O(\log{}n)$. Esta solución alternativa fue explicada por Victor Agnez en el blog de FFAO (la cual inspiró la explicación que sigue). El código está disponible en: http://ideone.com/HdOhu1.

Para facilitar la explicación, primero vamos a considerar un problema más simple: a partir de un arreglo de números, mantener un segment tree que responda cuantos elementos con valor entre $a$ y $b$ existen. Esto es fácil, construimos un segment tree donde la hoja $i$-ésima guarda la cantidad de veces que el número $i$ aparece en el arreglo. Utilizamos la operación suma para construir el segment tree. Lo que tenemos es que cada nodo representando el rango $[a, b]$ nos dice cuantos valores hay en ese rango.
En este segment tree es fácil buscar el $K$-ésimo menor elemento: lo hacemos recorriendo el árbol desde la raíz. Suponiendo que estamos en el nodo que representa el intervalo [a,b], el hijo izquierdo contiene la cantidad de elementos en el rango $[a, \frac{a+b}{2}]$. Si esa cantidad es menor o igual a $K$, entonces el $K$-ésimo menor elemento se encuentra en el hijo izquierdo. De lo contrario, el $K$-ésimo menor está en el hijo derecho. Si llegamos a una hoja, encontramos el $K$-ésimo.

Volviendo al problema E: vamos a suponer que para cada prefijo del arreglo, tenemos ese segment tree. Ahora, si miramos el $j$-ésimo segment tree y un nodo dentro del mismo representando el intervalo $[a, b]$, él mismo va a tener guardado cuantos valores en el rango $[a, b]$ hay en las posiciones $[0, j]$ del arreglo original. La clave de esta solución está en notar que si un nodo del $j$-ésimo segment tree guarda cuantos hay en el intervalo $[0, j]$, podemos restarle el mismo nodo pero del $(i-1)$-ésimo segment tree y obtener cuantos hay en el intervalo $[i, j]$ (es decir tomamos cuantos hay en o antes de $j$ pero le restamos los que aparecen antes de $i$). Es decir que, restando nodo a nodo el $j$-ésimo y el $(i-1)$-ésimo segment tree, puedo obtener un nuevo segment tree que me cubriría sólo el subarreglo $[i, j]$. Recorriendo este segment tree, puedo encontrar el $K$-ésimo menor de la misma forma ya explicada. El detalle está en que no es necesario crearse el nuevo segment tree entero, basta con ir haciendo la restas entre los dos árboles a medida que voy necesitando los valores.

Por último, notar que el $i$-ésimo segment tree es muy semejante al segment tree de prefijo $(i-1)$: apenas se agrega un elemento (sólo se hizo una operación de modificación). Por lo que utilizando persistencia (que aprovecha la memoria en común entre los árboles) podemos efectivamente tener los árboles de todos los prefijos.

F

Mostrar Solución

Trivial/Simulación

Basta simular el camino del robot como se describe en el enunciado..

G

Mostrar Solución

Strings/KMP

Es uno de los problemas más elegantes de la prueba, es difícil de entender al principio pero el código es muy corto.

El primer paso es relativamente intuitivo: como para los matching no importa que letra es cual, debemos representar las strings de una forma que no importe cual letra es cual.

Tal vez la forma más obvia sería sustituir la primera letra que aparece por "a", la segunda letra que aparece por "b", y así sucesivamente. Pero esa representación no es muy práctica pues es difícil determinar las representación de substrings de manera eficiente: por ejemplo, la representación de la substring "cd" en "abcdef" es "ab", y eso traería problemas más adelante.

Una posibilidad mejor de representación: representamos cada letra por la distancia entre esa letra y su última ocurrencia (si la letra no hubiese aparecido antes, ponemos -1). Por ejemplo: la string "awawww" se vuelve "-1 -1 2 2 1 1". Es fácil ver que con esta representación conseguimos lo que queríamos: dos strings que matchean (por ejemplo, "awa" y "dcd"), tendrán siempre la misma representación.

Una vez hecha la conversión, casi que podemos usar KMP, pero todavía tenemos el problema de las substrings: por ejemplo, la substring "waw" en "awawww" (-1 -1 2 2 1 1) tiene la representación -1 -1 2, mientras que la substring correspondiente de la representación es -1 2 2. Podemos ver que pasó aquí: el primer 2 está apuntando hacia afuera de la substring, por lo que debería ir un -1. Ese es el único cambio que debemos hacer al calcular la representación de una substring.

Recordemos que hace el algoritmo de KMP: repetidamente se toman dos prefijos iguales y compara si los próximos caracteres concuerdan. En el código del KMP, el cambio anterior puede ser traducido en un único if: en la comparación de los próximos caracteres, si alguno de ellos apunta fuera del prefijo, debe ser considerado como un -1.

H

Mostrar Solución

Greedy

Puede ser razonable pensar en una DP para resolver este problema, pero los límites son demasiado grandes. Vamos a analizar mejor las condiciones del enunciado. Vemos que se deben satisfacer las siguientes condiciones:
Dentro de las primeras $K$ noches, ninguna es eliminada.
Dentro de las primeras $2K+1$ noches, como máximo 1 es eliminada.
Dentro de las primeras $3K+2$ noches, como máximo 2 son eliminadas.
...

Si fuéramos a eliminar una noche de entre las primeras $2K+1$, ciertamente será la noche de costo máximo entre las noches $K+1$ y $2K+1$.

Extendiendo esto para las primeras $3K+2$ noches, escogemos la noche de mayor costo entre $2K+2$ y $3K+2$ y necesitamos decidir si vale la pena eliminar una noche de entre las primeras $2K+1$. La segunda noche escogida será entonces la mejor noche de entre las primeras $2K+1$, o la segunda mejor noche entre $2K+2$ y $3K+2$.

Continuando este proceso, vemos que el problema puede ser resuelto por un algoritmo greedy: es mantenida una priority queue con las mejores noches a eliminar hasta el momento. Cuando la noche $i$ es procesada, se verifica si vale la pena remover alguna noche ya escogida para incluir la noche $i$. La excepción es si $i$ es múltiplo de $K+1$, en tal caso no es necesario remover ninguna noche anterior para incluir $i$.

I

Mostrar Solución

Optimización DP

Primero debemos responder a la pregunta: Cuál es el menor costo posible para unir las casas de la ciudad $i$ a la ciudad $j$ a una misma estación? Una propiedad de conjuntos de puntos en una recta es que el punto que minimiza la suma de las distancias a los demás es la mediana del conjunto; de esta forma si consideramos la posición de todas las casas, la estación debe ser construida en la ciudad en que se encuentra la casa de posición mediana. El cálculo del costo en si puede ser efectuado con algunos pre-cálculos y sumas parciales.

Lo que resta del problema es modelar y optimizar una DP. Para optimizarla debemos aplicar lo que se conoce como "divide and conquer trick". Pueden buscar información sobre esta técnica de optimización en Google, material en inglés hay de sobra. Vamos a intentar en las próximas semanas subir al blog material en español sobre esto.

J

Mostrar Solución

Matemática

Si el coach retorna a la sala inicial después de recorrer $T$ túneles, eso significa que la sala inicial es parte de un ciclo, cuyo tamaño es un divisor de $T$ mayor que 1. Es posible probar que el número de grafos en los cuales la sala forma parte de un ciclo de tamaño $C$ disminuye a medida que $C$ aumenta, luego queremos que $T$ tenga la menor cantidad de divisores posibles, y si los tiene, que sean grandes: esto sucede si $T$ es primo, pues los únicos divisores de T serán 1 y él mismo. Así, basta imprimir el mayor primo menor o igual $N$.

Prueba, si alguien está interesado: vamos a calcular el número de grafos en que el vértice 1 es miembro de un ciclo de tamaño $C$. Podemos escoger los demás vértices del ciclo de $\binom{N-1}{C-1}$ maneras, y el orden de los vértices en el ciclo de $(C-1)!$ maneras. Los demás vértices pueden tener un túnel yendo hacia cualquier lugar, teniendo así $(N-1)^{N-C}$ posibilidades. Así, el número final es $\binom{N-1}{C-1} (C-1)! (N-1)^{N-C}$, el cual decrece a medida que aumenta $C$ (perdemos un factor de $N-1$ para agregar un factor menor).

K

Mostrar Solución

Flujo

Vamos a resolver el problema suponiendo que ya sabemos quien es el hombre lobo, después basta repetir el algoritmo para cada uno de los participantes.

La elección óptima para los que pueden votar al hombre lobo es claramente votar en él, por lo que no necesitamos preocuparnos por esas personas. Considerando que el hombre lobo recibe $X$ votos, él gana si alguien recibe por lo menos $X$ votos, o si alguna de las dos personas que puede elegir el lobo tiene al menos $X-1$ votos.

En el fondo, este es un problema bien tradicional de flujo máximo: Cada persona recibe una unidad de flujo de la fuente, que debe enviar para alguna de sus dos posibles elecciones (realizar un voto). Cada elección puede recibir como máximo $X-1$ o $X-2$ votos, y esta es la cantidad de flujo que puede pasar para la fuente. Los aldeanos ganan si todos consiguen votar, o sea, si el flujo máximo fuese igual al número de personas que deben escoger sus votos.

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!):

Mostrar Spoiler

A, J / L, C, F, H, B, G / D, E, I, K.  Muy probablemente difiera con lo que muchos piensen pués es una prueba dónde se han concentrado mucho los problemas en la franja media (abarcando muy bien el espectro de medio-fácil a medio-difícil).

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

Mostrar Solución

(ad hoc)

El problema trivial. Imprimir "S" o "N" según si había o no la letra 'i'.
Solución Python de una línea:
print("SN"["i"in input()])

Problema B

Mostrar Solución

(programación dinámica)

- Dividimos los puntos que no son E ni S en dos conjuntos: A = { E+1,  E+2, ... S-1 } (mod N) y B = { E-1, E-2, ... S+1 } (mod N)
- Sea A_i y B_i los i-esimos de los respectivos conjuntos en el orden mencionado (partiendo desde E), observar que el recorrido óptimo recorre los A_i y B_i en orden.
- El problema puede resolverse con programación dinámica en N^2.
- La recursion nos queda de la forma f(i,j,flag) respuesta óptima de llegar a S habiendo recorrido hasta A_i del conjunto A y B_i del conjunto B, flag indica si nos encontramos en i o j.
- Se podría prescindir de flag ya que dado un par (i,j) sin saber cual corrresponde a A y cual a B podemos determinarlo (los puntos son bien de A y otros de B) y podemos considerar que la segunda componente del par es el elemento donde nos encontramos.

Problema C

Mostrar Solución

(DFS)

- Guardamos para cada materia la cantidad de correlativas no aprobadas y marcamos como no aprobadas a todas las materias.
- Al principio la respuesta de cantidad de materias en el sistema es 0.
- Cada vez que aprobamos una materia la marcamos como aprobada y la "procesamos".  El procesamiento consiste en ver si está aprobada y la cantidad de correlativas no aprobadas es 0, de ser así incrementamos la respuesta, disminuimos en 1 la cantidad de correlativas no aprobadas de sus hijos y los procesamos.
- Ver que la condición del procesamiento se satisface sólo una vez. Luego sólo una vez se recorrerán a sus hijos. El procesamiento es invocado sólo por el padre y cuando se aprueba la materia. La complejidad es O(N+M).

Problema D

Mostrar Solución

(geometría, giro ó intersección círculos ó set)

- Para cada par de puntos (x,y) calculamos todos los posibles valores de lados de un triángulo semejante al original con un lado igual al segmento formado por estos puntos (6 casos).
- Podemos utilizar intersección de círculo para determinar donde se encontrarían el tercer punto (dos posibilidades para cada elección de lados).
- Chequeamos si estos puntos existen en nuestro input. Lo podemos hacer con un set en O(log(N)).
- Complejidad: O(N^2 log(N)).
- Tener cuidado de no estar contando repetidos. Tener en cuenta el caso donde el triángulo usado es isósceles.

Solucion alternativa:

Esta solución me dio AC, según mi análisis de complejidad es O(N^3). Aunque puede que las restricciones propias de la geometría euclídea y puntos enteros hagan que sea mucho menor.
- Creamos map< long long, bitset<1000> > mp[MAXN]. Donde para cada vertice v y distancia a otro vertice d mp[v][d] representa el conjunto de vertices a distancia d de v con subíndice mayor que v.
- Para cada par de puntos (x,y) calculamos por proporcionalidad todos los posibles valores de lados de un triángulo semejante al original con un lado igual al segmento formado por estos puntos (6 casos). Este punto es igual a la solucion anterior. Ver que solo nos importan si estas distancias al cuadrado son enteras.
- Siendo l1 y l2 el tamaño de los lados para el par de vértice (x,y) obtenido en un caso del apartado anterior actualizamos la respuesta con size( interseccion(mp[x][l1],mp[y][l2]) ).
- Si usamos un unordered_map (mas el uso de bitset para representar conjuntos), la cantidad de operaciones es de N cubo. Aunque hay que resaltar que la interseccion posiblemente sea O(N) pero con una constante muy baja (1/64) por el uso de bitset. Además la intersección sólo se ejecuta si l1 y l2 calculados resultan enteros y además l1 y l2 existen como claves en mp[x] y mp[y] respectivamente. Lo cual no siempre sucede y hace más rápida a nuestra solución.

Problema E

Mostrar Solución

(grafos DFS)

- La observación clave es: "Existe una cadena de botones que independientemente de donde me halle me lleve al 1 sí y sólo sí para todo par de estados existe una cadena de botones que independientemente de cual de los dos me halle me lleva al estado 1".
- => trivial
- <= induccion sobre el conjunto de estados donde posiblemente estoy. La premisa me permite ir reduciendo en 1 la cantidad aplicando la cadena que me da.
- Luego si consideramos el grafo cuyos vertices son pares de aplicaciones (i,j) y existe una arista a (a,b) si apretando un boton paso del estado i al a y del j al b. (N^2 vértices N^2M aristas). Existe existe una cadena de botones que independientemente de cual de las dos aplicaciones A,B me halle me lleva a la 1 sii existe un camino (A,B) a (1,1).
- Tenemos que chequear que para todas las aplicaciones a,b del vertice (a,b) se pueda alcanzar el vertice (1,1) en el grafo descripto.
- El grafo tiene N^2 vertices y N^2M aristas. La complejidad total es de O(N^2M).

Problema F

Mostrar Solución

(greedy)

Para resolver este problema se deben hacer primero varias observaciones.

1) Sólo las letras D y R importan, podemos eliminar todas

las demás letras.

2) Si hay dos D o dos R consecutivas en un nombre es lo mismo que solamente tener una.

3) La tercera es que si existe un DR en un nombre, entonces de forma greedy podemos pintar ambas letras de fucsia

(sumando 1 a la respuesta) y ya borrarla de la palabra.

Utilizando todas estas observaciones, los posibles nombres se reducen a tres: D, R y RD.

Resta ver como combinar estas palabras de forma óptima. Si tenemos al menos una D, se la puede juntar con una RD: DRD. Aplicando 3) esta DRD se transforma en una D (y le suma uno a la respuesta).

Análogamente R+RD se transforma en R (sumando uno a la respuesta). 

En cambio si no tenemos ninguna R ni ninguna D, solamente nos queda juntar las RD (aquí se desperdician las dos letras de los extremos).

Por último, cuando sólo nos quedan D's y R's, la cuenta es muy simple. La fórmula quedaría:

if(cant_RD>0){

    if(cant_D+cant_R>0) ans += cant_RD

    else ans += cant_RD - 1

}

ans += min(cant_D, cant_R)

Problema G

Mostrar Solución

(trie)

- El costo en el camino es el xor del costo de las aristas.
- Usando la promoción ir del nodo A al B cuesta lo mismo haciendo cualquier camino (usar dos veces un tramo sale gratis).
- Tomando una ráiz arbitraria R, costo(A,B) = costo(A,R) xor costo(B,R).
- Sean val[A] = costo(A,R) (podemos computarlo con un DFS). Ahora la respuesta para un nodo v es max_{a in V} val[a] xor val[v]. Este es un problema clásico lo podemos resolver pensando a cada val[v] como string de 0's y 1's y construyéndonos un trie con ellas (con el bit mas significativo a la izquierda). Luego para cada v obtenemos la respuesta utilizando el trie, siempre eligiendo el caracter más conveniente "encendiendo" bits en el resultado siempre que sea posible.

Problema H

Mostrar Solución

(programación dinámica)

- Sea f(X,Y,N) la respuesta a nuestro problema podemos hacer programación dinámica.
- Observar que f(X,Y,N) cuando Y>0 y N>1 depende solo posiblemente de f(X,Y-1,N-1) y f(X-1,Y-1,N-1) (cuando Y==0 o N==1 es un caso base). La cantidad de estados visitados es NN ya que Y y N son recuperables uno del otro.
- Tirar el parámetro que podemos recuperar y hacer la DP en N^2.

Problema I

Mostrar Solución

(matemática, ec lineal modular, grafo, Prim)

La idea principal es esta: Imaginar un grafo donde los vértices son las ranas y las aristas indican el tiempo (absoluto) en que esas dos ranas se encuentran. Pensamos ahora como resolver el problema utilizando este grafo. Un algoritmo posible es similar al Prim, comenzando desde la rana infectada. La idea es que en cada paso del Prim, de todas las ranas no infectadas se elija la se encuentre primero con una infectada, luego esta rana se infecta. Así el árbol recubridor representaría la historia de las infecciones.

En lugar de generar el grafo explícitamente (el cual puede tener infinitas aristas), para cada nodo expandido, buscaremos el tiempo de encuentro con las ranas no infectadas. Es importante tomar en cuenta solamente los encuentros después de que la rana fue infectada (razón por la cual este algoritmo no es exactamente Prim).

Resta ver como calcular los tiempos de encuentro:

Supongamos que tenemos dos ranas i y j, y queremos saber el próximo encuentro después del tiempo t, llamemosle t'.

Fijamos en que punto del patrón se van a encontrar: llamemosle m (es decir t'%K==m)

Calculamos en que posición se encuentra cada rana en el tiempo t + el tiempo que le lleva alcanzar el primer m, llamemosle p_i y p_j.

Si después de una ciclo completo del patrón la rana i avanza c_i charcos, se puede inferir que los puntos en los que t'%K==m

tienen la forma:

t' = p_i + x * c_i (mod n)

Utilizando estos datos podemos plantear la siguiente ecuación:

p_i + x * c_i = p_j + x * c_j       (mod n)

Resolviendo esta ecuación es posible encontrar el primer tiempo de encuentro de las ranas (si es que existe).

Luego hacemos un for para todos los posibles m y tomamos el mínimo.

Problema J

Mostrar Solución

(greedy)

- Ir poniendo las palabras en orden decreciente de longitud, empezando una nueva columna de ser necesario anchura igual a la palabra a insertar es óptimo.

Problema K

Mostrar Solución

(teoría de juegos, greedy ó programación dinámica)

Por simplicidad dividimos en dos partes la explicación.

Parte I:

- Existe un único camino simple de M a P. Veamos el problema como un camino M <-> P y "subarboles" colgantes de el mismo conformado por los nodos que no pertenecen al camino.
- Inicialmente M y P pertenecen al camino. Para todo vertice no perteneciente al camino visitarlo implica "salirse del camino" y no se puede volver a entrar. Tanto M como P sólo pueden visitar un único de los subárboles mencionados.
- La respuesta óptima de salirse del camino desde un vértice v es fácilmente calculable con un DFS. El problema quedó reducido a un camino y un vértice que se desprende de cada nodo del camino:
 M - o - o - o - o - o - o - P
 |      |    |   |   |   |   |   |    |
 o     o   o   o   o   o   o   o

Si bien creo que hay una solución que yo categorizaría de greedy para este problema (se basa en de observaciones matemáticas)  esta es la solución con DP que hice, lo bueno es que es muy simple entender que funciona.

Parte II:

- En lo sucesivo c[i] es el valor de cada vértice del camino, ca[i] del que se desprende de él con i=0..len-1. Donde len es la cantida de nodos del camino M-P, el nodo 0 representa a M y len-1 a P. Además consideramos len impar (si no és se puede agregar un nodo con c y ca igual a 0) y mid será la posición del vértice del medio.
- Es fácil calcular con programación dinámica (en el código pueden ver las fórmulas)
    - sumMid[i]: el acumulado de c[i] de i hasta el mid.
    - toMid[i]: estando en el nodo i la máxima cantidad de puntos podemos hacer yendo a lo sumo hasta mid.
    - fromMid[i]: estando en el nodo mid la máxima cantidad de puntos podemos hacer yendo para el lado donde se encuentra i, y llegando a lo sumo hasta un nodo antes de i.
- Ahora resolveremos el problema con programación dinámica, siendo f(i,j) la cantidad de puntos si ambas juegan óptimo arrancando M en la posición i del camino y P en la j. Nosotros queremos calcular f(0,len-1).
Caso base:
    f(mid-1,mid+1) = max ( ca[mid-1] - max(ca[mid+1],ca[mid]+c[mid]) , ca[mid]+c[mid] - ca[mid+1] )
    Como M juega primero puede elegir salirse del camino (primera opción) o ir al medio. P juega el máximo posible a consecuencia de ello.
Paso inductivo: (Acá i y j están a distancia mayor que dos)
    (A) i puede elegir irse del camino y ganar ca[i], con lo cual j puede seguir por el camino hasta a lo sumo un vértice antes de dicho nodo. Así la óptima es en este caso: ca[i] - max( sumMid[j] + fromMid[i] , toMid[j] )

    (B) i puede elegir seguir en el camino, sumando c[i+1]. Luego j puede:
        (B.1) seguir en el camino sumando c[j-1]. A lo cual el juego sigue en f(i-1,j-1). Teniéndose el valor óptimo para j de esta opción (dado que i ya eligió seguir en el camino) resulta: c[j-1] - f(i+1,j-1)
        (B.2) abandonar el camino en j, teniéndose una fórmula análoga al apartado (A) (pero ahora es j el que abandona el camino y ya se ha avanzado M hasta i+1): ca[j] - max( sumMid[i+1] + fromMid[j] , toMid[i+1] )
    Así la fórmula para el apartado (B) es: c[i+1] - max( c[j-1] - f(i+1,j-1) , ca[j] - max( sumMid[i+1] + fromMid[j] , toMid[i+1] )  ) (j elije la mejor opción de ambas).
Quedando el max entre las fórmulas de (A) y (B).
- La dinámica f(i,j) se basa sólo en el estado anterior f(i-1,j-1). Sólo se visitan O(N) estados. Podemos tirar un parámetro y recuperarlo del otro y la complejidad total será O(N).

Problema L

Mostrar Solución

(ad hoc, greedy)

Existen muchas soluciones posibles, a continuación la que yo creo más corta y simple. El problema nos define un árbol, y luego nos da una cadena. Nuestra tarea es decir si esta cadena es un camino en el árbol o no. Notar que en este árbol el padre es siempre mayor a sus hijos, por lo que todo camino válido va a estar dividido en dos partes: una ascendente y otra descendente. El máximo M de la cadena nos dara el punto de separación.

Para los elementos que estén en la parte ascendente tenemos que chequear que su anterior es el hijo. Para los elementos que estén en la parte descendente tenemos que chequear que su siguiente es el hijo. Para chequear si a es hijo de b podemos utilizar directamente la definición dada en el enunciado: b>2 and (a+1==b or a+2==b).

Por último debemos asegurarnos que la parte ascendente y la descendente sean disjuntas. Para esto basta con solo verificar que el anterior y siguiente de M son distintos.

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.