Dada una sequencia de n
números, puedes tomar cualquier prifijo y sufijo de la secuencia e invertir el signo de los elementos del prefijo o sufijo tomado. Determina cual es la máxima suma de elementos que puedes conseguir.
Sea:
left[i]:
máxima suma conseguida en $[1, i]$ tomando algún prefijoright[i]:
máxima suma conseguida en $[i, n]$ tomando algún sufijoLuego, la respuesta sería max(left[i] + right[i + 1]
$\mid \quad i \in [1, n]$ )
Ahora, notamos que (en clase se explicará con más detalle esto):
left[0] = 0
left[i] = max(left[i - 1] + arr[i], abs(sum(1, i)))
right[n + 1] = 0
right[i] = max(right[i + 1] + arr[i], abs(sum(i, n)))
Donde: sum(i, j) = suma de los elementos entre i y j
Así, con las relaciones anterior podemos calcular la respuesta en O(n)
Dados n
puntos. Determinar la cantidad de tripletas (A, B, C)
donde B
sea punto medio de A
y C
.
Si fijamos los puntos A
y C
, podemos calcular B
y si guardamos todos los puntos en un set podemos determinar en O(log n)
si B
es un punto dado en la entrada (sumando 1 a nuestra respuesta). Asi, podemos solucionarlos en $\text{O(} n ^ 2 \log n \text{)}$
Extra: ¿Cómo podríamos solucionarlo en $\text{O(} n ^ 2 \text{)}$ ?
Dado un array de n
elementos. Determinar dos índices $i, j$ $(arr[i] \not = arr[j] \land i < j)$ de manera que al intercambiar las posiciones de $i$ y $j$ el array no este ordenado de forma ascendente ni descentente.
Sea $(i, j)$ las posiciones a intercambiar.
Si $arr[i] < arr[j]$. Si al cambiarlas el array no queda ordenado de forma descendente, tenemos una respuesta. Sino el array tiene la forma
$$arr_1 \geq arr_2 \geq \dots arr_j \geq \dots \geq arr_i \geq \dots \geq arr_n $$De manera que ya no podríamos encontrar otro par $(i, j) \mid arr[i] < arr[j]$
Si $arr[i] > arr[j]$. Si al cambiarlas el array no queda ordenado de forma ascendente, tenemos una respuesta. Sino el array tiene la forma
$$arr_1 \leq arr_2 \leq \dots arr_j \leq \dots \leq arr_i \leq \dots \leq arr_n $$De manera que ya no podríamos encontrar otro par $(i, j) \mid arr[i] > arr[j]$
Así, podemos buscar un par $(i, i + 1) \mid arr[i] < arr[i + 1]$ y otro par $(i, i + 1) \mid arr[i] > arr[i + 1]$. Si encontramos esos pares y con ninguno encontramos una respuesta. Entonces, no hay respuesta.
Luego, lo anterior podemos implementarlo en O(n)
o O(n log n)
Dado un array de n
numereros. Encontrar el tamaño de la secuencia más grande que se puede formar con los elementos del array (cada elemento es tomado a lo más una vez) donde la secuencia es de la forma.
Si fijamos $f_0$ y $f_1$ podemos simular ir formando la secuencia deseada (notemos que $f_0 = f_1 = 0$ podemos tratarlo
como un caso especial). Así, podriamos lograr una solución
O(n * n * k)
donde k
sería el tamaño de la secuencia más larga donde ($f_0 \not = 0 \lor f_1 \not = 0$).
Pero recordamos que en una clase previa mostramos como para $f_0 = 0, f_1 = 1, f_{95} > 10 ^ {18}$. Luego, notamos que para otros $f_0, f_1$ definitivamente antes del término 95 la secuencia tendrá un valor absoluto mayor a 10 a la 9.
Así, nuestra solución O(n * n * k)
debería pasar.
Nota: En esta implementación se uso un mapa para la simulación, por lo que en realidad la complejidad es O(n * n * k * log k)
Extra: En el código anterior, esta sección:
int c = (a + b);
if (frec[c] == 0) break;
frec[c]--;
Hace que tengamos que buscar el elemento c
dos veces en el mapa, y esta operación se hace un gran cantidad de veces.
Luego, se podría hacer esto para reducir un poco el tiempo de ejecución:
int c = (a + b);
int& f = frec[c]; // una referencia a frec[c]
if (f == 0) break;
f[c]--;
Ya que solo buscamos a c
una vez en el mapa (como ya tenemos la referencia f[c]--
es O(1)
)
Tienes n
amigos. El amigo i
te enviará la tarjeta i
(comenzará el primer amigo, luego el segundo, ...).
Cada amigo tiene una lista de preferencencias de que tarjeta le gustaría recibir y tu tienes una lista de preferencia de que tarjeta te gustaria enviar. Para enviar una tarjeta al amigo i
debes seguir las siguientes reglas:
i
.i
, la tarjeta que le piensas enviar ahora tiene que tener mayor preferencia para i
.Básicamente, así podemos interpretar el enunciado por practicidad.
Podemos simular lo descrito en el enunciado en O(n * n * n)
. Ver la implementación para más detalles.
Dado $t_1, t_2, t_0, x_1, x_2$
Sea
$$t(y_1, y_2) = \frac{y_1 * t_1 + y_2 * t_2}{y_1 + y_2} \mid 1 \leq y_1 \leq x_1 \land 1 \leq y_2 \leq x_2$$Encontrar para que valores de $y_1, y_2$, $t(y1, y2)$ es lo más cercano posible a $t_0$. En caso de múltiples respuestas imprimir aquella donde $y1 + y2$ es máximo.
Luego, podemos fijar $y_1$, calcular $y_2$ a partir de ello e ir maximixando la respuesta.
Así, podemos resolver el problema en O(x_1)
Nota: Tener cuidado con la precisión.
Dado
$$s_1s_2 \cdots s_n \quad \mid s_i \in \{<, >, 1, 2, \cdots, 9\}$$Recibirás q
consultas de la forma l r
. En cada consulta debes simular la
ejecución de
e imprimir la cantidad de veces que se imprimio cada dígito (0-9
)
Para simular la ejecución de la secuencia $s_l \cdots s_r$ usted comienza en la
posicion l
en la direccion derecha. Ahora:
vuelve negativo, eliminalo de la secuencia.
<
o >
cambia la dirección hacia la izquida
o derecha respectivamente. Luego, muevete en tu dirección actual. Si lasentencia en tu posición actual es <
o >
, elimina la sentencia de tu
anterior posición.
[l, r]
. Termina la simulación.$$1 \leq n, q \leq 100 $$
En el peor de los casos (una consulta de al forma >99...99<
) la simulación
se hara en O(n)
Luego, bastará simular la ejecución de cada consulta siguiendo la descripción
del enunciado para obtener una solución en O(q n)
Nota: Tener cuidado, las consultas son independientes entre sí.
Se tiene una secuencia $a_1, a_2, \cdots a_n$ donde algunos dígitos han sido
reemplazados por ?
. Ahora, deberás reemplazar los ?
por dígitos de tal
forma que
e imprimir dicha secuencia (si hay multiples respuestas, imprime alguna válida)
o indicar que es imposible formar tal secuencia. Tener en cuenta que los
números formados no pueden tener 0
como primer dígito.
Si ya tengo formado el número $a_i$. Para formar $a_{i + 1}$ puedo intentar formar un número mayor que $a_i$ lo menor posible.
Si $a_{i + 1} > a_i$ y ambos tienen la misma cantidad de dígitos. Entonces ambos tendrán la forma: $$a_i = \overline{xmy}$$ $$a_{i + 1} = \overline{xnz}$$
Y $n > m$ y $z$ puede tomar cualquier forma.
Luego, para hacer $a_{i + 1}$ lo más pequeño posible, nos conviene hacer $n = m + 1$ y hacer que z
sea tan pequeño como sea
posible (para lo cual nos conviene completar con 0
s los ?
en z
).
Así, simplemente cada ?
en $a_{i + 1}$ puedo tomarlo como la posición de n
e intentar formar $a_{i + 1}$ y al final tomar el menor $a_{i + 1}$ formado (Si
no logro formar ningun $a_{i + 1}$ entonces no hay respuesta). Como $a_i$ tiene
a lo mucho 8
digitos. Entonces, en O(8 * 8) = O(1)
podemos formar todas las
posibilidades de $a_{i + 1}$.
Finalmente, puedo agrupar los números dados por su cantidad de dígitos. Ir completando
los ?
con lo anterior descrito. Juntar todas las secuencia y comprobar si se
forma una respuesta válida en O(n)
.
Sea:
$$D(x) = \{ \text{Los divisores de x ordenados de menor a mayor} \} $$$$f_0(x) = \{x\}$$$$f_k(x) = \bigcup_{d \in D(X)} f_{k -1}(d)$$Recibirás un x, d
y deberás imprimir los primos $10 ^ 5$ términos de $f_k(x)$
Notemos que: $$f_k(p) = \{1\} \times k \quad \bigcup \quad \{p\} \quad \mid p \text{ es primo }$$ $$f_k(1) = \{1\}$$
Luego, notemos que bastará simular la recurrencia anterior mientras mantenemos un contador de cuantos números ya hemos imprimido (lo cual nos indicará cuando detenernos)
Ahora, necesitamos tener un vector con los divisores que necesitaremos de manera rápida. Para ello podemos fijar una constante, por ejemplo
$$ \text{MX}= 10 ^ 5 $$Preprocesar todos los divisores de los números $< \text{MX}$ en O(MX log MX)
y aquellos $x \geq \text{MX}$ en $\text{O(}\sqrt{x} \text{)}$ (Se explicará esto en clase).
Consiguiendo así una solución en $\text{O(} \sqrt{x} + \text{MX} \log \text{MX} \text{)}$
Dado
$$a, b, c, n$$$$\text{Encontrar: } \max(x + y + z \mid x \cdot a + y \cdot b + z \cdot c = n \land x, y, z \geq 0)$$$$1 \leq a, b, c, n \leq 4000$$Podemos fijar $(x, y)$ y partir de ello determinar $z$ en O(n * n)
Dado n
palabras. Sea
Encontrar $$max(f(ch1, ch2) \mid ch2, ch2 \in a, b, \dots, c)$$
$$1 \leq n \leq 100$$$$1 \leq MAX_LEN \leq 1000$$Podemos fijar (ch1, ch2) y ver cuantas palabras cumplen la condición en O(26 * 26 * n * MAX_LEN)