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.

Invasion Zombie

Hola!, este es mi primer post en Omegaup y voy a describir mi solución para el problema Invasion zombie.

Hace un año encontré este problema, me pareció interesante y logre resolverlo, aunque algo tricky. Hace unos días me tope con este problema nuevamente y lo resolví por segunda ocasión, pero con una solución más simple, al menos eso creo.

Primer solución

La idea principal tanto en la primera como en la segunda solución es diseñar una función f(d) que nos retorne el número de colonias infectadas después de d días, nos interesa el mínimo valor de d tal que el número de colonias infectadas sea mayor o igual a C. Una propiedad importante es la siguiente, f(d) nunca decrece, es decir f(d) <= f(d+1). Esta propiedad nos permite utilizar búsqueda binaria para encontrar las respuesta en O(\lg_{2}(n)).

Diseñar una función que determine el número de colonias infectadas, dependiendo del background de cada uno, es la parte interesante, y es donde difieren las dos versiones, bueno, un poco.

Este es el código de la primer versión, no voy a entrar en detalles porque ni yo me acuerdo bien que trucos aplique, pero la idea es parecida a la de la de la segunda versión, lo que cambia es la estrategia.

Segunda versión

Bueno, empecemos, trascurridos d días, ¿cuántas colonias han sido infectadas?

Simulemos la invasión y veamos si podemos encontrar un patrón.

zombies-pattern

No es complicado llegar a la siguiente fórmula:

f(d) = d^{2} + (d+1)^{2}

Si el espacio de la ciudad fuese ilimitado nuestra función de verificación sería algo parecido a:

Sin embargo, el espacio de la ciudad es limitado y habrá casos como los siguientes:

zombies-sc1

zombies-sc2

Entonces nuestro objetivo es encontrar el área delimitada por la ciudad (un cuadrado de N * N unidades), lo cual se pone un poco tricky. La siguiente imagen nos ayudará a entender el código de la solución sin entrar en tantas explicaciones.

zombies-solution

Es decir, el área total menos el área de los triángulos superior, inferior, izquierdo y derecho. Obsérvese que los triángulos pueden traslaparse y por lo tango estaríamos restando esas áreas 2 veces, por ello tenemos que calcular las áreas de traslape (nw, ne, se y sw en la imagen) y regresar lo a la suma total.

Lo que sigue es la implementación:

Espero que les sea útil, dudas, comentarios o correcciones son bienvenidas.

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 “Temblor”

Problema: Temblor

Primero que nada, tratemos de entender qué es lo que se nos pide, pues es un problema poco tradicional: Dado un mapa de a lo más 4×4, hay que dar una serie de instrucciones que, sin importar en donde te encuentres en el mapa, logre llevarte a una salida; esta secuencia además, debe de ser la más pequeña posible.

Este es el caso de ejemplo:

mapa

La solución correcta es ONNEE, pues con esas instrucciones, podemos salir no importando en que lugar estemos (el lugar inicial está marcado con un punto rojo):

  • En el caso 1, las instrucciones ONN no hacen nada pues hay paredes, y las instrucciones EE nos sacan del mapa.
  • En el caso 2, ONN no hacen nada de nuevo y la primera E nos saca del mapa (la última E ya no importa).
  • En el caso 3, O no hace nada, pues hay pared, N nos sube un lugar, la segunda N no hace nada, y EE nos saca del mapa.
  • El caso 4, O nos lleva a la izquierda, donde se vuelve el mismo caso que el caso 3.
  • En el caso 5, O no hace nada, y NN nos lleva al caso 1.
  • Y finalmente, en el caso 6, O nos lleva al caso 5 y de ahí podemos salir.

Es mucho más fácil ver la solución si vemos a todos los olímpicos moverse al mismo tiempo:


Esto ejemplifica dos cosas: en primer lugar, el camino no debe de ser óptimo para cada uno, sino para todos en general, por ejemplo, el punto que inicia en la esquina superior derecha (cerca de la salida), podría salir yendo hacia la derecha, y saliendo en un único movimiento, pero si lo primero que hacemos es un “este”, estaremos complicando más las cosas para el resto de los olímpicos atrapados. En segundo lugar, puede haber más de un olímpico en un mismo lugar, y una vez que hay dos olímpicos en un mismo lugar, no importa realmente cuántos hay, sino que hay al menos 1 olímpico en ese lugar:

