Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

MOG Round #33 - Discussion by Norge 7 years ago

Hola a todos!

Esperamos que disfrutaran la competencia, ya hemos actualizado el rating de los competidores. La editorial será publicada pronto sobre este mismo post. Respecto a los problemas aunque eran varios estabamos contentos con el nivel en general y la variedad. Esperamos se mantengan atentos a las próxima competencia y nos encantaría que aumentara la participación. Mucha suerte a los equipos cubanos en Beijing !

Soluciones ( sus correcciones serán agradecidas )

A - Manzana

Considere la fórmula para recalcular los cambios en la distribución de las probabilidades en cada paso: $p_{i+1} = \sum_{u \in N(v)}{\frac{p_i(u)}{d(u)}}$, donde $N(v)$ denota el conjunto de todos los vecinos de $v$ (con respecto a las repeticiones).

Nota, que si $p_i(v) = \frac{d(v)}{2m}$ para cada $v \in V(G)$ entonces $p_{i+1}(v) = p_i(v)$, es decir, la distribución es estable.

De esta forma, usando la linealidad del valor esperado concluimos que la respuesta es igual a $\sum_{v \in V(G)}{\frac{k \times d(v) \times a_v}{2m}}$

B - Construyendo la red de carreteras
Dado $n$ puntos en el plano y la distancia entre los puntos definida como $\rho(i, j) = |x_i - x_j| + |y_i - y_j|$, seleccionar $n - 1$ aristas tal que es posible buscar un tour que, partiendo desde el primer punto, visite todos los puntos y regrese al origen usando solo esas aristas. La longitud total del tour debe ser mínima.

Si $n - 1$ aristas $T$ son seleccionadas (obviamente forman un árbol), entonces la longitud del tour es igual a $2\sum_{e \in T}{ \rho(v(e), u(e))}$. En efecto, es suficiente recorrer todo el árbol pasando por cada arista $2$ veces con el objetivo de recorrer todos los puntos y volver al origen. Esto significa, que solo debemos construir el Minimum Spanning Tree (MST) para el grafo implícito definido por los $n$ puntos.

Considere el algoritmo de Prim ( wiki ) para buscar MST. La implementación más básica que almacena los valores en una lista y selecciona el mínimo en tiempo linear toma $O(n^2 + m)$. Para este problema en particular $m = \frac{n(n - 1)}{2}$ por lo tanto esta solución es óptima. Además, la constante involucrada es pequeña debido a la simplicidad de las operaciones (incluyendo el valor absoluto para calcular las distancias).

C - Coeficientes
Dado $n$ pares $(x_i, r_i)$ determinar los valores $c_0, c_1, ..., c_{n-1}$ tal que:

$f(x_i) = r_i \text{ mod } 10^9+7$, donde
$f(x) =c_0 + c_1x + c_2x^2 + ... + c_{n-1}x^{n-1}$.

El entero $p = 10^9 + 7$ es un número primo. De esta forma podemos utilizar el Pequeño Teorema de Fermat para implementar la división e interpolar utilizando el Polinomio de Lagrange ( wiki ).

Primeramente definimos los polinomios básicos $l_i$ que son iguales a $1$ en el punto $x_i$ y $0$ en cualquier otro $x_j$, $i \ne j$.

$\Large{l_i = \frac{(x_0 - x)(x_1 - x)...(x_{i-1} - x)(x_{i+1} - x)...(x_{n-1} - x)}{(x_0 - x_i)(x_1 - x_i)...(x_{i-1} - x_i)(x_{i+1} - x_i)...(x_{n-1} - x_i)}}$

Ahora, construimos el polinomio resultante como $\sum_{i=0}^{n-1}{l_i(x) \times r_i}$. Aquí y en la fórmula anterior, todas las operaciones son consideradas módulo $10^9 + 7$. El grado del polinomio resultante no excede $n - 1$.

Solución 2
Opcionalmente, puede utilizar el método de Gauss-Jordan ( wiki ) para resolver el sistema de ecuaciones siguiente:

$\begin{pmatrix}1 & x_0 & x_0^2 & ... & x_0^{n-1}\\\ 1 & x_1 & x_1^2 & ... & x_1^{n-1}\\\ ... & ... & ... & ... & ...\\\ 1 & x_{n-1} & x_{n-1}^2 & ... & x_{n-1}^{n-1} \end{pmatrix}$ $\begin{pmatrix}c_0\\\ c_1\\\ ...\\\ c_{n-1} \end{pmatrix}$ = $\begin{pmatrix}r_0\\\ r_1\\\ ...\\\ r_{n-1} \end{pmatrix}$

