Soluciones de la Fase 2 de la Liga de Programación omegaUp

  1. Problema A

Las siguientes observaciones son claves para resolver el problema.

  1. Si p \leq n, entonces (w % p) < n. Así que el máximo residuo posible es n - 1.
  2. Si w satisface la condición del enunciado, entonces hay n - 1 diferentes residuos, luego los residuos son un subconjunto de n - 1 elementos, de la colección \lbrace 0, 1, \ldots , n - 1\rbrace.
  3. El mínimo común múltiplo de 1, 2, \ldots , n es mayor o igual al producto de los primos menores o iguales a n.
  4. El producto de los primos menores o iguales a 50 es mayor a 10^{18}

Veamos el caso donde 0 no forma parte de los residuos. De 1, vemos que

w % n = n - 1

w % n - 1 = n - 2

\ldots

w % 2= 1 .

Entonces w + 1 es un común múltiplo de 2, 3, 4,  \ldots,  n.

(*) Luego, de la observación 3 vemos que

mcm(2, 3, 4,  \ldots,  n) \geq P_n

 Donde P_n es el producto de los primos menores o iguales a n.

(*) Pero P_{50} > 10^{18}. Así que si w + 1 es un común múltiplo de 2, 3, 4,  \ldots,  n entonces n \leq 50.

Ahora el caso donde 0 sí forma parte de los residuos. Se sigue que existe 1 < k \leq n tal que w % k = 0. Con la misma lógica, de 1, vemos qué

w % k - 1 = k - 2

\ldots

w % 2= 1 .

Con ayuda de  (*), vemos que k \leq 50.  ¿Cuál es el orden de los residuos mayores a k?. Para esto, consideremos el mismo orden que usamos en el caso donde 0 no forma parte de los residuos.

El residuo k - 1 que originalmente pertenecía a k tiene dos direcciones: ser el residuo de un numero mayor que k, o k - 1 es el residuo que queda  descartado.

Sea M - 1 el residuo que queda descartado, entonces w + 1 debe ser común múltiplo de n, n - 1, n - 2, \ldots , M + 1, y para esto,

(w + 1) \geq n * (n - 1) * (n - 2)  * \ldots * (M + 1)

Lo cual sería imposible si n - M  \geq 50.

Ahora, si no descartamos los residuos de k + 1, \ldots , k + 50, entonces w + 1 \geq  (k + 1) * \ldots  * (k + 50) lo cual sería de nuevo imposible.

Por lo tanto, M + 50 > n y M - 50 < 1.

De modo que, si n > 100, la respuesta es “No”.  El problema ahora se limíta a n \leq 100 y w \leq 10^{18}.

Para éste problema, podemos guardar todos los residuos de w con los números menores o iguales a n en una estructura que nos maneje operaciones básicas de conjuntos, como un set. Usando el set, la respuesta es “Si”, si el tamaño del set después de añadir los residuos es n - 1, y “No” en caso contrario.

Tratemos cada query de manera independientemente, y nos tomamos a_1, a_2, \ldots, a_k como los puntos dados en la query.

El problema es equivalente a encontrar un círculo con el menor radio r posible, tal que todos los puntos de la query están dentro de él.  La respuesta sería el radio r.

Él cuál es un problema equivalente a encontrar el menor radio r tal que existe al menos un punto contenido en cada círculo con centro a_1, a_2, \ldots a_n y radio r.

Si dicho punto p existe, entonces existe al menos un par de círculos que se intersecten en algun punto T. Por supuesto, la distancia de p a T es menor o igual a r.

Por lo tanto, la respuesta puede ser encontrada con una búsqueda binaria.

  1. Fíjamos el radio r, el cual mandamos a la búsqueda binaria.
  2. Enumeramos los k círculos.
  3. Encontramos y enumeramos las intersecciones para cada par de círculos.
  4. Para cada intersección, recorremos cada centro. Si hay un centro a_ique tiene una distancia menor o igual a r entonces el menor radio que buscamos sí es menor o igual a r.

El costo de cada chequeo en la búsqueda binaria es O(k^3). Y la búsqueda binaria tiene un costo de aproximádamente 50 operaciones. Pero precalculando las soluciones, de 4, para todos los l puntos antes de contestar las preguntas, reducimos el costo del chequeo a O(k^2), lo cual ya es suficiente para resolver el problema.

