Primero que nada agradecer a los organizadores de la competencia y al departamento de nuestra carrera que nos apoyaron siempre. Después casi dos años entrenando tuvimos un resultado muy gratificante, logramos ser campeones de nuestra región! (Argentina, Perú, Bolivia, Uruguay, Chile y Paraguay). Estamos muy contentos por haber clasificado a las siguientes World Finals, a realizarse en Tailandia. Felicitaciones a todos los equipos que participaron. Esperamos que en los siguientes años otros equipos vivan lo que nosotros vivimos.

Los tres equipos de Rosario: Flower Power, Caloventor en Dos (con nuestro elefante) y [Listas, Turings y Lambdas]

Scoreboard final

http://bombonera.org/board/

Juez Online y Enunciados 

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=702

Nuestra compu al final de la competencia

Soluciones

A - At most twice

Mostrar Solución

Hay una dinámica que siempre aniquila a los problemas de este estilo que es ir avanzando sobre la cadena de caracteres de la representación decimal del número, conservando información útil y decir si se puede encontrar o no un número como el buscado. Generalmente llevamos además en el estado si el prefijo que venimos procesando es igual al del número dado o menor (para saber que dígito poner si decidimos cambiar asegurándonos que estamos analizando números menores al dado). Aquí la información adicional era la cantidad de cada dígito usada. Luego reconstruir adecuadamente para encontrar la mayor solución. Complejidad: O(3^10 * 18 * 2). También puede resolverse más fácil con greedy.

B - Blood groups

Mostrar Solución

El problema nos pide si se puede encontrar una asociación padre-gen del hijo para cada uno de los genes activos del hijo, sabiendo que cada padre puede dar a lo sumo un gen. Eso es buscar si existe un matching completo (para la cantidad de genes del hijo) en un grafo bipartito dado por los padres y los genes activos del hijo, lo cuál se puede resolver con cualquier algoritmo de Max Flow. Notar que cualquier padre no matcheado puede dar el gen 0 sin alterar la configuración del hijo excepto que tenga cada uno de los N genes. En ese caso, puede dar cualquiera de los que ya le hayan pasado otro padre excepto que el hijo no tenga ningún gen, en cuyo caso la respuesta es negativa.

C - Cake cut

Mostrar Solución

Si fijamos el punto i que elige Carol entonces Carla intenta elegir el punto j que está "más al medio" (minimiza la diferencia de áreas). Podemos para cada i calcular su j pero es O(n^2). La clave es notar que si ya calcule el j de un i puedo aprovechar esto para calcular el j correspondiente al i+1: el j de este i+1 tiene que estar sí o sí igual o más adelante que el j del i. Teniendo esto en cuenta podemos ir aumentando los índices i y j (de tal manera que siempre el corte i-j quede a la "mitad") en O(n).

D - D as in Daedalus

Mostrar Solución

Como quiere obtener la mayor puntuación absoluta posible siempre le conviene sumar la mayor cantidad de puntos. Osea jugar la mayor carta tal que el banco pague. Simple simulación.

E - Exposing corruption

Mostrar Solución

Primero observar que el grafo es bipartito. Ahora veamos que pasa con cada componente conexa de este grafo. Se puede ver que si elijo cambiar de partido a uno, voy a tener que cambiar todos los pertenecientes a su componente conexa sí o sí. Por lo tanto por cada componente conexa voy a guardarme el costo de cambiar de partido a todos los pertenecientes a la misma y la diferencia en cantidad de personas que genera. Calculado esto se puede hacer una dinámica estilo mochila, donde la capacidad es el presupuesto, los objetos son cada componente conexa y quiero maximizar la cantidad de personas en el primer partido. Dar vuelta todo y hacer lo mismo para el otro partido.

F - Fence the vegetables fail

Mostrar Solución

Recordemos que cuando un punto esta dentro de un polígono cualquier semirecta que salga de ese punto se interseca con el poligono una cantidad impar de veces. Nuestro algoritmo "tira" semirectas horizontales hacia la izquierda. Para eso hacemos un sweep line de izquierda a derecha. Por cada punto (x, y) veo cuantas rectas verticales pasaron por ese x anteriormente. Para esto podemos usar un bit (fenwick tree) o un segment tree o hasta segment tree con lazy.

G - Galactic taxes

Mostrar Solución

Cada camino es una recta en el gráfico costo en función del tiempo (pues sumo los A y B de las artistas que lo componen). Si dibujamos imaginariamente las rectas de todos los caminos posibles, para cada t nos quedaríamos con la que menor costo tiene. Si miramos la grafica notamos que tiene un solo máximo (parecido a la idea del convex hull trick, buscar). Por lo cual podemos hacer ternary search sobre la respuesta. En cada paso se fija el t y se hace un Dijkstra.

H - Height map

Mostrar Solución

Las caras que siempre van a estar van a ser la de abajo y la de los cuatro costados. Para las caras superiores (horizontales) podemos hacer un flood fill (dos casillas están conectadas si son adyacentes y tienen la misma altura) y contar la cantidad de regiones.
Para las caras laterales paralelas al eje x podemos hacer un algoritmo para cada par de filas adyacentes . Vamos de izquierda a derecha y tenemos tres estados: la cara actual mira hacia al norte, la cara mira hacia el sur, o no hay cara(las casilla del norte y la del sur están a igual altura). Cuando cambio a alguno de los dos primeros sumo 1 a la respuesta.
Para calcular las verticales paralelas al eje y simplemente giro 90° y hago el mismo algoritmo.

También se puede resolver contando aristas y vértices y usando la propiedad C = A-V+2

I - Identifying tea

Mostrar Solución

Trivial de la competencia

J - Just a bit sorted

Mostrar Solución

Este problema era el hard de la competencia. Hay dos formas de encararlo. Una idea es con Programación Dinámica pensando que pasa cuando se agranda K pero no sabemos de que manera se resuelve. La otra es hacer fuerza bruta con los casos más pequeños e intentar buscar una formula que determine un elemento de tabla (N,K) dado los anteriores. Nosotros estuvimos un rato intentando esto último pero no nos salió en la competencia. La formula es complicada pero no imposible de hallar. Usando está formula (no es necesario) se puede incluso reducir la complejidad a N lgN, o hacer programación dinámica en N^2. Notar que para Q = N y Q > N el número de posibilidades es él mismo.

K - Keep it energized

Mostrar Solución

Definimos f(i) = mínimo costo de llegar desde i hasta el final. La respuesta al problema es f(0).

Al comienzo f(0...n-1)=inf y f(n) =0. Recorremos en orden descendente de nivel los shops. Para cada shop=(L, S, C) calculo la máxima posición p a la que puedo llegar desde L con energía S usando búsqueda binaria. Luego cuando tomo en cuenta este shop puedo llegar desde L a cualquier posición en [L, p].

En particular me conviene saltar a la posición que me cueste menos llegar al final. Por lo que el costo mínimo usando este shop es C+min f(i), con i=L...p.
Para cada nivel me quedo con el shop que me genere menor costo. Se puede implementar usando un RMQ sobre los f(i) (existen otras soluciones).

Logramos que nuestra universidad fuera sede por primera vez! Muchas gracias a Exequiel Rivas por la organización.

Problemset

http://torneoprogramacion.com.ar/wp-content/uploads/2015/09/pruebaTAP2015.pdf

Scoreboard Final

http://torneoprogramacion.com.ar/2015/09/27/resultados-tap-2015/

Juez Online

A: http://coj.uci.cu/24h/problem.xhtml?pid=3381
B: http://coj.uci.cu/24h/problem.xhtml?pid=3382
C: http://coj.uci.cu/24h/problem.xhtml?pid=3383
D: http://coj.uci.cu/24h/problem.xhtml?pid=3384
E: http://coj.uci.cu/24h/problem.xhtml?pid=3385
F: http://coj.uci.cu/24h/problem.xhtml?pid=3386
G: http://coj.uci.cu/24h/problem.xhtml?pid=3387
H: http://coj.uci.cu/24h/problem.xhtml?pid=3388
I: http://coj.uci.cu/24h/problem.xhtml?pid=3389
J: http://coj.uci.cu/24h/problem.xhtml?pid=3390
K: http://coj.uci.cu/24h/problem.xhtml?pid=3391

Soluciones

Problema A – AM/FM

Mostrar Solución

Supongamos que tenemos el punto óptimo. El punto óptimo está en la intersección de áreas de algunas estaciones. Cualquier punto que tome que pertenezca a esa intersección va a ser igual de óptimo. Tenemos dos casos:

• Si la intersección es un círculo, entonces en el centro hay una estación por lo que puedo mover el punto en el centro de esa estación.
• Si la intersección no es un círculo, entonces está formada por la intersección de dos o más círculos no concéntricos. Puedo mover el punto al punto en donde algún par de circunferencias de esta intersección se cruzan.

Hemos demostrado que solo basta con probar los centros de las estaciones O(N) y las intersecciones entre las circunferencias O(N^2) como posibles candidatos. Solo resta buscar con fuerza bruta O(CANDIDATOS*N) cual es el candidato con más estaciones.

Problema B – Buen kilo de pan Flauta

Mostrar Solución

Debemos hacer búsqueda binaria sobre la respuesta. Si fijamos una cantidad mínima de triángulos en cada división, podemos ir tomando de manera greedy en O(10^6) y ver si es posible o no lograr tal cantidad mínima.

Problema C – CompuTenis recargado

Mostrar Solución

Solo tenemos que simular el partido.

Problema D – Directo a la felicidad

Mostrar Solución

