Dado un array $a_1, a_2, \dots a_n$. Encontrar cuantas tuplas $(x, y)$ existen tal que
$$1 \leq x < y < n \land \displaystyle\sum_{i = 1}^{x} a_i = \displaystyle\sum_{x + 1}^{y} a_i = \displaystyle\sum_{y + 1}^{n} a_i$$$$1 \leq n \leq 10 ^ 5$$$$-10 ^ 4 \leq a_i \leq 10 ^ 4$$Hint: Fija el primer elemento de la tupla
Link del problema
Solución
Recibirás dos números $a, b$ seguido que $q$ consultas de la forma $l, r$.
Para cada consulta imprime el máximo $d \in [l, r]$ tal que $d$ sea divisor de $a$ y $b$ o $-1$ si tal $d$ no existe.
$$1 \leq a, b \leq 10 ^ 9$$$$1 \leq q \leq 10 ^ 4$$$$1 \leq l \leq r \leq 10 ^ 9$$Hint: $\sigma_0 (n) = O(n ^ {1 / 3})$ (La demostración está en el Apéndice 1)
Nota: $sigma_0 (n)$ es la cantidad de divisores de $n$
Tiene n
cajas con $a_i$ caramelos en la i-esima caja. Debes repartir esos caramelos entre $k$ niños de tal manera que cada niño obtenga la misma cantidad de caramelos y que estos sean de una misma caja. ¿Cuál es la mayor cantidad de caramelos que un niño puede recibir?
Hint: Si cada niño puede recibir $x$ caramelos, entonces cada niño también puede recibir $x - 1$ caramelos
Link del problema
Solución
$N_0 = 1$
$N_i = N_{i - 1} + f(N_{i - 1})$
donde $f(x) = $ número de divisores de $x$
Recibirás $T$ consultas de la forma $l, r$ y deberás responder cuantos $i$ existen tal que $l \leq N_i \leq r$.
$$1 \leq T \leq 10 ^ 5$$$$1 \leq l \leq r \leq 10 ^ 6$$Hint1: La secuencia es creciente
Hint2: Podemos generar la cantidad de divisores de $1, 2, \dots n$ en $O(n log n)$
Hint3: podemos generar la secuencia hasta el máximo elemento que necesitaremos
Link del problema
Solución
Recibirás una matrix de $n \times m$ donde cada fila será una permutacion de $1 ... m$. Tienes permitido escojer (una sola vez) dos columnas (posiblemente las mismas) y cambiar sus elementos y para cada fila tienes permitido escojer (una sola vez) dos posiciones (posiblemente las mismas) y cambiar sus elementos. Las anteriores operaciones las puedes realizar en cualquier orden.
Tu tarea consiste en imprimir 'SI' en caso es posible obtener la matriz de $n \times m$ donde cada fila es la permutación identidad de $m$ elementos $(1, 2, 3, \dots, m)$ usando las operaciones anteriormente descritas o 'NO' en caso no sea posible.
$$1 \leq n, m \leq 20$$Hint1: Podemos probar todos los posibles pares de columnas a intercambiar en $O(n ^ 3)$
Hint2: Podemos saber cuantos intercambios son necesarios en una fila en $O(n)$
Link del problema
Solución
Un número de la suerte es un número donde sus dígitos son $4$ o $7$. Por ejemplo, $4, 7, 44, 47, 77$ son números de la suerte.
Sea:
$next(x) = $ menor número de la suerte que es mayor o igual a $x$
Recibirás dos números $l, r$ y deberás imprimir $next(l) + next(l + 1) + \dots + next(r)$ (se garantiza que la respuesta puede ser almacena en un entero de 64-bits)
$$1 \leq l \leq r \leq 10 ^ 9$$Hint: La cantidad de números de la suerte en el rango necesitado es poco
Link del problema
Solución
Dos números $a, b$ se dice que son $k-$interesantes si su representación binaria difiere en exactamente $k$ bits. Dado $n, k$ y una secuencia $a_1, a_2, \dots a_n$. Determinar cuantos pares $(i, j)$ existen tal que $i < j$ y $a_i, a_j$ son $k-$ interesantes.
$$1 \leq n \leq 10 ^ 5$$$$0 \leq k \leq 14$$$$0 \leq a_i \leq 10 ^ 4$$Hint1: Los valores $a_i$ son pequeños
Hint2: La cantidad de distintos pares de números $a[i], a[j]$ que difieran en $k-$bits es poco
Link del problema
Solución
Recibirás un entero $n$ seguido de $n$ números $a_1, a_2, \dots, a_n$. Debes retornar a cantidad de pares $(i, j)$ tal que $i < j \land a_i$ y $a_j$ tengan algun dígito en común (no necesariamente en la misma posición).
$$1 \leq n \leq 5 \cdot 10 ^ 5$$$$1 \leq a_i \leq 10 ^ {18}$$Hint: Se puede representar un número como una máscara que indique que digitos tiene el número usando 10-bits
Link del problema
Solución
Recibirás un $n$ seguido de una sudoku de $n ^ 2 \times n ^ 2$ donde los espacios que aún no se han completado tendrán 0's. El objetivo es imprimir la solución del sudoku con el menor orden lexicográfico o imprimir 'NO SOLUTION' en caso de no tener solución el sudoku dado.
Por ejemplo, para $n = 3$, si se recibe el sudoku de la izquierda, se deberá retornar el sudoku de la derecha.
Hint: Backtracking
Link del problema
Solución
Afimación: $\sigma_0(n) = O(n ^ {1/ 3)}$
Prueba:
$sigma_0$ es una función multiplicativa. Luego, observamos que es suficiente demostrar que lo anterior se cumple para un $n = p ^ k$ (pues para un $n$ que no tenga esa forma bastará usar la representación prima de este número y manipular unas desigualdades)
Y como queremos encontrar $\sigma_0(n) = O(n ^ {1/ 3)}$ bastará con demostrar que lo anterior se cumple a partir de un $n$ lo suficientemente grande (en este caso, para $p > 8$)
Los divisores se $p ^ k son \{1, p, p ^ 2, \dots, p ^ k\}$
$$\to \sigma_0 (p ^ k) = k + 1 \leq 2 ^ k$$$$\to \sigma_0 ^ 3 (p ^ k) \leq 8 ^ k < p ^ k$$$$\to \sigma_0(p ^ k) = O((p ^ k) ^ {1 / 3} )$$Por lo tanto, $\sigma_0(n) = O(n ^ {1/ 3)}$