O bien, si lo vemos como unos y ceros:

Donde 1 significa hay al menos un olímpico ahí y 0 significa no hay ningún olímpico ahí.

Por lo tanto podemos concluir que nuestra tarea es convertir un tablero lleno de 1’s en un tablero lleno de 0’s.

 

A estas alturas, ya tenemos lo suficiente como para hacer una búsqueda en amplitud sobre el problema. Los estados de nuestro espacio de búsqueda están representados por un mapa de NxM lleno de 1’s y 0’s y las transiciones entre un estado y otro son las operaciones Norte, Sur, Este y Oeste.

Nuestro árbol de búsqueda empezaría más o menos así:

Solo tendríamos que hacer una búsqueda en amplitud hasta llegar al mapa con puros ceros y reconstruir la solución para resolver el problema.

Sin embargo, representar un mapa entero como un estado puede ser algo problemático, pues podemos tener hasta 16 casillas. Como puede haber un total de 2^16 estados, eso quiere decir que tendremos un arreglo de 17 dimensiones y estaremos usando 2^32 casillas de enteros, lo cual es completamente absurdo, pues aunque nos cupiera en memoria, dudo mucho que un compilador soporte tantas dimensiones y mucho menos que vaya a ser fácil manipularlas.

Lo que nos tenemos que dar cuenta es que como nuestro estado son únicamente 1’s y 0’s podemos olvidarnos de la representación del arreglo, pues podemos convertir cada estado en un número binario. Por ejemplo, a continuación presentamos diferentes mapas y su representación binaria:

Esto simplifica muchísimo nuestro espacio de búsqueda, ya que en vez de necesitar dieciséis enteros para representar un estado, ahora solo necesitamos 1, donde cada bit del estado representa una casilla del mapa.

La pregunta que nos tenemos que hacer ahora es si es posible representar todos los estados con nuestra representación numérica, y la respuesta es que sí, pues solo son hasta 16 casillas en el mapa, o lo que es igual a 16 bits, y sabemos que un entero en la mayoría de los lenguajes modernos soporta hasta 32 bits, por lo tanto nos alcanza y nos sobra para representar todos los enteros.

La siguiente pregunta que nos tenemos que hacer es si nos va a alcanzar la memoria. Y la respuesta también es sí, pues tenemos hasta 2^16 estados, lo cual es alrededor de 65,000 casillas, cada una de ellas puede guardar ya sea la operación que se hizo para llegar a ella, o el estado del que se llegó, ¡o incluso se pueden guardar ambas cosas! Pues solo necesitamos 16 bits para representar el estado de donde vienes y otros 2 para representar la operación que hiciste. Pero la implementación del problema ya se la dejamos a los competidores. En todo caso, necesitamos únicamente 65,000 enteros lo cual cabe en menos de 300 KB.

De esta forma, nuestro árbol de búsqueda se transforma, y se vuelve más fácil de manipular:


Una vez hecha la conversión con bits, esto se vuelve una búsqueda en amplitud común y corriente desde un número con NxM bits prendidos, hasta 0. Una búsqueda así debe de ser fácil de hacer para cualquier competidor.

 

IOI 2015 – Entrevista con blak_dragon1

blak_dragon1

 

Para terminar con la serie de entrevistas a los representantes de México en la IOI 2015, tuvimos la oportunidad de platicar con blak_dragon1 (Ángel Ortega). Esto fue lo que nos dijo:

Cuéntanos cómo empezaste a programar y qué te motiva a resolver problemas:

Todo empezó en un curso llamado “Aprende a Programar” para las Escuelas Secundarias Técnicas. Yo estudiaba en la Escuela Secundaria Técnica No. 37 el 1er grado, ahí fue donde me invitaron a hacer un examen para lograr un lugar en el curso, y me agradó la idea porque algo que ya me llamaba atención en esos días era el uso de la computadora. Conseguí quedarme y aquí vi un poco de lógica matemática y Karel. Esto fue el inicio de todo, nos platicaron de la Olimpiada Mexicana de Informática y que esta da pie para la International Olympiad in Informatics. Eso me emocionó bastante para seguir adelante dentro de la olimpiada estatal del Distrito Federal.

