Aquí va el solucionario. Recordar que si no conocen algún término o algoritmo mencionado es recomandable que dejen de leer la solución y aprendan sobre ese algoritmo antes de seguir.
Juez Online y Enunciados
https://acm.javeriana.edu.co/maratones/2016/03/Soluciones
A. Acronyms
Este era el trivial de la competencia.
B. Tobby Bones
Este tipo de problemas son clásicos problemas de Segment Tree. Para hacer este tipo de problemas se los debe tener bien claro. En el segment tree cada nodo representa un rango del arreglo, pues bien en este problema cada nodo guarda los números que aparecen en ese rango. Ahora, para poder contestar la consulta eficientemente debemos guardar estos números usando un árbol balanceado de búsqueda (por ejemplo Treap, Red-Black Tree, Splay Tree, etc).
Existe una estructura oculta dentro del estándar de C++ que implementa esto, por lo que evitamos programar uno desde cero. (ver http://codeforces.com/blog/entry/11080)
Existe una estructura oculta dentro del estándar de C++ que implementa esto, por lo que evitamos programar uno desde cero. (ver http://codeforces.com/blog/entry/11080)
C. Tobby and Query
Otro problema de segment tree. En este caso aprovechamos que los valores posibles del arreglo son pequeños. En cada nodo guardamos una máscara de bits que indica que números aparecen bajo ese rango, la operación es el or de bits(|) y luego para devolver la cantidad simplemente contamos la cantidad de bits encendidos (la función __builtin_popcount(x) suele ser útil).
D. Standard Deviation
Solo debemos trabajar las formulas. En particular conviene definir el númerador de forma recursiva (respecto a n), de esta forma precalculamos todos los posibles númeradores. Una vez hecho esto por cada query obtenemos el numerador correspondiente, lo dividimos por (n-1) y por último la raíz cuadrada.
E. Tobby and the LED display
Este problema es trivial, solo hay que hacer lo que piden sin complicarsela mucho.
F. Triangular Test II
Para este tipo de problema que parecen basarse en alguna propiedad matemática que seguramente desconocemos, conviene crear una solución bruta e intentar encontrar algo de útilidad. Si hacemos esto nos daremos cuenta que la respuesta puede ser 1, 2 o 3 (nunca más que 3). Por lo tanto generamos todos los números triangulares y todas las sumas de dos números triangulares y los vamos marcando en un arreglo de 10^6. Por cada n, si la posición correspondiente está marcada imprimimos 1 o 2, si no la respuesta es 3.
G. Tobby and the line game
La respuesta a este problema es: ((xR-xL)*(xR-xL)+(yR-yL)*(yR-yL))/6.
H. Painting the Wall
Por cada celda a pintar tenemos que decidir si la misma es pintada por una linea vertical o por una horizontal. El hecho de que tenemos que elegir entre cosas y que esas decisiones afectan a las otras decisiones nos lleva a pensar que se trata de un problema de flujo. Notemos que las lineas son horizontales o verticales, por lo que intuimos cierta bipartitud e intentamos armar un grafo. Ponemos las lineas horizontales a la izquierda y las verticales a la derecha del grafo. Luego agregamos por cada celda una arista conectando las dos lineas que le corresponden. Este grafo es bipartito.
Ahora, si miramos el problema presentado en este grafo, necesitamos seleccionar un conjunto de vértices que cubran todas las aristas. Esto se conoce como el cubrimiento mínimo (min vertex cover) y para grafos bipartitos es igual al maximum matching (ver teorema de König). Podemos generar el matching usando el algoritmo de flujo de preferencia (por ejemplo Dinic) y luego reconstruir el cubrimiento (es decir cuales son los vértices que elegimos) utilizando el teorema de König.
Ahora, si miramos el problema presentado en este grafo, necesitamos seleccionar un conjunto de vértices que cubran todas las aristas. Esto se conoce como el cubrimiento mínimo (min vertex cover) y para grafos bipartitos es igual al maximum matching (ver teorema de König). Podemos generar el matching usando el algoritmo de flujo de preferencia (por ejemplo Dinic) y luego reconstruir el cubrimiento (es decir cuales son los vértices que elegimos) utilizando el teorema de König.
I. Tobby on Tree
Este problema es una aplicación casi directa de lo que se conoce como Heavy Light Decomposition. Se recomienda leer y entender bien este tema antes de intentar hacer este problema.
La solución en sí es esta: Generamos la descomposición y por cada cadena tenemos un Segment Tree (algo muy común cuando se hace Heavy Light), usando el GCD como operación.
La solución en sí es esta: Generamos la descomposición y por cada cadena tenemos un Segment Tree (algo muy común cuando se hace Heavy Light), usando el GCD como operación.
Problem J. Tobby Stones
Este problema era difícil porque requería implementar un árbol balanceado de búsqueda, con varias cosas. En primer lugar si no tenemos la operación de dar vuelta (la de tipo 1), el problema se puede hacer con segment tree (para consultar sobre rangos) con lazy propagation (pues necesitamos generar cambios sobre rangos eficientemente). En cada nodo guardo cuantos blancos y cuantos negros hay en el rango que él cubre y la operación es la suma. Generar la operación del Lazy (es decir las alteraciones) es algo más complicado. La operación necesita poder alterar un rango y poder combinarse con otra alteración en O(1). Nosotros tomamos que puede valer 0 (no operación), 1 (flip), 2 (set white) o 3 (set black). Para el lazy necesitamos saber como se altera el valor del nodo por cada operación (lo cual es obvio) y como combinar alteraciones. Para esto último hacer una tablita de 4x4 y analizar: Si hago un set white y luego un flip es como si hubiera hecho un set black. Si hago un set black y luego un set white es como si hubiera hecho sólo un set white. Y así llenar toda la tablita y usarla para combinar las alteraciones.
Si llegamos hasta acá sólo nos queda las de tipo 1 (reverse), pero para hacer este tipo de queries necesitamos un árbol balanceado de búsqueda, podríamos hacer una sqrt decomposition pero las cotas parecen demasiado grandes para esto. El problema de dar vuelta apareció como el problema más hard del TAP 2014 (problema K). Se resuelve usando lazy propagation sobre el árbol de búsqueda. Porqué un árbol de búsqueda? Bueno podemos guardar un arreglo en un árbol de búsqueda como un conjunto de pares (posición, valor).
Recomendamos aprender a usar Treaps como árbol de búsqueda por defecto pues ellos son los más cortos y fáciles de codear. El tutorial de http://e-maxx.ru/algo/treap es muy bueno (usen el traductor de Yandex, que es mejor para el ruso). Allí explica como usar el Treap para representar arreglos, lo cual nos da la posibilidad de hacer operaciones bastante locas (como por ejemplo borrar una posición de un arreglo) eficientemente. EL Treap es una estructura muy poderosa, es posible hasta simular arreglos de 2^64 (reutilizando memoria).
Si llegamos hasta acá sólo nos queda las de tipo 1 (reverse), pero para hacer este tipo de queries necesitamos un árbol balanceado de búsqueda, podríamos hacer una sqrt decomposition pero las cotas parecen demasiado grandes para esto. El problema de dar vuelta apareció como el problema más hard del TAP 2014 (problema K). Se resuelve usando lazy propagation sobre el árbol de búsqueda. Porqué un árbol de búsqueda? Bueno podemos guardar un arreglo en un árbol de búsqueda como un conjunto de pares (posición, valor).
Recomendamos aprender a usar Treaps como árbol de búsqueda por defecto pues ellos son los más cortos y fáciles de codear. El tutorial de http://e-maxx.ru/algo/treap es muy bueno (usen el traductor de Yandex, que es mejor para el ruso). Allí explica como usar el Treap para representar arreglos, lo cual nos da la posibilidad de hacer operaciones bastante locas (como por ejemplo borrar una posición de un arreglo) eficientemente. EL Treap es una estructura muy poderosa, es posible hasta simular arreglos de 2^64 (reutilizando memoria).
K. Tobby and Seven
Como la cantidad de bits swapeados es poca, podemos probar todas las permutaciones distintas. Tienen que empezar por permutaciones que generen números altos y luego cada vez más bajos hasta encontrar una múltiplo de 7, ahí imprimirlo y cortar (pues sino da Time Limit).
Notar que necesitamos generar todas las permutaciones distintas (cada permutación que chequeamos tiene que ser diferente a la que chequeamos anteriormente). Para hacer esto podemos recorrer todas las máscaras de k bits (2^20), las que tienen un número de bits encendidos igual a la cantidad de bits encendidos de los bits swapeados del número original son permutaciones válidas.
Notar que necesitamos generar todas las permutaciones distintas (cada permutación que chequeamos tiene que ser diferente a la que chequeamos anteriormente). Para hacer esto podemos recorrer todas las máscaras de k bits (2^20), las que tienen un número de bits encendidos igual a la cantidad de bits encendidos de los bits swapeados del número original son permutaciones válidas.
L. Tobby and Prime Sum
Utilizamos una dinámica que siempre solemos utilizar, que es una dinámica sobre los digitos. Notar que si encontramos la respuesta para cuando l=0 y r cualquiera, llamemosla g(r), podemos hacer g(r)-g(l-1) y encontrar la respuesta al problema, por lo que efectivamente reducimos un parámetro de la query.
La dinámica consiste en ir "armando" cada número desde el dígito más significativo hasta el menor. En su estado lleva la posición (si estoy poniendo el primer, segundo dígito, etc) y cuanto vale la suma hasta ahora de todos los dígitos que ya puse (<=4500). En cada paso voy a probar poner cada uno de los 10 dígitos. Hay que tener cuidado de solamente generar los números <=r. Para eso agregamos una flag al estado. Cuando la flag esta activa solo puedo poner digitos menores o iguales al que tiene r en esa posición, si pongo un dígito menor entonces los siguientes digitos pueden ponerse cualquier cosa (total el número ya es menor: 1234xxx es menor a 1235010 sin importar que haya en las x) por lo que desactivo el flag.
Esta parte depende mucho de como lo implementen, pero a nosotros lo que nos quedó fue para cada posible suma de dígitos, cuantos números forman esa suma. Por lo cual generamos todos los primos <=4600 y para cada uno de ellos sumamos la cantidad de números que lo formaban.
La dinámica consiste en ir "armando" cada número desde el dígito más significativo hasta el menor. En su estado lleva la posición (si estoy poniendo el primer, segundo dígito, etc) y cuanto vale la suma hasta ahora de todos los dígitos que ya puse (<=4500). En cada paso voy a probar poner cada uno de los 10 dígitos. Hay que tener cuidado de solamente generar los números <=r. Para eso agregamos una flag al estado. Cuando la flag esta activa solo puedo poner digitos menores o iguales al que tiene r en esa posición, si pongo un dígito menor entonces los siguientes digitos pueden ponerse cualquier cosa (total el número ya es menor: 1234xxx es menor a 1235010 sin importar que haya en las x) por lo que desactivo el flag.
Esta parte depende mucho de como lo implementen, pero a nosotros lo que nos quedó fue para cada posible suma de dígitos, cuantos números forman esa suma. Por lo cual generamos todos los primos <=4600 y para cada uno de ellos sumamos la cantidad de números que lo formaban.
11 comentarios: