Solución a “Panoramas”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 17
Autor: Miguel Ángel Covarrubias
Fuente: Miguel Ángel Covarrubias

El problema es un Steiner tree problem (un MST pero donde sólo hay que conectar un subconjunto de nodos) pero con costo por nodo en vez de por arista. El grafo de los panoramas es un árbol más un ciclo. Para un árbol una solución es poner como raíz a s_1 y para cada s_i marcar los nodos en su camino hacia la raíz. Se puede usar DP o recursión para calcular el mínimo numero de vertices que conectan todos los nodos interesantes y pasan por la raíz para cada subárbol.

\mathrm{dp}_r=\mathrm{interesante}(r)\  \mathrm{si}\ \Sigma_h\mathrm{dp}_h=0
\mathrm{dp}_r = \Sigma_h\mathrm{dp}_h+1\  \mathrm{si}\ \Sigma_c\mathrm{dp}_h>0

h es un hijo de r. La arista extra (u,v) en el ciclo c permite usar otros caminos a lo largo de c. Tales caminos deben conectar todos los nodos en c que tengan nodos interesantes en su árbol después de quitar las aristas del ciclo E-c. Etiquetemos tales nodos con un uno y los demás nodos del c con un cero. Para E-(u,v) el ciclo sólo no cubre los últimos ceros. Para encontrar la solución sólo basta encontrar la secuencia de ceros más grande.
En el siguiente diagrama, la arista que falta es (u,v). La DP sólo no usa el último cero, pero es mejor no usar los dos ceros que están adyacentes.

  0 1
 /   \
1     0
 \   /
  1-0

Este código implementa la solución.

Solución a “Mapas de bits”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 12
Autor: Jorge Alberto González Martínez
Fuente: Jorge Alberto González Martínez

En el problema se describen dos formas de representar un mapa de bits.

La forma bidimensional es simplemente utilizar una matriz para representar los bits.
La forma por descomposición consiste en agrupar los bits similares y solo escribir el valor de los bits similares. En caso de que no sean similares todos los bits en un mapa de bits dado, se procede a dividir en cuatro secciones, imprimir la letra D y procesar cada uno de los cuartos de la misma manera, tal como se lee en la descripción del problema.

La solución a este problema consistía en programar el método descrito. Este método inherentemente está basado en la técnica de divide y vencerás.

A continuación, un pseudo-código que muestra la forma de llevar a cabo la transformación de un mapa de bits bidimensional a la forma reducida:


ReduceMapa(mapaDeBits)
Si todos los elementos en mapaDeBits son iguales
    Imprime el valor y termina
Si no
    Imprime D
    ReduceMapa(mapaDeBits.superiorIzquierdo)
    ReduceMapa(mapaDeBits.superiorDerecho)
    ReduceMapa(mapaDeBits.inferiorIzquierdo)
    ReduceMapa(mapaDeBits.inferiorDerecho)

El método para hacer la transformación inversa es muy parecido, sólo que para imprimir la equivalencia hay que comenzar con un mapa de bits bidimensional que nos sirva de variable auxiliar para hacer la conversión. Esta variable auxiliar se puede declarar de manera global y, cuando el método recursivo termine, simplemente imprimir su contenido:


AmplificaMapa(mapaDeBits, sección)
Si mapaDeBits comienza con un valor
    Rellenar sección del mapa bidimensional con el valor
Si no
    AmplificaMapa(mapaDeBits.removerPrimerElemento, sección.superiorIzquierda)
    AmplificaMapa(mapaDeBits.removerPrimerElemento, sección.superiorDerecha)
    AmplificaMapa(mapaDeBits.removerPrimerElemento, sección.inferiorIzquierda)
    AmplificaMapa(mapaDeBits.removerPrimerElemento, sección.inferiorDerecha)

La primera vez que se llama a la función AmplificaMapa se debe entregar la representación de la forma por descomposición del mapa de bits en la variable mapaDeBits y la sección que se entrega inicialmente es todo el mapa de bits. Esto puede ser manejado por filas y columnas.

A continuación se muestra una implementación en C++ que resuelve el problema. Nótese cómo se maneja la sección sobre la que se está trabajando con cuatro variables: tl_row, tl_col, br_row, br_col. El nombre de las variables proviene de top-left row, top-left colum, bottom-right row y bottom-right colum respectivamente. Representan los índices (fila,columa) de las esquinas superior izquierda e inferior derecha.

Solución a “Pista”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 14
Autor: Miguel Covarrubias
Fuente: Codeforces

Este problema es una ligera modificación del Let’s Play Osu! que apareció en la ronda 146 en Codeforces. La solución explicada la pueden encontrar en el editorial.

Para N \le 10 se pueden checar todas las 2^N configuraciones de pistas. Para N \le 1000 funciona una dinámica O(N^2), donde los estados son (posición, altura/profundidad que se lleva hasta el momento).

Les dejo la implementación de DiegoRoque como un muy buen ejemplo de una solución a este problema.

Solución a “DP Genérica”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 13
Autor: Freddy Román Cepeda
Fuente: Project Euler

Podemos tratar este problema de varias maneras distintas, 3 de las cuales discutiré en esta solución.

Análisis 1

Primero, una idea que hubiera obtenido 50 puntos.