D - Destino
Considere un grafo dirigido y ponderado $G=(V, E)$, $m = |V|$, $e = |E|$, $w(e) \ge 0$ para cada $e \in E$. Además, cada nodo tiene algún color $c(v)$ y una permutación $p_1, p_2, ..., p_n$ es dada. Determinar una secuencia de nodos $s_1, s_2, ..., s_n$ tal que $c(s_i) = p_i$ para cada $i$ en el rango de $1$ a $n$ y $\sum_{i=1}^{n-1}\rho(s_i, s_i+1)$ es mínima. Aquí $\rho(u, v)$ representa la longitud del camino mínimo de $u$ a $v$ y es considerado infinito si no existe camino de $u$ a $v$.

Aplicamos programación dinámica $d(i, v)$ - el mínimo número de años necesarios para completar los primeros $i$ rituales y terminar en el nodo $v$. $d(i, v) = \infty$ si $c(v) \ne p_i$.

Para cada par $(i, v) (i \gt 0)$ tal que $c(v) = p_i$ calculamos $d(i, v) = \text{min}(d(i - 1, u) + \rho(u, v))$. El tiempo anterior es $O(nm^2)$ si las distancias se precalculan.

Podemos precalcular la matrix de todas las distancias en $O(m^3)$ usando el algoritmo de Floyd ( wiki ). El tiempo total de la solución sería $O(m^3 + nm^2)$.

E - Eclosión del huevo
Dado un conjunto de $n$ pares de enteros $(a_i, b_i)$ y un entero $m$ buscar un subconjunto $s_1, s_2, ..., s_k$ ($k$ no es dado y puede ser seleccionado arbitrariamente) tal que:

- $\large{\sum_{i=1}^{k}{a_{s_i}} \ge m}$;

- $\Large{\frac{\sum_{i=1}^{k}{b_{s_i}}}{\sum_{i=1}^{k}{a_{s_i}}}}$ sea máximo.

Aplicamos programación dinámica $d(i, x)$ - máximo número de pokemons que podemos atrapar usando las primeras $i$ atracciones y caminando una distancia total igual a $x$. Este es un problema de programación dinámica bien conocido ( wiki ).

$d(i, x) = max(d(i - 1, x), d(i - 1, x - a_i) + b_i)$

Calculamos $d(i, x)$ para todo $i$ en el rango de $0$ a $n$ y todo $x$ en el rango de $0$ a $L$, donde $L = \sum_{i=1}^{n}a_i$. Luego tratamos todo $x \ge m$ y escogemos el valor de $d(n, x)$ que maximice la proporción. El tiempo del algoritmo sería $O(nL)$.

Podemos darnos cuenta que no es necesario considerar valores de $x$ mayores que $m + max(a_i)$ porque siempre vamos a ser capaces de eliminar una atracción del subconjunto sin decrementar la proporción. Ahora, el nuevo tiempo sería $O(nm)$.

F - Los poderes de Freyja
Considere un polígono convexo y un número de puntos dentro del mismo. El objetivo es conectar algunos puntos a otros por segmentos tal que:
- no hay dos segmentos que se intersectan.
- la figura completa está conectada.
- cada región interna del grafo planar resultante es un triángulo.
- el menor ángulo de todos los triángulos es máximo.

Primero, debemos notar que no hay necesidad de separar los puntos en dos conjuntos. Solamente los unimos y resolvemos el problema de buscar una triangulación que maximice el menor ángulo.

Maximizar el menor ángulo de una triangulación es una de las propiedades principales de la triangulación de Delaunay ( wiki ) - triangulación de un conjunto $P$ de puntos tal que no existe un punto en $P$ dentro de la circunferencia circunscrita de cualquier triángulo. Esta propiedad hace dicha triangulación muy útil para algunas aplicaciones de métodos numéricos para la aproximación de soluciones de ecuaciones diferenciales parciales ( wiki ).

Existe un gran número de formas para construir esta triangulación, seleccione su favorita. Como el número de puntos en el problema es pequeño es razonable seleccionar un algoritmo simple que nos ahorre tiempo en el concurso. Una selección pudiera ser flip algorithm ( wiki ). Dicho algoritmo calcula una triangulación inicial y luego ajusta los triángulos que no cumplen la condición de Delaunay. La triangulación inicial se puede obtener haciendo un barrido por el eje X (de izquierda a derecha) e ir agregando cada punto a la vez. Para este problema pueden existir puntos colineales lo cual debe manejarse apropiadamente durante la implementación.

G - Cuadrícula y triángulos
Para varias cuadrículas de $n \times m$ contar el número de tríangulos válidos no-degenerados.

Los límites del problema permiten una solución en $O(n^2m^2)$ (con una constante pequeña). Si permitimos triángulos degenerados (triángulos con sus puntos en una misma línea), la respuesta sería $nm \choose 3$.

Es suficiente restar los triángulos degenerados. El número de triángulos degenerados con vértices sobre las líneas verticales u horizontales es $n {m \choose 3} + m {n \choose 3}$.

Considera cualquier otro triángulo degenerado $(x_1, y_1), (x_2, y_2), (x_3, y_3)$. Supón que $x_1 \lt x_2 \lt x_3$, y además $y_1 \lt y_2$. Sea $g = gcd(x_2 - x_1, y_2 - y_1)$, entonces $x_3 = x_2 + t \frac{x_2 - x_1}{g}, y_3 = y_2 + t \frac{y_2 - y_1}{g}$ para un entero positivo $t$. Bajo las condiciones $x_3 \leq n, y_3 \leq m$ tenemos que $1 \leq t \leq \text{min}(g(n - x_2)/(x_2 - x_1), g(m-y_2)/(y_2-y_1))$, por lo tanto el número de triángulos es igual a la parte derecha de dicha desigualdad.

El número de tríangulos con $y_2 \leq y_1$ es la misma por simetría.

Solución 2
Es posible obtener una solución en $O(nm)$ para este problema considerando todos los tamaños de rectángulos y contando el número de triángulos en dichos rectángulos aplicando inclusión-exclusión.

H - Feliz árbol pequeño
Se puede utilizar una estructura de datos como Treap para resolver este problema.

I - Integración de patrones
Dado dos patrones $a$ y $b$ de letras en inglés y los caracteres $\texttt{*}$ y $\texttt{?}$, buscar un patrón $c$ tal que cualquier cadena $s$ que satisfaga $a$ y $b$, también satisfaga $c$. De todos esos patrones, buscar $c$ que contengan el mínimo número de asteriscos, tenga la mayor longitud posible y contenga el mínimo número de signos de interrogación (en ese orden de prioridad).

Claramente, el patrón óptimo $c$ contendrá a lo sumo un asterisco, debido a que el patrón $\texttt{*}$ acepta todas las cadenas.

Cuándo es posible construir $c$ sin asteriscos? Claramente, dicho patrón $c$ podrá aceptar cadenas de una longitud fija. Por lo tanto, solo es posible si $a$ y $b$ no tienen asteriscos y tienen la misma longitud $l$. Adicionalmente, en este caso el patrón "$l$ símbolos de interrogación" acepta todas las cadenas que aceptan $a$ y $b$. Cómo minimizamos el número de signos de interrogación en este caso ? Si ambos $a$ y $b$ tienen la misma letra en la posición $i$, entonces podemos colocar dicha letra en la posición $i$ de la cadena $c$, de otra forma debemos colocar $\texttt{?}$. El patrón resultante es óptimo.

En el otro caso ($a$ y $b$ tienen al menos un asterisco, o tienen longitudes diferentes) estamos forzados a colocar un asterisco. Cuál es el mayor número de caracteres que podemos colocar en $c$? Sea $l$ la longitud mínima de cualquier cadena aceptada por $a$ o $b$. Podemos observar que $l$ es igual al mínimo número de caracteres diferentes de $\texttt{*}$ entre $a$ y $b$ (por ejemplo, para $a=\texttt{a?b*c}$ y $b=\texttt{??*?}$ tenemos que $l=3$). Como $c$ debe aceptar una cadena de longitud $l$, el número de caracteres diferentes a $\texttt{*}$ no puede ser mayor que $l$. Podemos notar que el patrón "$\texttt{*} + l$ símbolos de interrogación" funciona para este caso, luego la longitud $l + 1$ se puede obtener para $c$.

Cómo minimizamos el número de símbolos de interrogación en este caso? Supón que la posición $i$ precede al asterisco en $c$. Si existe un asterisco antes de la posición $i$ en $a$ o $b$, entonces $c$ debe colocar un signo de interrogación en la posición $i$. En otro caso, una letra se puede colocar en la posición $i$ solo si la misma letra aparece en $a$ o $b$ en la misma posición. El mismo argumento puede ser aplicado para colocar letras después del asterisco (si contamos las posiciones desde el final).

Sea $x$ la última posición donde pusimos una letra desde el comienzo, y $y$ la última posición donde se colocó una letra desde el final. El patrón resultante $c$ lucirá como sigue: los primeros $x$ caracteres con letras colocadas, seguido por $l - x - y$ signos de interrogación, seguido de un asterisco, seguido por los últimos $y$ caracteres ubicados.