Una motivación que encuentro es que me puede traer una gran cantidad de oportunidades tanto académicas en distintas universidades como laborales en grandes empresas internacionales, además que con el tiempo le he tomado un gusto a la resolución de problemas y a la sensación de competencia dentro de la olimpiada.

Vas a representar a México este año en la IOI. Cuéntanos cómo te preparaste para lograrlo. Cómo son tus días de entrenamiento?

Siento que en el proceso para la IOI de este año me he dedicado más a la olimpiada a comparación de otros años. Esta ocasión realmente aproveche las vacaciones y recesos escolares para entrenar, me puse a leer un poco sobre temas, estructuras de datos y algoritmos que pudieran servirme (Unas ocasiones leí de Algorithms, Fourth Edition de Robert Sedgewick, y en otras ocasiones fue  Algorithm Design de Kleinberg y Tardos) y aumenté la cantidad de horas por semana para practicar a partir de organizarme mejor para repartir el tiempo para no desatender los asuntos de la escuela y mejorar para la olimpiada.

Algo que considero muy importante fue el practicar con problemas de preselectivos de años pasados presenciales antes de una semana de exámenes para eliminación. Hice algo muy parecido con los exámenes de la USACO, antes de presentar mi primer examen de nivel Plata hice 2 exámenes de ese nivel para para darme una idea de la dificultad y en mi primer examen subí a Oro. Antes del examen de nivel Oro también practiqué con un examen de Oro pasado y así no me sorprendiera el cambio de dificultad. Y en estas alturas me preparo con exámenes completos de las IOI pasadas para irme ambientando.

 

Qué le recomiendas a los que van empezando? Algún material, libro o método de entrenamiento?

Yo les recomiendo que sigan al pie de la letra las instrucciones y recomendaciones que nos dan para la preselección, intentar hacer todo los problemas cada problemset, familiarizarse con exámenes de las olimpiadas abiertas de otros países (como USACO  de  Estados Unidos, COCI de Croacia) ya que sus exámenes  también serán tomados en cuenta para las primeras etapas. Si tienen asesores estatales que los estén apoyando aprovéchenlos al máximo, pregúntenle todas sus dudas y póngales bastante atención, cuando vean un tema con él, estando en casa refuercen lo visto leyendo de un libro el tema visto, un buen libro que les servirá para cubrir una gran cantidad de temas es Problemas y Algoritmos que se encuentra en Material Recomendado al inicio de OmegaUp.

Cuál es tu problema favorito de omegaUp y por qué? Hay un problema en particular que hayas disfrutado mucho resolver?

El que más disfruté resolver sin duda fue Fortune Telling 2 (parte de la Japan Olympiad in Informatics 2014),  ya que la combinación estructuras de datos y métodos de solución que implementé me pareció que fue variada (Búsqueda binaria con Segment Tree y al final un BIT), de igual forma sentí que el análisis para llegar a la idea fue  progresivo, lo fui haciendo parte por parte y cada vez  descubría algo me acercaba más a la solución. Otro aspecto por el cual me agrada es porque es de los primeros problemas en los que sin saber previamente que tienen una solución con una estructura de datos puede describir cómo resolverlo.

Descríbenos tu estrategia para atacar un concurso. En qué momento decides cambiar de problema?

Lo que siempre hago es leer todos los problemas que vengan en el examen y mientras voy leyendo, al llegar a la parte de los límites intentar ver si hay alguna solución parcial que en ese instante pueda deducir si conseguiré programarla sin problemas durante el examen, a partir de eso veo la cantidad mínima de puntos podré lograr. De igual forma ordeno los problemas del más fácil al más difícil y empiezo a atacarlos, empezando por el fácil. Cuando llego a un punto en el que llevo demasiado tiempo (40 minutos, 60 ya exagerando) pensando y sigo perdido o sin encontrar nada nuevo es en donde cambio de problema. Si ya pensé demasiado tiempo todos los problemas pendientes por resolver me arriesgo por la solución con más puntos que haya encontrado durante el tiempo de análisis de cada problema y si aún queda tiempo, regreso a seguir pensado otro poco pero por lo regular ya no vuelvo a tener tiempo para pensar de nuevo.

Aparte de resolver problemas, cuáles son tus hobbies? cuáles son tus libros favoritos? qué música escuchas? practicas algún deporte?

De hobbie me gusta armar puzzles 3D (Al estilo del cubo Rubik pero con variaciones).  Los libros de literatura que he leído son principalmente los que me han dejado leer como tarea y  los que más me han agradado son “Los días enmascarados” y “Aura”  de Carlos Fuentes, junto con  “Al sur de la frontera al, oeste del sol” de Haruki Murakami. De música me gusta mucho el Power Metal, principalmente si tiene un toqué Sinfónico (Al estilo Rhapsody of Fire), encuentro cierta inspiración al escuchar música con un ritmo enérgico. También me agrada el basquetbol, aunque no lo practico formalmente, durante algunos recesos de la escuela me gusta salir a jugar.

 

IOI 2015 – Entrevista con Emmanuel_Antonio

Emmanuel_Antonio

 

Emmanuel_Antonio será uno de los representantes de México en la International Olympiad in Informatics 2015. Tuvimos la oportunidad de entrevistarlo previo al concurso y esto fue lo que nos dijo:

Cuéntanos cómo empezaste a programar y qué te motiva a resolver problemas:

Empecé a programar cuando el maestro Luis Citalán me invitó a entrar al taller de la Olimpiada en la escuela. Me motiva ver a esas personas que han logrado cosas muy importantes.

Vas a representar a México este año en la IOI. Cuéntanos cómo te preparaste para lograrlo. Cómo son tus días de entrenamiento?

Ya es mi segundo año en la olimpiada, en el primer año aprendí muchas cosas nuevas en los entrenamientos y el segundo año lo dediqué a practicar esas cosas que había aprendido.

Qué le recomiendas a los que van empezando? Algún material, libro o método de entrenamiento?

No dejar de practicar, cada vez busquen problemas de mayor dificultad, que vean problemas de olimpiadas pasadas para así saber que temas son los que les hacen falta aprender o practicar y sobre todo que lo hagan por gusto, no porque se sientan obligados o algo así.

Cuál es tu problema favorito de omegaUp y por qué? Hay un problema en particular que hayas disfrutado mucho resolver?

No sabría decir cual es mi favorito. Disfruto aquellos que después de pensarlos un buen rato al fin te llega la idea de la solución.

Descríbenos tu estrategia para atacar un concurso. En qué momento decides cambiar de problema?

Leer todos los problemas y entender que es lo que pide cada uno de ellos, después empiezo con el que yo considero que podría estar más fácil. Cambio de problema cuando siento que pasa un buen rato y no logro avanzar en la idea.

Aparte de resolver problemas, cuáles son tus hobbies? cuáles son tus libros favoritos? qué música escuchas? practicas algún deporte?

Me gusta salir con mis amigos, ver películas o series y jugar. Me gustan los libros que tiene misterio o algo policiaco. Escucho casi de todo, son muy pocos los tipos de música que no me gustan. Me gusta mucho jugar fútbol. 😀

 

IOI 2015 – Entrevista con charlyhlms

charlyhlms

Esta vez tocó el turno de entrevistar a charlyhlms quién representará a México por segunda vez en la International Olympiad in Informatics. Esto fue lo que nos dijo:

 

Cuéntanos cómo empezaste a programar y qué te motiva a resolver problemas:

Empecé a programar cuando tenía 13 años, durante mi segundo año de secundaria. Estaba en el taller de Computación y a principios de ese año nos enseñaron a programar en Pascal y Karel, en ese entonces me parecía algo divertido y diferente, fue por eso que cuando me comentaron sobre la Olimpiada decidí inscribirme.

Resolver un problema es un proceso bastante interesante, no importando el tipo de problemas al que nos enfrentemos, tanto problemas de olimpiadas como problemas de la vida diaria representan retos que afrontamos constantemente, retos que a mi parecer son una manera de poner a prueba la creatividad de una persona y su capacidad de aplicar el conocimiento que ha adquirido, sin importar de donde, para un fin práctico. Además de esto, creo que todos podemos concordar en que después de resolver un problema suele haber una sensación de satisfacción,  de sentirnos mejores en lo que hacemos por que tuvimos la capacidad de dar solución a un problema por nuestros propios medios y saber que cada problema que resolvemos nos aporta nuevos conocimientos. Más particularmente para los problemas de olimpiada hay un par de situaciones que siempre me parecieron muy interesantes: El hecho de que no baste con obtener una buena idea,  sino que además tengas que escribir está idea para que una computadora pueda hacer lo que tienes en mente; y que después de haber obtenido la solución completa a un problema siempre puedes mirar atrás, aprender de los errores que cometiste en el proceso o de las nuevas ideas que pusiste en práctica, y de como ahora todo ahora parece tan obvio, después de que en un principio no parecías saber ni por donde empezar. La combinación de todo esto es lo que me ha motivado a dedicar buena parte de mi tiempo a resolver problemas.