Podemos observar que el problema es equivalente a encontrar de cuántas maneras se le puede asignar un número n_i del conjunto \{0,1,2\} a cada potencia de 2 tal que \sum_{i=0}^{\infty} n_i 2^i = x. Esto también es equivalente a encontrar cuántos números a y b hay tales que a + b = x y no haya ningún bit encendido en b que no esté encendido en a.

Consideremos la expansión binaria de a = \sum_{i=0}^{\infty} a_i 2^i y b = \sum_{i=0}^{\infty} b_i 2^i , donde cada a_i y b_i es 1 o 0. Al sumar a + b = \sum_{i=0}^{\infty} (a_i + b_i) 2^i tenemos que 0 \le n_i = a_i + b_i \le 2, como se necesita. Para contar solamente una vez cada configuración distinta de la secuencia n, añadimos la restricción de que cualquier b_i puede ser 1 sólo si a_i también lo es.

Subtarea 1

Para esta subtarea es suficiente probar todas las a y b posibles, revisando con un loop para cada bit si la condición sobre b se cumple. Este algoritmo corre en tiempo O(N^2 \log N).

Subtarea 2

Para esta subtarea podemos hacer una observación sencilla: a cada a sólo le puede corresponder una b, igual a x - a, lo que reduce la complejidad en tiempo del algoritmo a O(N \log N).

Subtarea 3

Podemos comprobar si b cumple la condición en tiempo constante utilizando operaciones de bits. Si ~a & b es igual a 0, b no tiene ningún bit encendido que a no tenga encendido. Ahora tenemos un algoritmo lineal. Desafortunadamente, ya no podemos mejorar nuestra solución fácilmente continuando con esta idea.

El siguiente código implementa esta solución:

Análisis 2

Podemos hacer programación dinámica de forma top-down. En ésta, contamos la cantidad de maneras de escribir x como pide el problema incluyendo o no cada una de las potencias distintas.

Consideremos la función f(n,p), que cuenta de cuántas maneras podemos escribir n utilizando potencias de 2 menores o iguales a p no más de 2 veces cada una. Es evidente que la respuesta se encontraría evaluando f(x,63).

Sabemos que f(n,p) = 0 si n es negativo o si p es negativo. Del mismo modo, f(n,p) = 1 si n = 0. De lo contrario, es igual a la suma de f(n,p-1), f(n-2^p,p-1) y f(n-2^{p+1},p-1), que corresponden a poner 0, 1, o 2 veces la potencia 2^p.

Subtarea 1

Aplicando directamente el análisis anterior, la subtarea 1 queda resuelta.

Subtarea 2

Varios de estos estados se repiten, así que convendría memorizarlos. Utilizando un contenedor como std::map, la solución se vuelve lo suficientemente rápida para resolver esta subtarea.

Subtarea 3

Podemos determinar en algunos casos rápidamente si la función se evaluará a 0. Sabemos que \sum_{i=0}^{k} 2^i = 2^{k+1} - 1. Entonces, el número más grande que podemos escribir sólo usando potencias de 2 menores o iguales a p a lo más dos veces es 2\sum_{i=0}^{p} 2^p = 2 (2^{p+1} - 1) = 2^{p+2} - 2. Por lo tanto, f(n,p) = 0 si n > 2^{p+2} - 2.

Esa optimización por sí misma (sin memorización), resuelve la subtarea 3.

Subtarea 4

Combinando las ideas de las dos subtareas anteriores, el algoritmo es lo suficientemente rápido para resolver todos los casos. Específicamente, la cantidad de estados que no podemos determinar como no viables instantáneamente es proporcional a \log x, y cada estado lo podemos evaluar en tiempo O(\log \log x) por nuestro std::map, dándonos una complejidad total de O(\log x \log \log x). Esta cota puede quedar más clara después de describir la tercera solución.

El siguiente código implementa esta solución:

Análisis 3

Esta solución es equivalente a la anterior, pero no precisa de un std::map.

Consideremos la función n(k), que definimos como el número que obtenemos tomando los bits 0..k de x. En otras palabras, si x = \sum_{i=0}^{\infty} x_i 2^i donde x_i es el i-ésimo bit de x, n(k) = \sum_{i=0}^k x_i 2^i. Ahora, definimos la función g(i,r), que cuenta de cuántas maneras se puede escribir el número n(i) + r2^i, utilizando potencias de 2 menores o iguales a i a lo más 2 veces. La respuesta, por lo tanto, se obtendría evaluando g(63,0).

Ahora, sabemos que g(i,r) = 1 si i < 0 y r = 0, porque podemos escribir sólo de una manera 0. Recordando que x_i es el i-ésimo bit de x, podemos decir que g(i,r) cuenta la cantidad de formas que se puede escribir el número (r+x_i)2^i + n(i-1). De ahora en adelante, por conveniencia, t = r + x_i.

Usando esto, podemos definir g(i,r) recursivamente:

g(i,r) = \begin{cases} 1 & \text{si } i < 0 \text{ y } r = 0 \\ \sum_{k=0}^{min(t,2)}g(i-1,2(t-k)) & \text{de lo contrario} \end{cases}

En otras palabras, si tenemos que poner t veces la potencia i, podemos elegir ponerla hasta min(t,2) veces, y contar las maneras de escribir el resto usando potencias de 2 menores a p. Pero como dejamos t-k veces la potencia i sin poner, es igual a poner 2(t-k) veces la potencia i-1.

La siguiente observación es que si t es mayor a 3, g(i,r) = 0 porque 2\sum_{k=0}^{i} 2^k < 4 \times 2^{i}. Entonces, sólo nos interesan los casos en los que 0 \le t \le 3. En total, sólo hay 4 valores posibles para t en los que g(i,r) no es 0: 0, 1, 2, y 3. Enumerémoslos:

g(i,r) = \begin{cases} g(i-1,0) & \text{si } t = 0 \\ g(i-1,2) + g(i-1,0) & \text{si } t = 1 \\ g(i-1,4) + g(i-1,2) + g(i-1,0) & \text{si } t = 2 \\ g(i-1,6) + g(i-1,4) + g(i-1,2) & \text{si } t = 3  \end{cases}

Pero g(i,r) = 0 si t > 3, y como t \ge r, nos quedamos con:

g(i,r) = \begin{cases} g(i-1,0) & \text{si } t = 0 \\ g(i-1,2) + g(i-1,0) & \text{si } t = 1 \\ g(i-1,2) + g(i-1,0) & \text{si } t = 2 \\ g(i-1,2) & \text{si } t = 3  \end{cases}

Tomando en cuenta que r sólo puede ser 0 o 2, y x_i sólo 0 o 1:

(g(i,0),g(i,2)) = \begin{cases} (g(i-1,0),g(i-1,2)+g(i-1,0)) & \text{si } x_i = 0 \\ (g(i-1,2)+g(i-1,0),g(i-1,2)) & \text{si } x_i = 1  \end{cases}

El siguiente código implementa esta solución, que corre en tiempo O(\log n) y espacio constante:

Como podemos observar, esta solución considera los mismos estados que la anterior, sólo que aquí evitamos computarlos, mientras que la otra los descarta inmediatamente.

Consideraciones

Varios competidores no consideraron que x no cabe en un entero signado de 64 bits. Si bien la respuesta cabe en uno, en los límites del problema se especifica que x < 2^{64}.

Análisis adicional:

Diego Roque escribió una solución distinta, la cual detallaré a continuación.

Consideremos la función f(x) como la define el problema: la cantidad de maneras de escribir x como una suma de potencias no negativas de 2 sin usar cada una más de 2 veces.

Enfoquémonos en la paridad de x (es decir, el último bit de x). Si x es impar, necesariamente tenemos que poner una vez la potencia 2^0, porque las otras dos opciones: ponerla 0 veces o ponerla 2 veces cambiarían la paridad de x. Por lo tanto, f(x) = f(\frac{x-1}{2}) si x es impar. En cambio, si es par, podemos elegir poner la potencia 2^0 0 o 2 veces, lo que nos deja con f(x) = f(\frac{x}{2}) + f(\frac{x}{2}-1). Sólo falta definir los casos base: f(0) = f(1) = 1.

Aquí está su código que implementa esta solución, que corre en tiempo O(\log^2 x \log \log^2 x):

Solución a “Comesolo”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 8
Autor: lhchavez
Fuente: Félix

Este problema es especial porque es el primero en omegaUp de solo salida! Usualmente lo que debes esperar cuando te enfrentes con uno de esos problemas es que sea un problema NP que no tiene una solución rápida, y usualmente te pedirán que te aproximes lo más posible a la solución óptima. Esto significa que te vas a tener que valer de técnicas ad-hoc y heurísticas para sacar puntos.

La solución del problema es bastante sencilla de explicar: haz una búsqueda en profundidad intentando todos los posibles movimientos por fuerza bruta hasta que te salga una solución aceptable e imprímela. El problema es que esta estrategia es O(n!), y como n puede valer hasta 30×30, puedes esperar que el programa corra varios milenios antes de encontrar la solución óptima. Hay tres trucos (en orden de importancia) para obtener una solución decente en un tiempo razonable:

  • No repetir estados.
  • No “clavarse” con soluciones que parece que son muy buenas, pero en realidad llevan a callejones sin salida.
  • Encontrar una manera de darle prioridad a los estados que tengan más probabilidad de llegar a una solución buena.

La estrategia que yo personalmente seguí fue que cada que encontraba un nuevo estado, obtenía su hash (que resultaba en un entero de 64 bits) y verificaba si no lo había visitado usando una tabla de hash*. Si no la había visitado, encontraba todos los estados vecinos (todos los tableros que resultaban de hacer un movimiento válido) y los guardaba en una fila de acuerdo a la cantidad de puntos (entre más puntos, más adelante en la fila). Luego, elegía aleatoriamente un estado de la fila dándole prioridad a los que estaban más adelante (pues son los que tienen mayor probabilidad de llegar a una buena solución), lo cual también me evitaba seguir un único camino donde me podría atorar. Repetí eso hasta que se me terminó la memoria de la computadora e imprimí la mejor solución.

A continuación, el pseudocódigo de la solución:

class Estado:
  int puntos = 0
  bool[N][N] tablero
  Estado padre = null

  def __init__(Estado p):
    puntos = p.puntos
    tablero = p.tablero
    padre = p

  def hash():
    # Puedes usar cualquier algoritmo que genere un entero de 64 bits
    # a partir de tablero y puntos. Este es el más sencillo.
    hash = puntos
    for i in range(0, N):
      hash = ((hash << 7) | (hash >> 53)) ^ tablero[i]
    return hash

  def siguientes(queue[300] colas):
    # Para todas las celdas (i, j) del tablero...
    for i in range(0, N):
        for j in range(0, N):
          # Si la celda tiene una pieza...
          if tablero[i][j]:
            # Para todos los vecinos contiguos (i+k, j+l)...
            for k in range(-1, 2):
              for l in range(-1, 2):
                # Asegúrate que se haya movido _algo_.
                if k == 0 && l == 0: continue
                # Y que pueda brincar dentro del tablero.
                if j + 2 * l < 0 or j + 2 * l >= N: continue
                # Y que haya brincado una pieza.
                if not tablero[i + k][j + l]: continue
                # Y que el lugar a donde brinca esté desocupado.
                if tablero[i + 2 * k][j + 2 * l]: continue
                
                hijo = new Estado(this)
                # Aumenta la puntuación del hijo
                hijo.puntos++
                # Borra la ficha original y la "comida".
                hijo.tablero[i][j] = hijo.tablero[i + k][j + l] = \
                  False
                # Agrega la ficha en su posición final.
                hijo.tablero[i + 2 * k][j + 2 * l] = True
                # Agrégala a la cola correspondiente.
                colas[hijo.puntos].push(hijo)

def elige_estado():
  # Número aleatorio entre 0 y 1.
  r = (random() / (float)RAND_MAX)
  # El índice de la última cola que estuvo llena.
  ultimolleno = -1
  # La cola que se está considerando.
  x = 0
  # Elige la cola con mayores puntos que no esté vacía como
  # primera opción.
  for i in range(0, N):
    if not colas[i].vacio():
      x = i
  # La primer cola tiene probabilidad de 31% de ser elegida.
  # La segunda cola tiene probabilidad de 21%, la tercera 14%,
  # la cuarta 10% y así sucesivamente.
  while x >= 0:
    if not colas[x].vacio():
      ultimolleno = x
    x--
    r *= 1.45
    if r >= 1 and ultimolleno != -1 break
  if ultimolleno == -1: return Null
  return colas[lastfull].pop()

queue[300] colas
hashtable estados_visitados

# lee el estado original
colas[0].push(estado_original)
Estado mejor = estado_original

while no_se_haya_terminado_la_memoria():
  Estado s = elige_estado()
  # Si ya no hay más estados por visitar,
  # encontramos la respuesta óptima en algún punto.
  if s == Null: break
  # Actualiza |mejor| si hay una respuesta mejor.
  if mejor.puntos < s.puntos: mejor = s
  # Repetir estados es malo.
  if s.hash() in estados_visitados: continue
  estados_visitados.add(s.hash())
  # Agrega todos los vecinos.
  s.siguiente(colas)

# A partir de este punto, |mejor| contiene la mejor solución. Podemos
# saber qué movimiento se hizo para llegar a él comparando las
# diferencias entre el tablero de |mejor.padre| y |mejor|. Ya solo es
# cuestión de imprimir el resultado y listo.

* Aquí mucha gente se va a quejar porque solo guardar el hash abre la puerta a que haya dos estados que puede tener hasta 900 bits que tengan el mismo hash de 64 bits (por el principio del palomar) y esté considerando que ya se visitó un estado que en realidad es nuevo. Si haces las cuentas, la probabilidad de colisión es negligible: la cantidad de estados que podía visitar en mi computadora (27 millones) es significativamente más pequeña que el número de estados necesarios para que la probabilidad de colisión sea de 1% (\approx 10^{135}, por la paradoja del cumpleaños).

Solución a “Colección”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 5
Autor: Alexis Cervantes / César Cepeda
Fuente: Alexis Cervantes / César Cepeda

Estructura de la solución: ¿Qué nos están pidiendo? El problema nos esta pidiendo que encontremos un subconjunto de las tarjetas tal que la suma de todos los puntajes de las tarjetas de ese subconjunto sea la maxima posible, y la suma de sus precios sea menor o igual al dinero con el que cuentas.  En otras palabras lo que se esta buscando es que:

la suma sea maxima siempre y cuando 

donde Xi = {1 si se compró la tarjeta iy 0 si no se compró}

Modelo del espacio de búsqueda como árbol: Al final de cuentas, incluso el nombre lo indica, este problema se puede reducir a asignarle a cada tarjeta un 0 ó un 1 dependiendo de si la vamos a comprar o no, por lo que una forma de modelar el espacio de búsqueda sería formar un número binario de N dígitos y crear todos los valores posibles para dicho número.

Para formar todos los números, podemos pensar que en el nivel j del árbol vamos a decidir si compramos la tarjeta j, por lo tanto todos los nodos del nivel j tendrán dos hijos, uno de ellos indicando que si compramos la tarjeta y el otro indicando que no la compramos.  El árbol de búsqueda queda como se muestra a continuación.

Técnica de búsquda a utilizar: Dado que tenemos que entregar como resultado el camino con el mayor puntaje de todos , es preciso que revisemos el 100% de los caminos.  

Una forma de resolver el problema es utilizar búsqued en profundidad, sin embargo el espacio de búsqueda es un árbol binario con N niveles por tanto de 2estados.  Para nuestro problema N=500 por lo que el espacio de búsqueda es indescriptiblemente grande, aunque claro que se pueden podar las ramas en las que el precio ya superó a la cantidad de dinero que tenemos, el aplicar la técnica de búsqueda en profundidad en este problema dificilmente alcanzaría para una mayor que 24 ó 25.

Necesitamos por tanto encontrar una poda mucho más agresiva.

Anteriormente, en el ejemplo de los Tanques, utilizamos la búsqueda en profundidad para encontrar un camino mínimo, por lo tanto, debido a que cada nivel que descendemos el coste aumenta, se podía aplicar la poda de que si obteniamos algún mínimo se podían cortar todas las ramas cuyo coste fuera mayor o igual que el mínimo actual.  Sin embargo al querer encontrar un máximo, esto no es posible, ya que el coste por rama siempre aumenta y lo que queremos es es encontrar el máximo, así que no sabemos si el camino nos va a llevar a algo mejor a menos que lo recorramos todo!

Pero que pasaría si tuvieramos una función tal que nos permitiera saber cual es el máximo posible que podemos obtener por una cierta rama?  En ese caso, podríamos cortar cualquier rama si supieramos que por ese camino es imposible lograr algo mejor que lo que ya tenemos.

Esta técnica se conoce como de “acotamiento y poda”.  La idea es buscar una función que para cada estado del espacio de búsqueda nos de cotas del máximo posible al que se puede llegar por dicho camino y de mínimo seguro que podemos obtener también por ese camino.

Esta técnica es increíblemente poderosa y conviene que mediten un momento sobre la misma.  Vale la pena hacer notar que no siempre es sencillo encontrar la función de acotamiento correcta.  Ya que una función que de una cota muy alta no nos sirve de mucho, ya que las podas serian pocas, pero una cota incorrecta nos puede hacer que entreguemos resultados incorrectos.  Por lo tanto al utilizar esta técnica, siempre debemos buscar la función que acote lo más posible pero estando siempre 100% seguros de que el resultado que obtuvimos es efectivamente mayor o igual al máximo posible.

Para este problema voy a definir las dos funciones de acotamiento, llamemos a(c) a la función que nos da el máximo posible que se puede obtener estando en el nodo cb(c) a la función que nos da el mínimo asegurado que tenemos también al estar en el nodo c.  El demostrar que ambas funciones son válidas queda como tarea para el alumno.

Lo primero que tenemos que hacer es ordenar las tarjetas de acuerdo a la relación U/P, es decir, cuantos puntos nos dan por cada peso gastado.  Como queremos obtener el máximo puntaje por nuestro dinero obviamente son mejores las tarjetas que nos dan muchos puntos por peso comparadas con las tarjetas que nos dan pocos puntos por cada peso gastado. OJO: esto no implica que la solución correcta deba tomar siempre las mejores tarjetas, únicamente quiere decir que comparadas individualmente, para nuestro objetivo son mejores las tarjetas que dan más puntos por peso.

Una vez que tengamos todas las tarjetas ordenadas en base a este criterio, iremos decidiendo si las tomamos o no, en ese respectivo orden.  Para cada nodo, nuestras funciones de acotamiento estarán definidas de la siguiente manera:

b(c):  Para calcular la cota mínima asegurada del nodo c vamos tomando las tarjetas que aún no hemos utilizado según el ordenamiento mientras aún tengamos dinero, en el momento en el que no tengamos más dinero para comprar ahi nos detenemos.  Ese es el mínimo que seguro podemos obtener.

a(c):  Para calcular la cota alta, hacemos el mismo procedimiento que en b (o mejor tomamos el resultado de b para no recalcular) y con la primera tarjeta que no pudimos tomamos su relacion U/P y la multiplicamos por el dinero que aún tenemos disponible y lo sumamos a b.  Así obtenemos el máximo posible que se puede lograr en el subárbol del nodo c.  La operación que efectuamos al final fue la de utilizar el dinero que aún tenemos disponible para comprar un “pedazo” de la mejor tarjeta aún queda, obviamente esto no es posible ya que no podemos comprar pedazos de tarjeta, sin embargo nos sirve para calcular el máximo posible.  

Demostrar que b es válida es trivial, sin embargo queda para el lector demostrar que a es una cota que siempre dará un número mayor o igual al máximo posible que se puede obtener por ese camino.

Obviamente una vez que tengamos las funciones de acotamiento, podemos hacer nuestra búsqueda almacenando cual es el mejor mínimo asegurado que hemos obtenido hasta el momento y eliminando todas las ramas cuyo máximo asegurado es menor o igual que éste.

Detalles de implementación: Para la implementación queda un último detalle que resolver, y este es como vamos a buscar?  Como casi siempre tenemos dos opciones, la primera es la de la búsqueda en profundidad, para la cual se implementa una rutina recursiva y no se requiere de mantener arreglos de memoria externos.  Y la segunda es una búsqueda por amplitud, para la cual requieres de una cola que te permita almacenar los estados proximos a ser evaluados.

Si optamos por la búsqueda en profundidad, hay un detalle de implementación muy sútil que puede ser de gran ayuda.  Supongan que modelamos el árbol de búsqueda como el que se muestra en la figura de arriba.  Y supongan que nuestro algoritmo de búsqueda revisa primero la rama izquierda, de ser asi, la cota mínima asegurada y la cota máxima del hijo de la izquierda es exactamente igual a la de su padre, por lo que bajariamos un nivel en la búsqueda sin obtener ninguna información nueva, si, en cambio, revisamos primero el hijo de la derecha, entonces estaríamos obteniendo nuevas cotas con información probablemente últil.

Si se opta por la búsqueda en amplitud, se tiene una ventaja, y esta es que la cola se puede sustituir por un monticulo de modo que se priorice la búsqueda según el nodo que tiene el mejor mínimo asegurado.  Sin embargo aunque esto podría efectivamente reducir la búsqueda bastante no estamos seguros del tamaño que puede llegar a tener la cola y requeririamos que al llenarse la cola el programa pudiera cambiar a una técnica de búsqueda en profundidad, lo cual haría el código más enredado.  Sin embargo si se desea llegar a límites aún mas grandes, esta sería la opción a seguir.  

Implementación:  

Solución a “Ubongo 3D”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 8
Autor: Miguel Covarrubias
Fuente: Miguel Covarrubias

La solución pone piezas de manera recursiva mientras quepan en el tablero y no se empalmen.

resuelve(pieza)
    si pieza > P
        regresa “Si”
    para cada rotación de la pieza
        para cada casilla g del tablero
            para cada cubo c de la pieza
                si al poner c sobre g, la pieza queda dentro de los primeros 2 niveles del tablero y no se empalma con otra pieza ya puesta entonces
                    marca las posiciones de los cubos de la pieza como ocupados
                    resuelve(pieza + 1)
                    desmarca los cubos de la pieza

Para rotar una pieza se puede rotar por 0^o, 90^o, 180^o o 270^o alrededor de cada eje. El número de operaciones es aproximadamente (número de rotaciones * número de casillas del tablero * número de cubos de una pieza)^3 \le (24 * 7 * 5)^3 < 600,000,000. En los casos de prueba y en el juego todas las soluciones tocan la base del tablero, si no fuera así, solo hay que duplicar el 7 a 14. Para checar si una pieza se puede poner en cierta posición se pueden usar mascaras de bits para los niveles del tablero y para las posiciones ocupadas. Para poner la última pieza se puede comparar todas las rotaciones de los cubos no ocupados contra la última pieza y la complejidad cubica de la solución se reduce a cuadrática.

Solución a “Bloqueo”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 8
Autor: Khayyam
Fuente: Khayyam

La primera observación que hay que hacer es que si todas las carreteras son bidireccionales y entre cada par de ciudades existe exactamente un camino que las conecta (usando una o mas carreteras) entonces la representación gráfica del problema es un árbol: los nodos representan las ciudades y las aristas representan las carreteras. La siguiente figura, muestra el árbol que representa el caso de prueba dado como ejemplo. Los nodos rojos representan las ciudades ocupadas, el esfuerzo necesario para destruir cada carretera se muestra junto a la arista correspondiente. Entonces queremos eliminar un subconjunto de aristas de peso total mínimo de tal forma que los nodos rojos queden separados.

Caso de ejemplo Solución

En problemas relacionados con árboles, es muy natural tratar de dividir el problema en problemas más pequeños que están dados por los sub-árboles del árbol original. Esto además sugiere usar recursión: “para resolver un árbol, primero resolvemos recursivamente sus sub-árboles y luego combinamos las sub-soluciones”.

Comencemos con los casos sencillos. Si hay solamente un nodo (el árbol tiene altura 0), entonces no habrá aristas y el esfuerzo total necesario es cero.

Consideremos ahora un árbol de altura 1 como el de la siguiente figura. Como la raiz no es roja, basta con eliminar una de las dos aristas:
elegimos la que requiera menos esfuerzo.

Caso sencillo: altura 1 Solución (suponemos que la arista izquierda requiere menos esfuerzo)

Si la raiz fuera roja, entonces tendríamos que eliminar ambas aristas. Con lo anterior nos damos cuenta de que hay dos casos que debemos considerar:

  1. Si la raiz es roja, entonces debemos eliminar todas las aristas que la conectan con nodos rojos
  2. Si la raiz no es roja, entonces no es necesario desconectar la raíz de todos los nodos rojos: la solución óptima es dejar conectado
    el nodo rojo asociado a la arista mas costosa.

Lo anterior se ilustra en la siguiente figura (aquí suponemos que la arista de la derecha es la mas costosa de todas):

Si la raiz es roja, entonces debemos eliminar todas las aristas que la conectan con nodos rojos Si la raiz no es roja, entonces no es necesario desconectar la raíz de todos los nodos rojos

Ahora que tenemos la solución para los casos pequeños, veamos si podemos usar estas soluciones para construir la solución del problema general,
como en la siguiente figura.

Si la raiz es roja y el nodo blanco está conectado
a algun descendiente rojo, la solución ya no es correcta
Aún si la raiz es blanca, no podemos dejar conectado el nodo blanco
ya que si está conectado con un descendiente rojo, la solución sería incorrecta

Supongamos que ya tenemos la solución para todos los hijos directos de la raíz, es decir, que ya cortamos de manera óptima las aristas de todos los subárboles, de modo que ningún par de nodos rojos se conectan en el sub-árbol. Usando sólo esta información, ¿podemos construir la solución del problema general?. Desafortunadamente, esto no es suficiente: nos gustaría dejar conectados a los hijos blancos, pero si existe un nodo rojo debajo de ellos, entonces tendríamos que desconectarlo también. Lo que necesitamos saber es precisamente si un hijo blanco está conectado con uno de sus descendientes rojos, de ser así diremos que el nodo blanco es “peligroso”. Si el nodo blanco está desconectado de todos sus descendientes rojos, entonces diremos que es “seguro”. Entonces tenemos tres tipos de nodos: ocupados, peligrosos y seguros, que representamos como nodos rojos, amarillos y verdes, respectivamente.Con este nuevo concepto, vemos que tenemos dos tipos de soluciones distintas para una raíz blanca: tenemos soluciones peligrosas y soluciones seguras. Es fácil ver que no existen “hojas peligrosas”, ya que las hojas están ocupadas (rojas) o son seguras (verdes).

Reformulemos nuestra solución con este concepto. Si la raíz es roja, entonces debemos desconectarla de todos sus hijos rojos y de todos sus hijos peligrosos. Esto significa que para cada hijo blanco tenemos dos opciones:

  • Hacer que el hijo sea seguro (verde) y no cortar la arista que lo une con la raíz (puede ser costoso hacerlo seguro, pero con eso nos ahorramos el costo de separarlo de la raíz)
  • Hacer que el hijo sea peligroso (amarillo) y cortar la arista que lo une con la raíz (puede ser barato dejarlo inseguro, pero pagamos al separarlo de la raíz)

Lo anterior resuelve el caso en que la raíz es roja.

Ahora, si la raíz no es roja, debemos calcular dos soluciones: la solución segura (dejar la raíz verde) y la solución peligrosa (dejar la raíz amarilla). Notemos que la solución segura es exactamente igual al caso anterior. Por otro lado, para la solución peligrosa, debemos dejar la raíz conectada a exactamente un hijo que sea rojo o peligroso. Para elegir cuál de todos los hijos rojos o peligrosos dejaremos conectado, basta iterar sobre todos los hijos y elegir la mejor opción. El código queda como sigue:

Solución a “La Venganza de Silvio”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 1
Autor: Freddy Román Cepeda
Fuente: Freddy

Este problema es bastante sencillo de entender, la dificultad radica en que exponenciar un número de la manera obvia no es lo suficientemente rápido para obtener todos los puntos disponibles.

Subtarea 1

Para obtener el primer grupo de puntos, sólo basta calcular N^M multiplicando a N por sí mismo M veces, teniendo cuidado de que no haya overflow.

Subtarea 2

Para la segunda subtarea, se necesita algo más rápido, para lo que se puede usar exponenciación binaria.

Sabemos que x^0 = 1, que (x^n)^2 = x^{2n}, y que x * x^{n-1} = x^n para toda x y n, por lo que podemos escribir la siguiente relación:

\text{potencia}(N,M) = \begin{cases} 1 & \text{si } M = 0 \\ (potencia(N,M/2))^2 & \text{si } M \text{ es par} \\ N * (potencia(N,(M-1)/2))^2 & \text{de lo contrario} \end{cases}

Aplicando esta definición directamente, la segunda subtarea queda resuelta. Esto es porque el algoritmo descrito anteriormente tiene complejidad O(log M), ya que en cada paso M se reduce a la mitad.

Subtarea 3

El algoritmo anterior es lo suficientemente rápido para resolver esta subtarea, pero el rango de los enteros de la máquina no es lo suficientemente grande para guardar a M. Para ello requerimos una observación adicional. Dividir entre 2 en base 2 ignorando el residuo es lo mismo que recorrer todos los dígitos una vez a la derecha descartando el bit menos significativo, y, además, se puede saber si un número es par o no con sólo ver el bit menos significativo del mismo.

Podemos aprovechar esta observación guardando M como una cadena de bits y modficando un poco la función descrita anteriormente. Si A es el arreglo donde guardamos los bits de M, está 0-indexado, tiene k bits, y los bits están ordenados del más significativo al menos (como viene en la entrada del problema), la respuesta se encuentra evaluando potencia2(N,k-1), donde potencia2 es:

\text{potencia2}(N,i) = \begin{cases} 1 & \text{si } i < 0 \\ (potencia2(N,i-1))^2 & \text{si } A[i] = 0 \\ N * (potencia2(N,i-1))^2 & \text{de lo contrario} \end{cases}

Subtarea 4

El problema con el algoritmo anterior es que ocupa demasiada memoria para los casos que contiene esta subtarea. Para corregirlo, podemos analizar la función anterior.

Por conveniencia, definamos f(i) como el número que se obtiene tomando los elementos [0..i] del arreglo A, y f(-1) = 0. Recordando que multiplicar por 2 en base 2 es lo mismo que recorrer todos los dígitos a la izquierda, f(i) = 2f(i-1) + A[i].