Nota que $x + y$ no puede exceder $l$ debido a que hay $x + y$ caracteres diferentes a $\texttt{*}$ en ambos $a$ y $b$.

La complejidad resultante es $O(|a| + |b|)$.

J - Jugando con joyas
Hay varias pilas de joyas. Dos jugadores juegan un juego, un movimiento consiste en dividir una pila en otras pilas de igual tamaño. El jugador que no pueda hacer un movimiento pierde. Determinar el ganador.

La solución utiliza teoría de Sprague-Grundy en juegos imparciales ( wiki ). Aquí hay algunos hechos:

- Podemos asignar una función Grundy $f$ a cada juego, la cual es un entero no negativo. El jugador que debe hacer un movimiento gana si y solo si $f \gt 0$.
- Si dos juegos tienen funciones Grundy $f_1$ y $f_2$, entonces la suma de esos juegos tiene función Grundy $f_1 \oplus f_2$, donde $\oplus$ es el operador suma módulo $2$ (OR exclusivo, $x \wedge y$) de dos números
- Si un juego tiene opciones de movimientos a juegos con funciones Grundy $f_1, f_2, ..., f_n$, entonces dicho juego tiene función Grundy igual a $\text{mex}(f_1, f_2, ..., f_n)$, donde $\text{mex}$ es igual al menor entero no-negativo que no está presente entre sus argumentos.

Usando lo anterior podemos determinar que la función Grundy para un sola pila de tamaño $x$ es igual al número de factores primos impares (con multiplicidad), más $1$ si $x$ es par.

Demostración por inducción
Considera un movimiento que divide $x$ en un número impar de pilas $z$. Debido a que los juegos iguales se pueden cancelar, esto es equivalente a cambiar $x$ por $\frac{x}{z}$. Si $x$ es impar y tiene $f$ factores primos, entonces cada movimiento decrementa el número de factores primos, y para cada número $f' \lt f$ podemos obtener un número con $f'$ factores primos elminando exactamente $f - f'$ factores. Por consiguiente, $\text{mex}$ de las posibles funciones Grundy es exactamente $f$.

Sea $x$ par. Dividiendo $x$ en una cantidad par de pilas es equivalente a eliminar todas las pilas, esto es hacer la función de Grundy igual a $0$.

Nuevamente, podemos mostrar que todos los posibles movimientos hacen la función Grundy $0$, o la hacen igual a $f' + 1$ para $f' \lt f$, donde $f$ ahora es igual al número de factores primos impares. Aplicando un argumento similiar podemos ver que $\text{mex}$ de las posibles opciones es igual a $f + 1$.

La solución ahora consiste en buscar las funciones Grundy para cada pila y hacerles XOR, luego se compara el resultado con $0$. Esto requiere factorizar los números dados, lo que se puede hacer en $O(\sqrt{n})$.

La complejidad total es $O(n\sqrt{A})$, donde $A$ es el valor del máximo número.

K - Constante de Kaprekar
Para un entero $x$ de $5$ dígitos (ceros a la izquierda son permitidos) se define $f(x)$ como la diferencia entre los enteros que se obtienen por ordenar los dígitos de $x$ ascendentemente y descendientemente. Para varios enteros, determinar el resultado de aplicar $f(x)$ un total de $999999$ veces secuencialmente.

Construir un grafo donde los vértices son todos los números de $5$ dígitos, y las aristas van de $x$ a $f(x)$. Como todos los vértices tienen outdegree $1$, el camino desde cualquier $x$ comienza con una parte "pre-periódica" seguido por otra parte periódica (ciclo).

Para cada vértice del grafo la longitud de la parte pre-periódica y el ciclo se pueden encontrar en $O(V)$ con DFS, donde $V$ es el número de vértices. Podemos observar que luego de $999999 \gt V$ pasos arrivaremos seguramente a un ciclo desde cualquier vértice. Ahora es suficiente memorizar todos los ciclos y usar la operación de módulo para encontrar el vértice resultante.

La complejidad total sería $O(V + T)$.

L - Pequeño triángulo
Dado un lattice ( wiki ) en dos dimensiones, resultado de la combinación lineal de los vectores $v_1, v_2, ..., v_n$. Determinar la menor área de un triángulo no-degenerado con vértices en el conjunto.

Calcular el producto cruzado ( wiki ) de todos los pares de vectores, tomar el GCD = g de todos, y la respuesta es $\frac{g}{2}$ ( demostración al lector :v )