Vas a representar a México este año en la IOI. Cuéntanos cómo te preparaste para lograrlo. Cómo son tus días de entrenamiento?

Llegar a la IOI fue un proceso que principalmente requirió mucha disciplina y constancia a la hora de entrenar. No creo poder describir un día normal de entrenamiento porque mi manera de entrenar cambiaba dependiendo de en que me quería enfocar. Entre las cosas que hacía estaba  presentar un examen por semana, para esto usaba fuentes como la Usaco o exámenes de IOIs u OMIs pasadas. Después de hacer el examen leía las soluciones tanto de los problemas que resolví como los problemas que no resolví e implementaba estas soluciones completas.

También le dediqué mucho tiempo a leer para aprender nuevos temas y técnicas además de mejorar mis habilidades matemáticas, un libro que aún no acabo de leer pero estoy disfrutando es Art and Craft of Problem Solving. Además de esto hubo un tiempo en que me interesaba mejorar mi rapidez a la hora de implementar además de mi capacidad para escribir códigos sin errores, para ello escribía todos mis códigos en papel antes de escribirlos en computadora, lo bueno de hacer esto es que al escribirlos en papel, con pluma, no se tienen las  herramientas de edición que se tienen cuando se hace en un editor de texto, por lo que se vuelve muy importante estar completamente seguro de lo que se está implementando. En general estás fueron algunas de las cosas que hice durante este año de entrenamiento, pero como dije no sólo es importante tener un buen plan o método de entrenamiento sino también ser capaz de cumplir con las metas que uno se propone y ser muy constante.

De los 4 representantes de México, tú eres el olímpico con más experiencia. Tuviste la oportunidad de participar en la IOI 2014, qué lecciones aprendiste y qué planeas hacer diferente este año?

Ir a una IOI ha sido una de las mejores experiencias en mi vida, no haber obtenido una medalla no opacó este hecho pero si es algo que me ha sido difícil superar. Lo importante de esto es que me dio la oportunidad de aprender muchas cosas sobre la competencia y sobre lo que tenía que mejorar. Entendí cosas muy importantes como la relevancia de manejar el tiempo de la manera correcta, y en especial de mantener la calma durante el examen sin importar lo difícil que se pongan las cosas. Comprendí y trabajé en las cosas que debía mejorar, algunas de ellas ya las mencioné: mi rapidez y la eficacia con la que programo por ejemplo. No creo que el resultado que obtuve el año pasado fue en vano, la experiencia me ha servido demasiado, y para esta IOI estoy muy motivado, motivado como nunca lo he estado, porque voy a disfrutar mucho la competencia y porque estoy seguro que estoy en un mejor momento que el año pasado.

Qué le recomiendas a los que van empezando? Algún material, libro o método de entrenamiento?

Durante mi primer año en la pre-selección un libro que me resultó de mucha ayuda fue Problemas y Algoritmos por Luis Enrique Vargas Azcona. Incluye muchos de los temas básicos y no tan básicos que se abarcan durante las primeras etapas del pre-selectivo y una gran ventaja es que está escrito en español, y muchos de los problemas propuestos en el libro se pueden resolver en OmegaUp. Además de ese libro leí Introduction to Algorithms, y Algorithm Desing por Jon Kleinberg, también me fueron de mucha utilidad aunque quizá son un poco más avanzados y están escritos en inglés.

Claro que aparte de tener una fuerte base de teoría y conocer muchos temas, resulta igual de importante dedicar la mayoría del tiempo de entrenamiento a resolver problemas. Una muy buena página para entrenar es la Usaco Training Gateway (http://train.usaco.org/usacogate), resulta bastante útil porque los problemas están divididos por secciones y cada sección abarca un tema diferente. Y como parte importante de la competencia es ser capaz de resolver problemas incluso bajo la presión y el estrés de un examen, también  recomendaría hacer exámenes constantemente, para esto además de OmegaUp, hay un par de buenas páginas como la USACO http://www.usaco.org/ y COCI http://hsin.hr/coci/ en las que se pueden encontrar exámenes de años pasados.

Cuál es tu problema favorito de omegaUp y por qué? Hay un problema en particular que hayas disfrutado mucho resolver?

Diría que mi problema favorito de OmegaUp es Pequeños Autobuses, fue un problema que enfrenté por primera vez durante un eliminatorio de la pre-selección, pero fui capaz de resolverlo hasta unas semanas después. Esos problemas que te toman mucho tiempo resolver siempre terminan siendo “divertidos”. Aparte de este problema en general disfruto mucho resolver tareas de IOI; resultan divertidos porque aunque se trate de un problema relativamente sencillo suele haber detalles que lo hacen ser un problema interesante, ya porque necesitan una idea bastante creativa o bien porque requieren de una implementación elegante. Algunos problemas de IOI de este estilo son: Bloques, Fuerza Media, Montañas, Joining Points, Impresora de Tipos, Cueva, Ríos, Loros (Todos estos están disponibles en OmegaUp), además de Batch Scheduling de la IOI del 2002, Amazing Robots de la IOI del 2003 y Robots de la IOI 2013.

Descríbenos tu estrategia para atacar un concurso. En qué momento decides cambiar de problema?

Lo primero que hago cuando enfrento un examen es siempre leer todos los problemas y asegurarme de entenderlos perfectamente, al punto de que pueda dejar de ver la descripción del problema y no olvidar los detalles importantes. Después de esto mi estrategia suele cambiar dependiendo de la dificultad de los problemas que intentaré resolver, pero normalmente intento atacar cada uno de los problemas en orden. Al atacar un problema me doy una cantidad limitada de tiempo para pensar en la mejor idea que me sea posible, digamos, media hora, aunque este tiempo puede disminuir si me doy cuenta que no estoy obteniendo avances importantes, o por el contrario aumentar si creo estar cerca de una solución completa. Después de esto implemento la mejor solución que haya obtenido y al obtener los puntos esperados cambio de problema. Al final si ya he intentado algo para todos los problemas del examen, elijo alguno de los problemas que no resolví completamente e intento mejorar mi puntaje obteniendo mejores ideas.

Sobre cuando “cambiar de problema”, al menos yo sólo lo hago cuando he dedicado mucho tiempo a depurar mi código. Siempre hay ocasiones en que obtenemos una buena idea, la implementamos y después de subirla no obtenemos los puntos que esperábamos, aunque puede llegar a ser bastante molesto no es prudente darse por vencido en ese mismo instante como no es conveniente dedicar más tiempo de lo adecuado a buscar un error en la idea o en la implementación. Depende mucho del examen y de la situación particular en la que te encuentres, pero siempre se debe dedicar una parte del examen a buscar el posible error en nuestra implementación o incluso en la idea, pero es igual de relevante, en caso de no poder encontrar dicho error, ser capaz de abandonar el problema, bien cambiando de problema o bien intentando una solución diferente que probablemente dé menos puntos. Saber manejar el tiempo durante un examen se vuelve en ocasiones tan crucial como tener buenas ideas o ser rápido codificando, pero esto es algo que se obtiene con la práctica, después de haber realizado una buena cantidad de problemas y exámenes.

Aparte de resolver problemas, cuáles son tus hobbies? cuáles son tus libros favoritos? qué música escuchas? practicas algún deporte?

Además de resolver problemas, me gusta leer y escribir y también tocar la batería. Algunos de mis libros favoritos son El Llamado de la Selva por Jack London, Nada de Janne Teller y El Juego del Ángel de Carlos Ruíz Zafón. También disfrutó bastante de escuchar música, creo que mis gustos son bastante variados pero normalmente escucho Rock, algunos de mis grupos favoritos son The Beatles y Soda Stereo aunque recientemente comencé a escuchar otro generó musical: Jpop. Viajar es también algo que siempre me ha gustado y la olimpiada me ha dado la oportunidad de hacerlo con bastante frecuencia.