Lo que buscamos, es la cantidad de subconjuntos tales que su \&  es igual a 0. Esta cantidad puede verse como la cantidad de subconjuntos totales, menos la cantidad de subconjuntos tales que su \& es diferente de 0. Ahora, esta cantidad puede verse como la cantidad de subconjuntos cuyo  \& tienen exactamente un bit prendido, más la cantidad de subconjuntos cuyo \& tienen exactamente dos bits prendidos, \ldots, más la cantidad de subconjuntos cuyo \& tienen exactamente 20 bits prendidos (esto ya que 10^6 \leq 2^{20}).

Para esto usaremos el principio de inclusión – exclusión. De modo que la cantidad que buscamos esta dada por

S_ 0 - S_1 + S_2 - S_3 + \ldots + S_{20}

Donde S_i nos dice cuantos subconjuntos tienen  un ~and~ con al menos i bits prendidos.

Ahora, S_i puede ser calculado con la ayuda de una SOS (Sum Over Subsets) DP.

Para esto,  sea mask alguna máscara de bits en [1, 2^{20}], y definamos m como el ~and~ de algún subconjunto del arreglo, tal que mask \& m = mask. Es decir, mask es una submáscara de m. Entonces, DP[mask] nos dice cuántas diferentes m existen. (dos m se consideran diferentes, si las posiciones de los elementos en el arreglo que la componen no son todas iguales). Está DP puede calcularse de la siguiente manera.

  1. Los casos base los formamos añadiendo la cantidad de ocurrencias de x en el arreglo, a DP[x].
  2. Fíjamos bit \in [1, 20], de izquierda a derecha.
  3. Para cada mask en [0, 2^{20}], tal que mask tiene el bit-ésimo bit apagado  (mas formalmente, mask \& (1 << bit)  = 0 ) se hace la transición DP[mask | (1 << bit)] += DP[mask].

De modo que S_i = 2^{DP[m]}, para cada m una máscara con al menos i bits prendidos.

Sean p_1, p_2, \ldots, p_m las posiciones de la cadena en donde hay un 1.

Definimos r cómo la posición donde yace la rana, y b como la cantidad de brincos que ha dado hasta el momento. Inicialmente, r = p_1 y b = 0. La respuesta puede encontrarse mediante siguiente algoritmo.

  1. Encontrar j tal que p_j - r \leq k y p_{j + 1} > k
  2. Hacemos

    b = b + 1 y r = p_j

  3. Repetimos mientras r \neq p_m.

La respuesta final es b. El algoritmo se puede implementar con complejidad lineal usando la técnica de two pointers (usando r y j como los pointers).

Rescatando la cantidad de ocurrencias para cada vocal (no hay que olvidarse de contar las mayúsculas) mientras recorremos la cadena, estamos listos para imprimir las tres respuestas. Las cuales son

(a)  Tamaño de la cadena.

(b)  Suma de las ocurrencias de cada vocal.

(c)  Imprimir la cadena de derecha a izquierda.

Salvemos los dos vectores dados a_1, a_2, \ldots , a_n y b_1, b_2, \ldots , b_n, y generemos un nuevo vector c_1 = (a_1 + b_1), \ldots, c_n = (a_n + b_n). La solucion es imprimir c_1, c_2, \ldots, c_n.

 

Soluciones de la Fase 1 de la Liga de Programación omegaUp

Para este problema, consideramos un arreglo de ocurrencias O sobre los elementos del arreglo. De modo que la respuesta está dada por

\sum\limits_{i=A}^B O_{i}

Si consideramos el mismo arreglo de ocurrencias O sobre los elementos del arreglo, la respuesta está dada por O_k.

Podemos generar todos los elementos de la secuencia de Fibonacci hasta 30000, y guardarlos en un mapa M, de modo que M_k = 1 si k es un elemento de Fibonnaci, y M_k = 0 en caso contrario. Generamos la respuesta simplemente iterando desde i = 4 hasta i = N - 1, e imprimimos i si M_i = 0.

