Posted on

Soluciones a Liga Omegaup – Fase 1

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.

Posted on

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.

 

Posted on

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.

Posted on

Solución a “Suma Manhattan”

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

Este problema requería manipular con cuidado la expresión que había que computar.
Recordemos que nos piden computar

\sum_{0 \leq i < j < N} manhattan(S_i,S_j).

Para resolver la primer subtarea bastaba con iterar sobre todas las parejas de puntos y calcular su distancia. Esto corre en tiempo cuadrático y no es suficiente para obtener todos los puntos.

La siguiente subtarea era una pista: se puede computar la distancia Manhattan de dos puntos considerando por separado sus coordenadas en x y y. Ahora nos preocuparemos por calcular la siguiente expresión:

\sum_{0 \leq i < j < N} |a_i - a_j|.

Donde a son las coordenadas en x o y. El problema está en el valor absoluto. La manera más sencilla de deshacernos de él es ordenar la secuencia a, de tal manera que a_i \leq a_j. Entonces tenemos:

\sum_{0 \leq i < j < N} |a_i - a_j| = \sum_{0 \leq i < j < N} |a_j - a_i| = \sum_{0 \leq i < j < N} a_j - a_i.

La primer igualdad es verdadera porque |x| = |-x| para cualquier x. La segunda es porque como ahora a está ordenado, como a_j \geq a_i \implies a_j - a_i \geq 0, el valor absoluto no hace nada.

Podemos entonces separar la suma en dos términos:

\sum_{0 \leq i < j < N} a_j - \sum_{0 \leq i < j < N} a_i.

Analicemos el primer término. Estamos sumando sobre todas las j tantas veces haya una i menor que ella. Eso quiere decir que cada a_j la vamos a sumar j veces (nota que a_0 la sumamos 0 veces).

El segundo término nos dice que sumaremos todas las a_i tantas veces haya una j mayor a ella. Eso quiere decir que cada a_i la vamos a sumar N-i-1 veces (nota que a_{N-1} la sumamos 0 veces).

Juntando esas ideas, entonces tenemos:

\sum_{j = 0}^{N-1} j \cdot a_j - \sum_{i = 0}^{N-1} (N - i - 1) \cdot a_i

= \sum_{i = 0}^{N-1} i \cdot a_i - \sum_{i = 0}^{N-1} (N - i - 1) \cdot a_i.

= \sum_{i = 0}^{N-1} (i - (N - i - 1)) \cdot a_i.

= \sum_{i = 0}^{N-1} (2i - N + 1) \cdot a_i.

Y con eso terminamos: ahora tenemos una expresión que podemos computar fácilmente en tiempo lineal. Hay que tener cuidado al computar esto: La primera observación es que hay que estar tomando módulo después de cada operación porque en cualquier momento puede haber un overflow. Algunos competidores obtuvieron 60 puntos en este problema por no tomar esto en cuenta. La segunda observación es que el término (2i - N + 1) \cdot a_i no necesariamente cabe en un entero signado de 32 bits — hacía falta utilizar enteros de 64 bits para realizar este cálculo.

Aquí está mi código que implementa la solución anterior.