Concluida la final mundial de este año queremos compartir con ustedes los resultados de los equipos del caribe. Los 4 equipos que nos representaron resolvieron al menos 2 problemas y tres resolvieron 3 , lo cual es digno de destacar. El equipo KFP de la Universidad Central Marta Abreu de las Villas fue el mejor ubicado y se colocó en la posición 100 , con 3 problemas resuletos y 368 minutos de penalidad, dejando por detrás 40 equipos y entre ellos 12 latinoamericanos. En total participaron 22 equipos latinoamericanos.

Esta vez sin duda alguna pueden decir que están entre los 100 mejores equipos del mundo!! :D

Recordemos que el equipo KFP había quedado en 3er lugar en la pasada regional caribeña. El que quedó en 1er lugar en aquella ocasión fue el de la Pontificia Universidad Católica Madre y Maestra que esta vez quedó en el lugar 106 .

Felicidades a todos los equipos que nos representaron y en especial a KFP !

A continuación pueden ver los resultados de los 4 equipos caribeños y los 13 primeros lugares que fueron los que obtuvieron las medallas (4 de oro, 4 de plata y 5 de bronce).


Recursos
- Ranking completo png ( 1.3 MB ), oficial ( este link no funcionará en el futuro )
- Problemas pdf ( 1.6 MB )
- Broadcast youtube

Read more

ACM ICPC World Finals 2018 by leandro 6 months, 1 week ago

ACM ICPC 2018 World Final Poster

Ya comenzó la Final Mundial del ACM-ICPC del 2018, este año celebrada en Beijing (China) en la Universidad de Pekín . Tres equipos de nuestro país estarán compitiendo y esperamos buenos resultados. La final comenzó ayer 15 de abril (domingo) y terminará el próximo viernes 20 de abril. La competencia de práctica será el miércoles 18 de abril y el concurso real el jueves 19 de abril. Un total de 22 equipos latinoamericanos estarán participando en la final, a continuación mostramos los integrantes de cada uno de ellos.

Equipos Cubanos (3)

Universidad de Pinar del Río
sUrPRise
sUrPRise
De izquierda a derecha : Manuel Alejandro Díaz Pérez, José Guerra Carmenate, Luis Manuel Díaz Barón (coach), Elio Alejandro Govea Aguilar
full image ( 4.6 MB )


Universidad de Oriente - Sede Antonio Maceo
Netscape
Netscape
De izquierda a derecha : Aurora Gil Pons, Alexander Bestard Rivera, Reynaldo Gil Pons (coach), Ernesto David Peña Herrera
full image ( 4.7 MB )

Universidad Central "Marta Abreu" de Las Villas
KFP
KFP De izquierda a derecha : Daniel Enrique Cordovés Borroto, Niuber Ramirez Grey, José Daniel Rodríguez Morales (coach), Ruddy Guerrero Álvarez
full image ( 4.7 MB )