La clave para este problema, es usar variables que no provoquen un desbordamiento, por ejemplo, unsigned long long. Luego, es conocido que la serie de Fibonacci crece rápidamente, lo suficiente, como para generar la secuencia con todos sus elementos menores o iguales a N, guardando por cada uno su respectiva posición en ella. Por lo tanto, basta con checar si N es un elemento, e imprimir su posición. En caso de no serlo, imprimimos -1.

Este tipo de problema es conocido como straight-forward. Podemos guardar las estaciones de radio, y checar cuál estación es la mas cercana a la frecuencia dada, con una simple resta. En caso de haber dos estaciones con la misma distancia, la respuesta es la mayor. Solo debemos cuidar que la frecuencia esté dentro del rango permitido.

En este problema lo que tenemos es un grafo dirigido acíclico con aristas pesadas (intuitivamente, es un árbol, sin la propiedad de que cualquier par de nodos estan conectados por un único camino).
Los vértices son los eventos temporales, las aristas son dirigidas de p_i a i, y su peso es d_i. Además, cada vértice contiene un valor extra r_i. Un grafo que podemos asociar al primer caso de ejemplo es el siguiente.

Sean v_1 y v_k dos vértices distintos, tales que v_1 es ancestro de v_k. Es decir, existe un camino v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_k en el grafo. Definimos S(v_1, v_k) como

\sum\limits_{i=1}^{k - 1} d_{v_i}

 

Es decir, la suma de los pesos en las aristas del camino.
De modo que el problema se convierte en: Para cada vertice v, contar cuántos vértices u en su “subárbol” \; existen tales que

r_u - S(v, u) \geq 0

Porque esto siginifica que tenemos suficientes segundos para viajar por el tiempo desde u hasta v.

Consideremos un arreglo E, donde la entrada E_v guarda cuántos descendientes u de v satisfacen

r_u - S(v, u) \geq 0

Pero

r_u - S(p_v, u) < 0

Donde p_v es el padre de v. Si v = 0, entonces no hace falta considerar a su padre, puesto que no podemos viajar por el tiempo a algún ancestro de 0 (ya que ni siquiera existe alguno).

En otras palabras, E_v guarda cuántos descendientes de v llegan a lo mas al vértice v.

También consideremos un arreglo D, donde la entrada D_v guarda cuántos descendientes u de v satisfacen

r_u - S(v, u) < 0

Es decir, D_v guarda cuántos descendientes de v no pueden llegar al vertice v.

Y además mantengamos un arreglo T, donde la entrada T_v guarda el tamaño del “subárbol” de v (incluyendo a v). En otras palabras, cuántos descendientes tiene v en total mas el mismo.

Por lo tanto, la respuesta final para el vértice v está dada por

(T_v - 1) - \sum\limits_{v \rightarrow u} (E_u + D_u)

donde u es un hijo directo de v.
Ya que esto calcula cuántos descendientes de v si pueden llegar a v.

Para el cálculo de nuestros arreglos, hacemos una dfs sobre el “árbol”  (partiendo del vertice 0). Para cada vértice u, hacemos una búsqueda binaria sobre un arreglo que mantenga la suma acumulada de los costos sobre las aristas que forman parte del camino de 0 a u, que nos devuelva el máximo ancestro v al que podemos llegar desde u.  Lo que nos dice que  E_v actualiza su valor a E_v + 1 (inicialmente, E_1 = E_2  = \ldots = E_n = 0). Esto se puede hacer usando un arreglo global. La idea es añadir la suma acumulada, luego explorar recursivamente el subárbol de u, y luego quitar la suma acumulada que añadimos. Esto es particularmente sencillo si usamos un vector de la STL para el arreglo global.

El arreglo T se calcula facilmente en la misma dfs, ya que

T_v = 1 + \sum\limits_{v \rightarrow u} (T_u)

Ahora podemos generar D, al estilo de programacion dinámica usando E. Notemos que

D_v = \sum\limits_{v \rightarrow u} (E_ u + D_u)

Lo que se puede hacer en la misma DFS.

Por lo tanto, nuestro algoritmo tiene complejidad O(Nlog(N)).

Primero reescribamos la expresión dada como

k = \dfrac{xy}{x + y}

De donde podemos despejar y como

y = \dfrac{xk}{x - k}

Sin perdida de generalidad, supongamos x \leq y, entonces se tiene