Ahora, es simple notar que potencia2(N,i) = N^{f(i)}, que podemos reescribir como potencia2(N,i) = N^{2f(i-1) + A[i]} = (N^{f(i-1)})^2 N^{A[i]}.

Por lo tanto, podemos escribir un ciclo en vez de utilizar recursión.

Este algoritmo ocupa espacio constante, por lo que resuelve la subtarea 4.

Aquí está la implementación del algoritmo anterior:

Consideraciones

Hay que tener cuidado de que no haya overflow. Cuando un entero de k bits se eleva al cuadrado, puede ahora tener a lo más 2k bits. Como m puede tener hasta 31 bits, es necesario usar enteros de 64 bits durante todos los cálculos.

También, varios competidores no consideraron el caso en el que se pide calcular N^0 \pmod 1.

Solución a “Cueva”

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 4
Autor: Ethan Jiménez Vargas

Después de comprender el problema podemos deducir dos cosas:

  • Los N puntos de la cueva modelan un árbol, esto debido a la propiedad de que existirán N-1 aristas y siempre hay un camino entre cualquier par de nodos.
  • Podemos traducir la tarea principal del problema a lo siguiente “Para cada una de las Q preguntas, ¿el nodo A es un ancestro del nodo B?”, de modo que necesitamos encontrar una manera óptima de saberlo.

Subtarea 1. Para obtener los primeros 25 puntos del problema solo necesitamos implementar el método de fuerza bruta que nos permita conocer si A es ancestro de B, esto puede conseguirse con una búsqueda en profundidad (DFS) que desde el nodo A encuentre la manera de llegar al nodo 1, restringiendo que no sea posible pasar por el nodo B, si existe un camino del nodo A al nodo raíz la respuesta es 1, en caso contrario la respuesta es 0. Hay que cuidar los casos especiales cuando el nodo B es el nodo raíz o cuando el nodo A es el mismo nodo B, en ambos casos la respuesta es 0.

Complejidad de la solución: O(NQ)

Subtarea 2. Es notable que esta vez el número de preguntas es mucho mayor, por ello la solución anterior tardaría demasiado. Cambiemos nuestra estrategia, esta vez realicemos una búsqueda en profundidad desde el nodo 1 hasta los demás N nodos, llevando una lista L de los nodos que forman parte del camino desde el nodo 1 hasta el nodo K, incluyendo los nodos 1 y K, esto puede lograrse mediante recursividad.

La tabla ancestro[K][M] nos permitirá saber si el nodo M es un ancestro del nodo K, dándonos cuenta que todos los ancestros de K se encuentran en la lista L cuando la búsqueda en profundidad llega al nodo K, podemos llenar la tabla ancestro[K][M] durante la búsqueda en profundidad. Con la tabla anterior es fácil responder las preguntas, pues la respuesta depende de ancestro[B][A].

Complejidad de la solución: O(N2+Q)

Subtarea 3. Para obtener los puntos de esta subtarea podemos utilizar cualquier algoritmo para resolver el clásico problema del ancestro común de dos nodos en un árbol, puesto que la respuesta es 1 si el ancestro común entre los nodos A y B es el nodo A. Este problema ya ha sido estudiado ampliamente y tiene diversas formas de ser resuelto con complejidad O(NlogN), en el foro de tutoriales de TopCoder podemos encontrar un buen artículo con algunos de los algoritmos que pueden ser utilizados:

TopCoder Lowest Common Ancestor

El algoritmo que utiliza programación dinámica es el más recomendado, puesto que se puede responder a las Q preguntas en un tiempo constante.

Complejidad de la solución: O(NlogN+Q)

Subtarea 4. Para empezar, notemos que la solución anterior no funciona para este conjunto de puntos porque utiliza demasiada memoria, el simple hecho de almacenar los nodos y las aristas ocupa bastante espacio en memoria (aproximadamente 100Mb) y una solución para la subtarea 3 requeriría al menos 50Mb más, por lo tanto no es posible completar la subtarea 4 con una solución como la anterior, para obtener los 100 puntos en este problema necesitamos una idea mucho más creativa.

Renombremos todos los nodos del árbol enumerandolos del 1 al N siguiendo el orden establecido por el recorrido en postorden del árbol comenzando por el nodo 1, después, para cada nodo, con su respectivo número Y, hay que obtener el menor número presente en el subárbol con raíz en el nodo Y, denotemos este número menor como X, con los números X y Y definimos entonces un intervalo cerrado [X,Y] que nos representa que en el subárbol con raíz en el nodo Y se contienen todos los nodos cuyo número se encuentra en el intervalo [X,Y]. Podemos interpretar esta información de una manera más conveniente, un nodo con número Y es ancestro de un nodo con número K si X ≤ K ≤ Y, lo cual nos permitirá responder las preguntas planteadas.

Es recomendable que el olímpico experimente y se convenza que la propiedad del intervalo [X,Y] es siempre correcta debido a que el recorrido en postorden establecerá que el nodo con el número X, que establece la cota inferior del intervalo, siempre será una hoja del subárbol y el nodo con valor Y, que establece la cota superior del intervalo, siempre será la raíz del subárbol, cualquier otro valor fuera del intervalo estará excluido del subárbol con raíz en el nodo Y.

Complejidad de la solución: O(N+Q)