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
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
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
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
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
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
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
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
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
Trivial de la competencia
J - Just a bit sorted
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
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).
Uno pregunta, para la pregunta E dicen que cuando "cambio" a uno de las primeras aumento uno, pero que pasaria en el caso
ResponderBorrar2 2
10 100
5 50
para la superficie entre las dos filas ambas caras miran al sur (hacia abajo) pero son dos caras no?
Perdón, pregunta H
BorrarEstás en lo correcto. En tu caso es como que voy al estado sin cara y vuelvo de nuevo al estado, sumando uno. La condición de que empieze una "nueva cara" es un poco más complicada en realidad. Si yo tengo algo así:
Borrarx z
y w, con x > y
entonces me mantengo en el estado(es la misma cara) sii se cumple que z > w, w < x, z > y.
Tienen alguna demostracion para saber que la funcion del problema G es unimodal y se puede hacer busqueda ternaria??
ResponderBorrarProbar unimodalidad suele ser complicado. Lo mejor es aprenderlo intuitivamente: en un plano xy, dibujar muchas rectas. Luego para cada x, marcar el punto (x, y) con menor y tal que (x, y) pertenezca a una recta (este es el lower hull). Lo que te queda marcado es una función compuesta por pedazitos de las rectas originales. Ahora intenta buscar algún caso en donde la función marcada no sea unimodal.
BorrarEsa funcion que tu describes es claramente unimodal. Ahora lo acabo de entender, podemos ver cada camino como una recta At + B, ya que es la suma de todas la rectas que lo componen, y entonces nos queda una funcion unimodal para t, gracias y SUERTE para la final mundial en el 2016...
BorrarQué lástima! El E lo pensé exactamente igual, solo que no sabía como encarar le problema de la mochila, no te puedo creer. Gracias por todo!!!!!!
ResponderBorrarPodrías explicarme un poco más la solución dinámica del A?
ResponderBorraren el problema K mencionan la existencia de otras soluciones, la verdad la unica que yo vi fue esa misma, podrian por favor mencionar otra(s), y exitos en la final mundial.
ResponderBorrarHola, primero que nada felicitaciones por la clasificación al mundial. Para los que me leen, implemente una solución un poco distinta para el F. Mi solución lo único que utiliza es un set, y es parecido a una simulación un poco fastidiosa, pero it works! :D.
ResponderBorrarLa idea es la siguiente, los segmentos que nos van a interesar del polígono son los segmentos horizontales. Además ordenamos los segmentos por sus y's.
En el set (que es un set de pares de enteros) se mantienen qué segmentos con respecto X están "activos", es decir, que si pregunto inmediatamente por un punto que este en una coordenada (x',y') y ese x' está dentro de uno de los segmentos activos, entonces se considerará que esta dentro del polígono.
Fíjense que inicialmente los segmentos activos obviamente son los segmentos que son, por decirlo de una manera "el piso del polígono", y a medida que hacemos un line sweep en el eje y, pueden pasar varias cosas, o dos segmentos activos se unen, o se borrar varios segmentos activos ya que el polígono empieza a cerrarse. Esta idea es mucho mas fácil verla si dibujamos los casos de pruebas.
Por otro lado, los puntos que se preguntan si están fuera o dentro del polígono también deben ser ordenados por sus y's e ir haciendo en conjunto con los segmentos el line sweep, pues los segmentos activos, están activos hasta cierto y y luego se sigue modificando el set.
La idea es un poco difícil de explicar pero si tienen algunas dudas y quieren implementar esta idea, no duden en contactarme,
Saludos :D.