x \leq \dfrac{xk}{x - k}

x^2 \leq 2xk

x \leq 2k

Por lo tanto, podemos iterar x desde 1 hasta 2k, obtenemos y, y verificamos que k = \dfrac{xy}{x + y}, y > 0.

Guardamos las parejas que satisfazcan dichas condiciones y las imprimimos en el orden requerido, cuidando no repetir alguna respuesta.

Lo que nos deja con un algoritmo de complejidad O(k).

Una solución alternativa es la siguiente:

Te puedes dar cuenta que x, y > k, entonces el problema se convierte a  buscar a y b que cumplan

\dfrac{1}{k} = \dfrac{1}{k + a} + \dfrac{1}{k + b}

con a,b > 0. Si simplificas la igualdad llegas a que k^2 = ab, así que todo se reduce a encontrar las parejas de divisores a, b de k^2.  Lo que deja también un algoritmo de complejidad O(k).

Nota: Agradezco a José Tapia y a Carlos Galeana por su colaboración en el problema G.

Solución a “Splatoon”

Problema: Splatoon.

Este problema pide llevar a un inkling desde el inicio de una calle hasta el final siguiendo sus reglas de movimiento.

Ignoremos por un momento el hecho de que los inklings pueden pintar el piso y con ello alterar la calle en donde se realiza la carrera. Si los inklings no tuvieran esta habilidad, se puede hacer un algoritmo de fuerza bruta intentando todas las operaciones posibles, es decir, hacer una búsqueda en amplitud para encontrar el camino más corto, en donde el estado está representado únicamente por la posición en donde se encuentre el inkling.

Recuerda que en las búsquedas es importante marcar visitados para que la complejidad del algoritmo no se vuelva exponencial.

Para cada posición, se tienen dos posibles operaciones, saltar, o caminar, ambas toman 1 segundo y la distancia a la que se llega depende directamente del color sobre el que se está parado. El movimiento de saltar es muy fácil pues solo hay una casilla donde se puede caer, pero el movimiento de avanzar difiere cada vez pues depende directamente del color de las siguientes casillas.

Es posible hacer un ciclo para ver hasta donde puedes llegar avanzando desde la casilla en donde estás, y agregar a la búsqueda el lugar más lejano a donde puedas llegar. Sin embargo, si únicamente registramos la última casilla a donde se puede llegar, casos como el siguiente se nos escaparán:

En la solución superior, primero se avanza todo lo que se puede en la pintura naranja hasta llegar a la casilla azul, de ahi ya sea saltando o avanzando únicamente se puede llegar a la casilla blanca, y de ahí, no importa lo que hagas, te tomará dos segundos llegar al final.

En cambio, en la solución inferior, se avanza solo 3 casillas en la pintura naranja, lo cual es 1 casilla menos del máximo, de ahí se hace un salto el cual nos deja de nuevo en pintura naranja, desde donde podemos llegar caminando hasta el final en un total de tan solo 3 segundos, 1 segundo menos que la solución anterior.

Por lo tanto, no es suficiente visitar la distancia máxima, también hace falta visitar la distancia máxima – 1. Si intentamos hacer cosas similares con otro color de pintura, o más deteniéndonos todavía más atrás del máximo, no hay realmente ninguna ventaja, por lo que el caso presentado anteriormente es el único caso especial.

Una búsqueda en amplitud bien hecha que considere este caso sacará 30 puntos, una que no considere este caso sacará únicamente 5 puntos. Da perfectamente en tiempo y memoria porque a lo más tendremos un total de 1000 estados.
Sin embargo, la parte interesante de este problema es que los inklings son capaces de alterar el estado de la calle usando la pintura que traen en su tanque para poder recorrer más rápido la calle, utilizando hasta D disparos de tinta.

En este caso, necesitamos agregar una segunda dimensión al estado de nuestra búsqueda, ahora no sólamente es suficiente con guardar el lugar en donde estamos, sino que es necesario guardar también cuanta tinta queda en el tanque. En este caso, agregamos una operación más, la cual es pintar, la cual cuesta 0 segundos, nos avanza 0 casillas y nos quita una unidad D de pintura.

Si hacemos esto, nuestro espacio de búsqueda crece del N que era en la solución de 30 puntos, a N x D, lo cual es 1000 x 1000 y aún da en tiempo y memoria.

