Editorial for C-3BA y las Subsecuencias

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: humbertoyusta

Subtarea 1: $a_i \leq 2$ ~a_i \leq 2~

Denotemos $dp_{i, 1}$ ~dp_{i, 1}~ como la cantidad de subsecuencias de $a_1, a_2, ... a_i$ ~a_1, a_2, ... a_i~ que cumplen con las condiciones y terminan en $1$ ~1~ (el otro elemento de la subsecuencia es $2$ ~2~).

Similarmente, $dp_{i, 2}$ ~dp_{i, 2}~ será la cantidad de subsecuencias de $a_1, a_2, ... a_i$ ~a_1, a_2, ... a_i~ que cumplen con las condiciones y terminan en $2$ ~2~ (el otro elemento de la subsecuencia es $1$ ~1~).

Realizando un ciclo de $1$ ~1~ a $n$ ~n~, en cada paso $i$ ~i~ se puede notar que:

Si $a_i = 1$ ~a_i = 1~:

$dp_{i, 2} = dp_{i-1, 2}$ ~dp_{i, 2} = dp_{i-1, 2}~ (ya que no hay ninguna subsecuencia nueva que termine en $1$ ~1~)
$dp_{i, 1} = dp_{i-1, 1} + dp_{i-1, 2}$ ~dp_{i, 1} = dp_{i-1, 1} + dp_{i-1, 2}~ (las anteriores, o las que terminaban en 2, añadiendole el actual $1$ ~1~)

Similarmente, si $a_i = 2$ ~a_i = 2~:

$dp_{i, 1} = dp_{i-1, 1}$ ~dp_{i, 1} = dp_{i-1, 1}~ (ya que no hay ninguna subsecuencia nueva que termine en $2$ ~2~)
$dp_{i, 2} = dp_{i-1, 1} + dp_{i-1, 2}$ ~dp_{i, 2} = dp_{i-1, 1} + dp_{i-1, 2}~ (las anteriores, o las que terminaban en 1, añadiendole el actual $2$ ~2~)

Finalmente, la respuesta es $dp_{n, 1} + dp_{n, 2}$ ~dp_{n, 1} + dp_{n, 2}~.

Tiempo $O(n)$ ~O(n)~, memoria $O(n)$ ~O(n)~.

Subtarea 2: $n \leq 16$ ~n \leq 16~

En esta subtarea $n$ ~n~ es suficientemente pequeño para probar todos los subconjuntos, por ejemplo usando máscaras de bits para simular cada subconjunto, y en cada uno de ellos realizar un ciclo para chequear que cumpla las condiciones del problema.

Tiempo $O(2^n \cdot n)$ ~O(2^n \cdot n)~, memoria $O(n)$ ~O(n)~.

Subtarea 3: $n \leq 400$ ~n \leq 400~

En esta subtarea, podemos probar para cada par $(x, y)$ ~(x, y)~ tal que $1 \leq x, y \leq n$ ~1 \leq x, y \leq n~ y $x \neq y$ ~x \neq y~, y para cada uno de ellos contar la cantidad de secuencias que cumplen las propiedades que los contienen como elementos, para un par específico podemos usar la misma solución de la subtarea 1.

Tiempo $O(n^3)$ ~O(n^3)~, memoria $O(n)$ ~O(n)~

Subtarea 4: Cada número aparece a lo más dos veces en el arreglo.

Como cada número aparece a lo más dos veces en el arreglo, las subsecuencias que cumplan las propiedades tendrán longitud a lo más 4, veamos para cada longitud en específico como contar la cantidad de subsecuencias de esta longitud.

Denotemos $fst_x$ ~fst_x~ como la primera vez que aparece el elemento $x$ ~x~ en el arreglo (si aparece) y $scd_x$ ~scd_x~ como la segunda vez que aparece el elemento $x$ ~x~ en el arreglo (si aparece dos veces)