Para cada componente del grafo, o bien podemos poner estadios en todas las ciudades o bien agregar rutas y transformarlo en completo. Simplemente elegir la opción de menor coste y sumar el resultado de cada componente.

Problema E – Empaquetamiento perfecto

Mostrar Solución

Próximamente! (en unos días, vayan pensando en estados y exponenciación de matrices)

Problema F – Favoritismo inducido

Mostrar Solución

Planteamos una dinámica sobre el árbol. Dado un nodo v pintado de color c, cual es el índice de disturbios mínimo que se puede lograr mirando solo el subárbol de raíz en v? Esto es f(v, c). Para calcular f(v, c), simplemente para cada hijo de v, pruebo asignarle cada uno de los colores y obtengo el mínimo de su subárbol (acá uso f recursivamente) y me quedo con el mínimo.

Problema G – Genética alienígena II

Mostrar Solución

El proceso de convertir la cadena sería ir matcheando un sufijo de la primer cadena y un sufijo de la segunda. El sufijo de la primer cadena se va a ir invirtiendo ocasionalmente. Una primera observación es que si sabemos cual es el sufijo de la primer cadena, podemos recuperar el sufijo de la segunda porque ambas tienen la misma cantidad de carácteres.

El truco está en notar que el sufijo de la primer cadena en cualquier estado es una substring de la cadena con la que empecé (que puede estar invertida). Por lo tanto para describir el estado solo basta con un (i, j, inv) donde inv es 1 o 0.
Con esto puedo recuperar el sufijo de la segunda haciendo j-i+1. Ya pudiendo describir el estado eficientemente podemos probar todo haciendo una dinámica, que tome un estado y diga cual es la mínima cantidad de movimientos necesarios.

Problema H – Haciendo la tarea

Mostrar Solución

La cantidad de restas es pequeña. Podemos simular el proceso e imprimir cuantas restas hicimos.

Problema I – Invasión extraterrestre

Mostrar Solución

Como N<=1000 podemos agregar todos los sufijos de ambas cadenas a una lista. Imaginemos primero que eso de que cambian de frecuencia no pasa, es decir sólo tenemos que matchear. Tenemos todos los sufijos y los ordenamos. Para cada sufijo i de una palabra, el siguiente sufijo (i+1) va a ser con el que más caracteres tenga en común al comienzo (no existe otro sufijo que tenga más carácteres al comienzo en común con i que i+1). Si el siguiente sufijo es de la otra palabra, los caracteres que tengan en común al comienzo determinan una subcadena en común entre ambas cadenas. Prestemos atención, para cada posición de la primer cadena (en realidad para cada sufijo) estamos encontrando la subcadena con más caracteres en común. Osea que mirando todas las posiciones (sufijos) y sacando un máximo ya tengo la respuesta.

Por último, para lidiar con los cambios de frecuencias hay que ‘normalizar’ los sufijos. Antes de agregar el sufijo a la lista lo transformo. Voy de izquierda a derecha. Si ese caracter no apareció antes la transformo la menor letra que no haya sido usada. Si el carácter ya apareció, la transformo a la letra que había usado antes.
Ej:
zzzybbx -> aaabccd
azmmd -> abccd
Luego aplico el algoritmo ya explicado. Se provee una implementación muy clara realizada por Emilio Lopéz http://sprunge.us/SZIW?c++

Problema J – Jugando con Piedras II

Mostrar Solución

Lo esencial es resolver el problema primero para 1, 2 y 3 pilas, luego la estrategia general se puede deducir viendo esos tres casos. Sea E la estrategia de jugar inverso a la última jugada de tu oponente. Es decir, sacar N piedras de la pila que tu rival saco 1, sacar N-1 de la que tu rival saco 2, etc. Si el segundo jugador puede ganar siguiendo la estrategia E - es decir luego de k turnos de sacar N+1 (entre ambos) el primero no puede jugar – usa esa estrategia. Si no puede, es decir el primero tiene una jugada ganadora JG que impide al 2do seguir con la estrategia E, hagamos que el primero empieze con JG y siga la estrategia E con las jugadas del segundo. Es claro que llegamos a la situación donde el 2do no podía jugar y en este caso el primer jugador tiene asegurada la victoria.

Problema K – Kimetto, Kipsang y Kipchoge

Mostrar Solución

Tenemos que mantener un par de cosas. Primero, para cada posición i, cual es la siguiente posición j tal que S[i]=S[j], llamemosle next (next(i)=j). Podemos usar varios sets para hacer esto. Lo mismo para la posición anterior, ant(j)=i.
Ahora dada una query E k podemos reducir el problema a buscar en el rango [0, k] cual es el máximo ant. Si mantenemos los valores de ant en un arreglo, sacar el máximo en un rango se puede hacer eficientemente con un segment tree!
Sólo resta ver como actualizar los next y los ant en cada query.