No obstante, la operación de pintar altera el mapa, por lo que si no guardamos también en el estado que las casillas siguientes ahora son de otro color, pintar no servirá de nada. Podríamos agregar una dimensión más a la búsqueda para considerar este caso, pero esto solo le agregaría complejidad innecesaria a la búsqueda.

La clave está en que pintar toma 0 segundos, por lo que podemos convertir la operación de pintar en una operación compuesta, que sea pintar y avanzar.

Pintar y avanzar toma 1 segundo, y nos permite avanzar 4 casillas hacia adelante siempre, por lo que hacer una operación de pintar y avanzar nos lleva del estado (i, d) al estado (i + 4, d – 1) con un costo de 1 segundo.

El detalle con esta solución, es que estamos ignorando de nuevo el caso especial explicado en la solución de 30 puntos, por lo que si se nos olvida que es posible ahorrarnos un segundo en ciertas ocasiones, sacaremos entre 35 y 90 puntos dependiendo de la implementación.

Para sacar los 100 puntos, es necesario agregar una operación más, la cual es pintar, avanzar y saltar, la cual nos lleva del estado (i, d),  al estado (i + 6, d – 1) con un costo de 2 segundos. Y como esta operación toma 2 segundos en vez de tan solo 1, no es suficiente con utilizar una cola común y corriente para hacer la búsqueda en amplitud, sino que es necesario utilizar una estructura de datos más avanzada, como una cola de prioridad o un montículo que nos ayude a ordenar los estados y elegir siempre con el tiempo más pequeño.

 

Solución a “Los Chocolates del Agente Nieves”

Problema: Los Chocolates del Agente Nieves

En este problema tenemos un tubo de chocolates los cuales se van a vender uno cada día, pudiendo vender únicamente los que están en ese momento en los extremos. El precio por vender un chocolate es igual al precio base de chocolate multiplicado por el número de días que se han vendido chocolates (empezando en 1).

El objetivo es encontrar la mayor ganancia posible al vender todos los chocolates.

 

Si lo quisiéramos resolver como una búsqueda, ¿qué tendríamos que considerar? En una búsqueda, nos importa obtener dos cosas, el espacio de búsqueda (es decir, cómo estará representado nuestro estado y qué valores puede tener), y las operaciones en nuestra búsqueda.

En cuanto a nuestros estados en la búsqueda, nos importa saber qué chocolates aún tenemos disponibles y cuántos días han pasado. Podríamos empezar teniendo N valores booleanos por cada chocolate y un número para saber cuántos días han pasado, por ejemplo, si tenemos 3 chocolates y aún no vendemos nada, tendríamos el estado (1, 1, 1, 1), si ya vendimos el primer chocolate, tendríamos (0, 1, 1, 2), si vendimos el tercer chocolate tendríamos (1, 1, 0, 2) y si vendemos los chocolates 1 y 2, tendríamos (0, 0, 1, 3). Sin embargo, esta representación es un poco inútil, ya que en el peor de los casos, tendríamos 1000 chocolates, lo cual hace un estado de 1000 posibles valores.

Podemos mejorar esto solo guardando únicamente los índices a los extremos del tubo, ya que ya sabemos que aún tenemos todos los chocolates entre estos dos valores. Eso transforma los estados anteriores a los siguientes estados respectivamente: (1, 3, 1), (2, 3, 2), (1, 2, 2). y (3, 3, 3). Esto vuelve al estado muchísimo más manejable, pues cada valor puede valer únicamente entre 1 y 1000.

Ya que tenemos nuestro estado, definimos las operaciones que hay que hacer para ir entre estado y estado, y estas operaciones son únicamente 2, vender el chocolate de la izquierda, o vender el chocolate de la derecha, si estamos en el estado (1, 3, 1) y vendemos el de la izquierda, nos lleva al estado (2, 3, 2), y si vendemos el de la derecha, nos lleva al estado (1, 2, 2). Podemos continuar estas instrucciones recursivamente sobre los estados que resulta y generar un árbol de búsqueda:

