Solucionario Regional Latinoamérica 2016

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

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

Links Útiles

• 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.