Equipos Argentinos (2)
Universidad Nacional de Córdoba - FaMAF
Gracias Demetrio
Gracias Demetrio
De izquierda a derecha : Matías José Hunicken Berardo, Luis Ferroni Rivetti, Martin Rodriguez (coach), Ezekiel Carranza
full image ( 4.6 MB )
Universidad Nacional de Rosario
Flower Power
Flower Power
De izquierda a derecha : Fernando Jesús Fiori, Margarita Capretto, Martín Villagra (coach), Emilio López
full image ( 4.6 MB )
Equipos Brasileños (7)
Instituto Militar de Engenharia
Lorem Ipsum
Lorem Ipsum
De izquierda a derecha : Naum Azeredo Fernandes Barreira, Matheus Cariús Castro, Claudia Justel (coach), Athos Couto
full image ( 3.9 MB )
Universidade de São Paulo
¯\_( "/ )_/¯
¯\_( "/ )_/¯
De izquierda a derecha : Victor Sena Molero, Arthur Nascimento, Renzo Gomez (coach), Yan Couto
full image ( 4.8 MB )
Universidade de São Paulo - Campus de São Carlos
Trei Linha
Trei Linha
De izquierda a derecha : Lucas de Oliveira Pacheco, Rodrigo Weigert, Danilo Tedeschi (coach), Samuel Santos
full image ( 9.7 MB )
Universidade Federal de Campina Grande
Choose difficulty: TITAN
Choose difficulty: TITAN
De izquierda a derecha : Felipe Mota dos Santos, Árysson Cavalcanti Figueiredo, Ordan Silva Santos, Rohit Gheyi (coach, no está en la foto)
full image ( 4.3 MB )
Universidade Federal de Pernambuco
ALT
ALT
De izquierda a derecha : Tiago Goncalves, Arthur Costa, Katia Guimarães (coach), Lucas Santana
full image ( 3.5 MB )
Universidade Federal do Rio de Janeiro
Esse é meu time
Esse é meu time
De izquierda a derecha : Tiago Montalvão, Igor Figueiredo, Marcia Cerioli (coach), Ian Miranda
full image ( 5.4 MB )
Universidade Federal do Rio Grande do Norte
Ginga com Tapioca
Ginga com Tapioca
De izquierda a derecha : Hélio Duarte, Railton Calheiros, Carlos Augusto Prolo (coach), Victor Lima
full image ( 4.4 MB )
Equipos Chilenos (1)
Universidad de Chile
No importa entrenen weon
No importa entrenen weon
De izquierda a derecha : Javier Oliva, Pablo Astudillo, Jorge Perez (coach), Matias Ramirez
full image ( 4.5 MB )
Equipos Colombianos (2)
Universidad Nacional de Colombia - Bogotá
UNschwifty
UNschwifty
De izquierda a derecha : Manuel Alejandro Vergara Díaz, Daniel Augusto Caceres Salas, Diego Said Niquefa Velásquez (coach), Víctor Gabriel Ramírez Caballero
full image ( 4.5 MB )
Universidad Tecnologica de Pereira
No name available
No name available
De izquierda a derecha : Carlos Andrés Arias Londoño, Yeferson Gaitan Gomez, Hugo Humberto Morales Peña (coach), Manuel Felipe Pineda
full image ( 4.2 MB )
Equipos Costarricenses (1)
Universidad de Costa Rica
TicoBits
TicoBits
De izquierda a derecha : Melvin Alonso Elizondo Perez, Diego Ugalde Ávila, Rodrigo Antonio Chaves Fernández, Edy Miguel Ramírez-Jiménez (coach, no está en la foto)
full image ( 4.5 MB )
Equipos Dominicanos (1)
Pontificia Universidad Católica Madre y Maestra
Firefox
Firefox
De izquierda a derecha : Michael Gonzales, Sarahaime Rodríguez, Carlos Toribio (coach), Angel Gonzalez
full image ( 4.2 MB )

Equipos Mejicanos (3)
Facultad de Ciencias-UNAM
PU++
PU++
De izquierda a derecha : Jorge Fernández Hidalgo, Santiago Ley Flores, Manuel Alcantara Juárez (coach), Luis Enrique Chacón Ochoa
full image ( 4.1 MB )

ITESM Campus Queretaro
Pragma
Pragma

De izquierda a derecha : Guillermo Salvador Barrón Sánchez, Fabian Gomez Gonzalez, Pedro Pérez (coach), Iván Alejandro Soto Velázquez
full image ( 3 .7 MB )

Universidad Autónoma de Nuevo Leon
Los A´s
Los A´s
De izquierda a derecha : Ángel Domínguez, José Tapia, María Chávez (coach), Victor Hugo Antonio De La Fuente Jimenez
full image ( 10.2 MB )
Equipos Peruanos (1)
Pontificia Universidad Católica del Perú - FCI
O(1) O(n) O(u(n))
O(1) O(n) O(u(n))
De izquierda a derecha : Rodrigo Manuel Horruitiner Mendoza, Paul Michael Luyo Carbonero, Jesús Peña (coach), Jesús Alonso Espino Luna
full image ( 4.6 MB )
Equipos Venezolanos (1)
Universidad Central de Venezuela
Super Pollos
Super Pollos
De izquierda a derecha : Satoru Díaz Nakada, Samuel Nacache, Héctor Navarro (coach), Leonardo Santella
full image ( 4.6 MB )


Recursos
- Descargar schedule : 2018-schedule.png ( 132.7 kB )
- Sitio oficial: http://www.icpc2018.org/

Read more

Soporte para JavaScript by leandro 6 months, 2 weeks ago

Hola a todos, hoy agregamos JavaScript al grupo de lenguajes en el MOG. Estamos usando precisamente V8 la versión 4.8.0.


Esto es un ejemplo del problema A+B en JavaScript
var tokens = readline().split(' '); 
var a = parseInt(tokens[0]);
var b = parseInt(tokens[1]);
print(a+b);

Aquí puede descargar V8 compilado para windows: link (29.7 MB)

Para ejecutar un archivo main.js debe utilizar el comando: d8 main.js

Read more

IV Copa UH ACM-ICPC by otero1991 6 months, 2 weeks ago


Hola a todos! El Sábado 7 de abril a las 10:30 am tendremos la 4ta copa UH de programación competitiva ACM-ICPC. La competencia estará abierta para que participen todos los interesados! Entra en http://www.matcomgrader.com/contests/ para que te registres. Tendrá una duración de 4 horas y previamente se realizará una sesión de práctica.

Patrocinado por Viera Academy !


Resultados de la III Copa: http://matcomgrader.com/contest/standing/6197

Resultados de la II Copa: http://matcomgrader.com/contest/standing/5185

Resultados de la I Copa: http://matcomgrader.com/contest/standing/3145

En las tres ediciones anteriores ganó UH++. Quién ganará este año?

Nota sobre los lenguajes
- La clase principal de los envíos en Java debe llamarse Main.
- CPython es la implementación de Python2 (2.7.13) y Python3 (3.5.3) en el sistema.
- Los módulos para python son:
modules.py2.txt , modules.py3.txt

Registro
Aconsejamos no utilizar correos nacionales (.cu) por varias razones: algunos servidores solo admiten correos nacionales, otros pueden tener problemas con la cuota, si eres estudiante es probable que al terminar la carrera pierdas el correo, etc. Por estas razones usted debería usar un servidor de correo más robusto: gmail , yahoo , outlook , etc.

Read more

MOG Round #33 - Discussion by Norge 6 months, 3 weeks 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

Dado un grafo $G$ y bonificaciones $a_i$ (cada vez que se visite el nodo $i$) calcular el valor esperado ( wiki ) de bonificaciones de un camino aleatorio si la distribución inicial de la probabilidad es $p_0 = \frac{d(i)}{2m}$, donde $d(i)$ es el grado del nodo $i$ y $m = |E(G)|$.

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 )

Read more