Una vez teniendo el árbol de búsqueda, podemos proceder a darle valor a cada uno de los nodos. Del nodo inicial (1, 3, 1), si decides vender el chocolate de la izquierda, obtendrás una ganancia igual a lo que te de el nodo (2, 3, 2) más el precio del chocolate 1 multiplicado por el número de días, que en este caso es 1, y si decides vender el chocolate de la derecha, la ganancia será lo que de el nodo (1, 2, 2) más el precio del chocolate 3 (múltiplicado por 1). De las dos opciones, tomaremos el máximo.

Llenemos ahora el resto del árbol de búsqueda con estos datos:

De aquí podemos ver dos cosas, la primera es que los nodos de hasta abajo, que son nuestros nodos hoja, tienen el mismo valor en el chocolate izquierdo como en el derecho, por lo que el valor máximo que podemos obtener de ellos es el precio de ese único chocolate por el número de días que llevamos. Y la segunda cosa es que tenemos nodos repetidos, por lo que cuando hagamos nuestra búsqueda, necesitamos guardar cálculos que ya hayamos hecho para no calcular un mismo estado más de una vez.

Nuestro árbol de búsqueda ya está terminado, así que es hora de convertirlo a una función matemática. Nuestra función recibe como entrada un estado, en este caso el chocolate más a la izquierda que nos queda, el más a la derecha y el nivel en el que estamos, y dado lo que aprendimos de nuestro árbol de búsqueda, regresará el siguiente valor:

Con esto, y considerando que debemos evitar repetir valores duplicados, es más que suficiente para resolver el problema con el método que más te guste, ya sea dinámica o memorización, aunque hay un pequeño problema para guardar los valores visitados.

Vamos a necesitar un arreglo de 1000 x 1000 x 1000 si es que queremos guardar un arreglo que se identifique de esta forma:

arreglo[izquierda][derecha][nivel]

Y esto es mucho más de lo que cabe en memoria, por lo que tenemos que encontrar una forma de reducir la memoria que necesitamos.

Lo que nos tenemos que dar cuenta es que la variable nivel es innecesaria, pues puede calcularse utilizando el número de chocolates que nos quedan en el tubo y el número de chocolates que teníamos originalmente:

nivel = total – chocolates_en_el_tubo + 1

Y para calcular el número de chocolates que nos quedan en el tubo solo se necesitan el índice del chocolate más a la izquierda, y más a la derecha, que ya tenemos en nuestro estado.

chocolates_en_el_tubo = derecha – izquierda + 1

Despejando:

nivel = total – derecha + izquierda – 1 + 1

nivel = total – derecha + izquierda

De esta forma, podemos eliminar el nivel de todos nuestros estados y cambiar el valor de nivel de todas las fórmulas por el valor de arriba. Esto simplifica nuestro arreglo de visitados de 1000 x 1000 x 1000 a un arreglo de tan solo 1000 x 1000, lo cuál es suficiente en tiempo y memoria.

 

Solución a “Contraseña Binaria”

Concurso: Preselectivo para la IOI 2015, Etapa 1, Problemset 7
Autor: Orlando Isay Mendoza Garcia
Fuente: Christian Adan Hernández Sánchez

Podemos ayudarnos de la imagen para comprender mejor esta explicación:

En ella aparecen de forma descendente a la izquierda los números pares comenzando desde el dos, y su representación binaria a la derecha. En la parte superior aparece el valor de cada cifra en decimal.

Tomando en cuenta el límite del problema, sabemos que si sumamos B(i) para cada par menor o igual a N, en el peor de los casos tendríamos que realizar 500,000,000,000,000 veces la función. Aún si lograramos calcularla en una operación nuestro programa excedería el tiempo límite.

En cambio, haciendo cálculos notamos que:
2^{50} \approx 1,000,000,000,000,000. Lo cual significa que a lo más habrán 50 columnas en la tabla (ya que en la forma binaria cada cifra representa una potencia de 2).

Dado que sabemos que en una suma el orden de las cantidades a sumar no importa, podemos determinar que es lo mismo sumar los valores de forma horizontal, tanto como de forma vertical. Sumando los valores de las columnas solo tomaría 50 operaciones. La columna 1 podemos ignorarla ya que al ser pares los números de la lista ninguno contendrá un 1 en la última cifra.