Subsecuencias de longitud 2, cada par de elementos diferentes del arreglo, lo cual se puede contar de manera sencilla con dos ciclos.
Subsecuencias de longitud 3, seguirán el patrón $x, y, x$ ~x, y, x~, para cada par $(i, j)$ ~(i, j)~ tal que $i < j$ ~i < j~ y $a_i = a_j$ ~a_i = a_j~, habrán $j - i - 1$ ~j - i - 1~ de estas secuencias (cualquier elemento entre ellos será diferente, y entre los 3 formarán una subsecuencia válida), se puede contar con dos ciclos chequeando los pares de elementos iguales y contando.
Subsecuencias de longitud 4, seguirán el patrón $x, y, x, y$ ~x, y, x, y~, para cada par $(x, y)$ ~(x, y)~ tal que $1 \leq x, y \leq n$ ~1 \leq x, y \leq n~, $x \neq y$ ~x \neq y~ y $x$ ~x~ y $y$ ~y~ aparecen dos veces, existe una ocurrencia de este tipo si y solo si $fst_x < fst_y < scd_x < scd_y$ ~fst_x < fst_y < scd_x < scd_y~, se puede contar con dos ciclos sobre $x$ ~x~ y $y$ ~y~, y luego de manera sencilla para cada par se chequea si forman o no una subsecuencia de este tipo.

Tiempo $O(n^2)$ ~O(n^2)~, memoria $O(n)$ ~O(n)~

Subtarea 5: Sin restricciones adicionales.

Denotemos $dp_{i, x, y}$ ~dp_{i, x, y}~ como la cantidad de subsecuencias que terminan en $y$ ~y~, el penúltimo elemento es $x$ ~x~ y están contenidas en $a_1, a_2, ... a_i$ ~a_1, a_2, ... a_i~.

Procesemos todos los elementos de izquierda a derecha, así podremos calcular $dp_i$ ~dp_i~ basado en $dp_{i-1}$ ~dp_{i-1}~, las transiciones serían:

$dp_{i, x, y} = dp_{i - 1, x, y}$ ~dp_{i, x, y} = dp_{i - 1, x, y}~ si $a_i \neq x$ ~a_i \neq x~.
$dp_{i, a_i, x} = \sum_{j = 1, j \neq a_i}^{n} dp_{i - 1, x, a_i}$

Una implementación ingenua de esta $dp$ ~dp~ tomaría $O(n^3)$ ~O(n^3)~ tiempo y memoria, pero la dimensión de $i$ ~i~ no es necesaria, simplemente $dp_{x, y}$ ~dp_{x, y}~ es la cantidad de subsecuencias que terminan en $y$ ~y~, el penúltimo elemento es $x$ ~x~, y están contenidas en el prefijo que hemos procesado. Las transiciones son aproximadamente las mismas, la primera transición no es necesaria ahora (iría de un estado a si mismo), con esto se obtiene una solución en $O(n^2)$ ~O(n^2)~ tiempo y memoria, en cuanto a tiempo es suficiente, pero usa demasiada memoria (el límite del problema es 16 MB).

Trucos usuales de ahorrar memoria no funcionan de manera ingenua, por lo cual intentaremos hacer un ciclo sobre cada elemento $x$ ~x~ $(i \leq x \leq n)$ ~(i \leq x \leq n)~ y contar la cantidad de subsecuencias válidas que terminan en $x$ ~x~.

Denotemos como $dp_{y, 0}$ ~dp_{y, 0}~ la cantidad de subsecuencias que terminan en $y$ ~y~, y su otro elemento es $x$ ~x~, y $dp_{y, 1}$ ~dp_{y, 1}~ la cantidad de subsecuencias que terminan en $x$ ~x~, y su otro elemento es $y$ ~y~.

Procesamos todos los elementos de izquierda a derecha (noten que hemos fijado $x$ ~x~ antes), las transiciones serían:

$dp_{a_i, 0} += dp_{a_i, 1}$ ~dp_{a_i, 0} += dp_{a_i, 1}~ si $a_i \neq x$ ~a_i \neq x~ (esta transición se hace en $O(1)$ ~O(1)~)
$dp_{y, 1} += dp_{y, 0}$ ~dp_{y, 1} += dp_{y, 0}~, para todo $1 \leq y \leq n, y \neq x$ ~1 \leq y \leq n, y \neq x~ si $a_i = x$ ~a_i = x~ (esta transición se hace en $O(n)$ ~O(n)~, pero en total se hará $n$ ~n~ veces porque hemos fijado $x$ ~x~ y solo la hacemos si $a_i = x$ ~a_i = x~)

Luego de procesar todos los elementos de izquierda a derecha, añadimos $\sum_{y = 1, y \neq x}^{n} dp_{y, 1}$ ~\sum_{y = 1, y \neq x}^{n} dp_{y, 1}~ a la solución.

Luego de fijar cada posible $x$ ~x~, tendremos la respuesta del problema.

Tiempo $O(n^2)$ ~O(n^2)~, memoria $O(n)$ ~O(n)~.

Comments

There are no comments at the moment.