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.
Orale muchas gracias Martín, no tienes la solución del L?
ResponderBorrarMe había olvidado que estaba el L jeje, gracias por avisar!
BorrarExcelente Martín, cómo sacaste la fórmula del G?
ResponderBorrarA decir verdad conviene hacer la cuenta con fuerza bruta e intentar encontrar el patrón, que en este caso era muy complicada aparentemente. También notar que lo que pasara en la dimensión x no afecta a lo que pasa en la dimensión y(eso puede ser una pista para la formula).
BorrarMartín, te agradezco mucho por el análisis de las respuestas. Estoy iniciando en las competencias y se me ha dificultado poder realizar los ejercicios. Un saludo desde Colombia.
ResponderBorrarMuchas gracias Martin, de mucha utilidad el analisis de las respuestas, nos sirve para seguir practicando en el post-marathon, solo un pequeño comentario, al parecer el juez de boca no permite utilizar la función __builtin_popcount(x) por lo que tienen que hacer el conteo con una función aparte, en mi caso convirtiendo el decimal a binario, Saludos desde México.
ResponderBorrarQue raro, nosotros lo usamos varias veces con el juez Boca, estás seguro que no habrá sido un error de tu código? Si querés hacerlo a mano la forma más fácil es con operaciones de bits:
Borrarint q=0; for(int i=0; i<32; i++) q+=(n>>i)&1;
en el ejercicio D (estandar desviation) como encuentro la formula? he intentado calcular el numerador con ciclos (en vez de calcularlo normalmente, solo tomo los números impares menores a n los elevo al cuadrado y los acumulo en una variable y luego multiplico la variable acumuladora por dos) pero da tiempo limite, lo he intentado en una función recursiva pero para casos muy grandes me da java.lang.stackoverflowerror error que quizás se deba a que se repite muchos veces la recursividad y java lo toma como una recursividad infinita(aunque no la sea). entonces no se me ocurre nada mas, podrías ayudarme?
ResponderBorrarTe recomiendo hacerte casitos paso a paso con n=2, luego con 3, con 4, etc. hasta que pilles un patrón, luego verás que ese patrón es una sumatoria conocida (con la que tienes que jugar un poco) y con eso podrás resolverlo. Saludos.
Borrargracias, encontré un cierto patrón y en base a eso pre-calcule todo y ya no da tiempo limite.
BorrarHola, te agradezco que te tomes el trabajo de hacer el análisis, que es algo que no se encuentra en ningún otro lado que yo sepa, además de que está buenísimo y de que está en español (otro aspecto que no se ve casi nunca).
ResponderBorrarAdemás me gustaría agregar que existe una solución con tablas aditivas para el C. Con un array cnt[10][100000], donde cnt[i][j] indica en cada posición j, cuántas veces aparece el número i.
Aunque teniendo las plantillas del segment tree, sería también sencillo implementarlo así.