Observando la siguiente imagen, vemos que la columna C se forman grupos de tamaño C (por ejemplo, en la columna 4 se forman grupos de cuatro elementos),que contienen una la mitad de 1s y la otra de 0s. También podemos ver que en la columna 2 no hay 0s antes del primer grupo, en columna 4 hay un 0, en la que sigue hay 2, luego 4,etc (área en color gris). Podemos notar que ese espacio aumenta en base a potencias del dos.

Teniendo el número N habrán N / 2 números en la lista. Para calcular la cantidad de grupos completos que se forman en cada columna dividimos N menos el espacio lleno de ceros en esa columna, entre el número de la columna en el que estemos; a su vez, esta cantidad la multiplicamos por, el número de la columna entre dos. Sin embargo, puede que nos falten de contabilizar los 1s que pudieran estar en un grupo que no se completo. Esto se arregla sumando a lo anterior, el mínimo entre el resto de la división anterior y, el número de la columna entre dos.

Código:

Solución a “Poema Equino”

Concurso: Preselectivo para la IOI 2015, Etapa 1, Problemset 5
Autor: Freddy Román Cepeda
Fuente: Edgar Augusto Santiago Nieves, Freddy Román Cepeda

Los límites de este problema permitían hacer una búsqueda sobre todos los estados posibles de los caballos sobre el teclado, ya que si el estado es (\text{poema},\text{fila caballo}_1,\text{columna caballo}_1,\text{fila caballo}_2,\text{columna caballo}_2), solamente hay 100 \times (4 \times 10)^2 = 160,000 estados distintos.

Además, como el problema no pide la cantidad mínima de movimientos no hace falta hacer una BFS (búsqueda en amplitud), sino que una DFS (búsqueda en profundidad) utilizando el mismo stack del lenguaje es suficiente. Para simplificar la implementación, se podían utilizar varias observaciones. Particularmente, no importa qué caballo es el 1 o el 2, por lo que en vez de escribir código para mover a ambos basta con añadir una transición que cambie los roles de los caballos en cada estado. Esto además de simplificar la implementación sirve como una poda ya que ¡reduce la cantidad de estados a la mitad! (¿por qué?). También, se puede aprovechar que los operadores booleanos en C/C++ evalúan a 1 cuando son verdaderos y a 0 cuando son falsos, lo cual es bastante útil para indexar arreglos.

Varios competidores fallaron en su primer intento por no revisar que los caballos no podían ocupar la misma tecla al mismo tiempo. ¡Cuidado!

La siguiente solución implementa las simplificaciones descritas anteriormente.

Solución a “Carretera”

Concurso: Preselectivo para la IOI 2015, Etapa 1, Examen 1
Autor: Freddy Román Cepeda
Fuente: Edgar Augusto Santiago Nieves, Freddy Román Cepeda

Para obtener los puntos de la primer subtarea bastaba notar que las condiciones especificadas significan que hay dos bloques de coches yendo en diferentes sentidos que inicialmente no se intersectan y eventualmente lo harán, por lo que la respuesta simplemente es el máximo de los anchos de estos bloques.

Este código obtiene los primeros 30 puntos:

Para el resto de los puntos: Sea f(t) el ancho necesario para la fotografía en el segundo t. La observación crucial es que f es una función unimodal: es decir, existe un punto t_0 tal que f es decreciente a la izquierda de t_0 y es creciente a la derecha.

Computar f(t) para t fijo es trivial: basta con obtener el coche más a la izquierda y más a la derecha en el segundo t, lo cual toma tiempo O(N). Como f es unimodal, podemos utilizar búsqueda ternaria o búsqueda binaria para encontrar el mínimo de la función en tiempo O(\lg T), donde T es el tamaño del rango a evaluar. Con eso obtenemos un algoritmo con complejidad O(N \lg T), suficiente para obtener todos los puntos del problema.

El siguiente código implementa la solución anterior con búsqueda binaria.

Solución a “Químicos”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 6
Autor:  Luis Héctor Chávez (lhchavez)
Fuente: Ethan Jiménez Vargas

Éste es un problema que tiene una solución elegante y determinística pero requiere algoritmos avanzados bastante complicados. Lo bueno es que es posible aproximar a la solución utilizando fuerza bruta mediante backtracking.

El problema nos pide encontrar una manera de asignar sustancias a los tubos y después mezclarlas con las dos operaciones disponibles (suma y diferencia absoluta) para terminar con un acomodo homogéneo de sustancias: la diferencia entre el tubo con más cantidad y con menos cantidad de sustancia debe ser lo más pequeña posible. Una manera de hacerlo es proponer un intervalo [a,b] y ver si es posible asignar sustancias y aparear los tubos de manera que la cantidad de sustancia resultante de la mezcla en todos los tubos esté contenido dentro del intervalo. Para acelerar el proceso, puedes elegir los intervalos haciendo una búsqueda binaria de acuerdo a su ancho b-a, porque a fin de cuentas lo que nos pide el problema es precisamente el ancho mínimo. Para cada intervalo propuesto [a,b], podemos hacer un grafo con 2N nodos (uno para cada tubo), agregando un arco entre dos nodos A y B si A+B\in[a,b] ó |A-B|\in[a,b]. Después, buscamos un apareamiento máximo) en el grafo: buscamos el conjunto de arcos con cardinalidad máxima tal que cada nodo tenga a lo más un arco incidente. Esto se puede encontrar con el algoritmo de Edmonds (también conocido como el Blossom algorithm por la forma de los ciclos de longitud impar) en tiempo O(|2N|^4), lo cual encontraría todas las soluciones en solo un par de segundos.

Lamentablemente la implementación del algoritmo de Edmonds es bastante complicada. Como este es un problema de solo-salida y todo se vale, en vez de hacer el intento por implementarlo, utilicé la librería Boost de C++ que ya tiene muchísimos algoritmos de grafos ya implementados.

Ahora, si no se te ocurre usar el algoritmo de Edmonds o no tienes acceso a Boost, aún así puedes obtener una cantidad decente de puntos usando una heurística: podemos intentar hacer un apareamiento máximo usando fuerza bruta, rindiéndonos si el problema suena muy complicado y asumimos que no existe un apareamiento. Una fuerza bruta naïve con un contador que se decrementa cada vez que se llama la función de búsqueda es más que suficiente. Haciendo un par de modificaciones al algoritmo anterior nos da una solución que nos da el 80% de los casos bien:

Claro que si te quieres ver greedy, puedes subirle al número de intentos, pero posiblemente no haya suficiente tiempo en el concurso para que termine. Si llegas a utilizar estas técnicas “impuras”, asegúrate primero de obtener cualquier solución que te de puntos antes de subirle para encontrar mejores respuestas.

Solución a “Crucero”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 4
Autor: Saúl Germán Gutiérrez Calderón
Fuente: USACO Enero 2009 Gold

Como se puede notar, al trazar la ruta óptima del crucero se está desperdiciando mucho espacio, y daría lo mismo si expandiésemos la isla para que no se desperdiciara espacio entre la ruta y la orilla de ésta.


Si supiéramos cual es la ruta óptima del crucero para expandir la isla bastaría con hacer un Flood Fill para rellenar los espacios con agua que quedan dentro de la ruta.

Resulta que el flood fill e puede hacer aun sin conocer cuál sería la ruta óptima. Si nos ponemos a hacer todos los tipos de celdas adyacentes a la celda actual en un flood fill, nos toparemos con que solo hay 2 que permiten que la isla crezca y 1 que evita que se expanda. El resto de las celdas adyacentes no nos dice nada acerca de si tenemos que poner algo ahí o no (de momento).

Si se pone un pedazo de isla nuevo en el centro de las figura de abajo, entonces la cosa peligrosa tendría que ser rodeada de alguna manera para poder pasar, lo cual nos llevaría a tomar una ruta mas larga. Por ello, no es una buena idea poner un pedazo de isla ahí.

Si es como la de la figura de abajo,

ambos caminos tienen la misma longitud. Por ello, se puede poner un pedazo de isla ahí y esto nos simplifica el problema.

La ruta óptima no puede pasar por el cuadro del centro ya que esto sería un desperdicio de tiempo, por lo cual podemos expandir la tierra ahí.

Entonces, sólo hay que hacer todas las expansiones de tierra hasta que ya no se pueda más y después de esto se puede hacer una mano derecha para buscar la orilla de la isla que al mismo tiempo será la ruta óptima.