Longest Beautiful Subsequence

Explicación

Resolver este problema de una sola vez es extremadamente difícil: recorramos primero las subtareas.

Subtareas 1-2

Debido a las cotas pequeñas de $N$ , basta una solución $\mathcal{O}(N^2)$ .

Definimos $\texttt{dp}[i]$ como la longitud de la LBS (subsecuencia bella más larga) más larga que termina en $i$ , y $\texttt{trans}_k(y)$ como todos los $x$ tales que $x \hspace{3pt} \& \hspace{3pt} y$ tiene $k$ bits. Transicionamos iterando sobre todos los $j < i$ donde $a_j \in \texttt{trans}_{k_i}(a_i)$ . Para reconstruir una solución óptima definimos otro arreglo $\texttt{prv}$ , donde $\texttt{prv}[i]$ es el índice más óptimo a incluir justo antes del índice $i$ .

Consideremos el primer caso de ejemplo: $n = 4$ , $a = \{1, 2, 3, 4\}$ , y $k = \{10, 0, 1, 0\}$ .

Caso base: $\texttt{dp}[i] = 1$ para todo $i$ (cualquier número suelto forma una LBS) y $\texttt{prv}[i] = i$ .
$\texttt{dp}[1]$ : intentamos extender la LBS más larga que termina en $a_0 = 1$ . Como $\texttt{bc}[a_0][a_1] == k_1$ , nuestra nueva LBS es válida, y actualizamos $\texttt{dp}[1] = \texttt{dp}[0] + 1 = 2$ y $\texttt{prv}[1] = 0$ .
$\texttt{dp}[2]$ : intentamos extender la LBS tanto desde $a_0$ como desde $a_1$ .
- $a_0$ : $\texttt{bc}[a_0][a_2] == k_2 \rightarrow \texttt{dp}[2] = \texttt{dp}[0] + 1 = 2$ y $\texttt{prv}[2] = 0$
- $a_1$ : $\texttt{bc}[a_1][a_2] == k_2 \rightarrow \texttt{dp}[2] = \texttt{dp}[1] + 1 = 3$ y $\texttt{prv}[2] = 1$
- Tomamos el mayor de los dos valores de DP, así que $\texttt{dp}[2] = 3$ y $\texttt{prv}[2] = 1$ .
$\texttt{dp}[3]$ : intentamos extender desde $a_0$ , $a_1$ y $a_2$ .
- $a_0$ : $\texttt{bc}[a_0][a_3] \neq k_3 \rightarrow$ no hay transición
- $a_1$ : $\texttt{bc}[a_1][a_3] == k_3 \rightarrow \texttt{dp}[3] = \texttt{dp}[1] + 1 = 3$ y $\texttt{prv}[3] = 1$
- $a_2$ : $\texttt{bc}[a_2][a_3] == k_3 \rightarrow \texttt{dp}[3] = \texttt{dp}[2] + 1 = 4$ y $\texttt{prv}[3] = 2$
- Tomando la mayor de las dos opciones, $\texttt{dp}[3] = 4$ y $\texttt{prv}[3] = 2$ .
Respuesta final: $\texttt{len} = \max(\texttt{dp}[i]_{i \in [0, n)}) = \texttt{dp}[3] = \boxed{4}$
Reconstrucción de una solución:
- Usando nuestro arreglo $\texttt{prv}$ y el índice final de la LBS, podemos hallar repetidamente el índice óptimo a incluir antes del actual.
- elegimos $i$ tal que $\texttt{dp}[i] = \texttt{len} = 4 \Rightarrow i = 3$
- inicializamos $ans$ como $\{i\} = \{3\}$ .
- Agregamos repetidamente $\texttt{prv}{[ans_0]}$ al frente de $ans$ .
  - $ans = \{\texttt{prv}[3], 3\} = \{2, 3\}$
  - $ans = \{\texttt{prv}[2], 2, 3\} = \{1, 2, 3\}$
  - $ans = \{\texttt{prv}[1], 1, 2, 3\} = \{0, 1, 2, 3\}$
  - $\texttt{prv}[0] = 0$ , así que terminamos.
- Por lo tanto, nuestra respuesta final (indexada desde cero) será $ans = \boxed{\{0, 1, 2, 3\}}.$

Implementación

Complejidad temporal: $\mathcal{O}(N^2)$

Código

C++


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) { cin >> a[i]; }
	vector<int> k(n);
	for (int i = 0; i < n; i++) { cin >> k[i]; }
 
	vector<int> dp(n, 1);
	int ans = 1;
	// best_i: índice más óptimo en el que terminar
	int best_i = 0;
	// prv[i] = índice óptimo a incluir justo antes de i
	vector<int> prv(n);
	// inicialmente, prv[i] = i
	iota(prv.begin(), prv.end(), 0);
 
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < i; j++) {
			// bc[a[j]][a[i]] == k[i]
			if (__builtin_popcount(a[j] & a[i]) == k[i]) {
				if (dp[j] + 1 > dp[i]) {
					prv[i] = j;
					dp[i] = dp[j] + 1;
				}
			}
		}
		if (dp[i] > ans) {
			ans = dp[i];
			best_i = i;
		}
	}
 
	cout << ans << endl;
 
	vector<int> res;
	while (prv[best_i] != best_i) {
		res.push_back(best_i);
		best_i = prv[best_i];
	}
 
	res.push_back(best_i);
	reverse(res.begin(), res.end());
	for (int x : res) { cout << x + 1 << " "; }
}

Subtarea 3

Aunque las cotas de $N$ ahora son mucho mayores ( $N \leq 10^5$ ), el valor máximo de $a_i$ ahora es solo $M = 2^8$ . Podemos usar esto para optimizar la solución: en lugar de recorrer cada índice previo posible, recorremos todos los valores previos posibles.

Más concretamente, definimos $\texttt{dp1}[i][x]$ como la longitud de la LBS más larga que termina con el valor $x$ (en lugar del índice) y es un subconjunto de los primeros $i$ números. Tenemos dos transiciones para cada índice $i$ :

Incluir $a_i$ : para calcular $\texttt{dp1}[i][a_i]$ , transicionamos desde $\texttt{dp1}[i - 1][x]$ para todo $x \in \texttt{trans}_{k_i}(a_i)$ .
No incluir $a_i$ : $\texttt{dp1}[i][x] = \texttt{dp1}[i - 1][x]$ para todo $x \leq M$ .

Esto mejora nuestra complejidad temporal a $\mathcal{O}(NM)$ . Notemos que, como $\texttt{dp1}[i][x]$ solo depende de $\texttt{dp1}[i - 1][...]$ , podemos eliminar la primera dimensión.

Consideremos de nuevo el primer caso de ejemplo: $n = 4$ , $a = \{1, 2, 3, 4\}$ , y $k = \{10, 0, 1, 0\}$ . El valor máximo es $M = 4$ .

Caso base: $\texttt{dp1}[a_0 = 1] = \{1, 0\}$ .
- todos los demás valores de DP empiezan en 0
- $\texttt{prv}[i] = i$
$\texttt{dp1}[a_1 = 2] = \{2, 1\}$ .
- recorremos todos los estados $\texttt{dp1}[x]$ donde $x \leq M$ y $x$ está en $\texttt{trans}_{k_i}(a_i)$ . Los valores de $x$ que cumplen estas condiciones son $0$ , $1$ y $4$ .
- De estos $x$ , $\texttt{dp1}[x = 1]$ tiene el mayor valor de len, así que:
  - $\texttt{dp1}[a_1]. \texttt{len} = \texttt{dp1}[x].\texttt{len} + 1 = 2$ .
  - $\texttt{dp1}[a_1].\texttt{end} = i = 1$ .
  - $\texttt{prv}[i] = \texttt{dp1}[x].\texttt{end} = 0$ .
$\texttt{dp1}[a_2 = 3] = \{3, 2\}$ .
- aquí, $x \in \{1, 2\}$ y $\texttt{dp1}[x = 2]$ tiene el mayor valor, así que:
  - $\texttt{dp1}[a_2]. \texttt{len} = \texttt{dp1}[x].\texttt{len} + 1 = 3$ .
  - $\texttt{dp1}[a_2].\texttt{end} = i = 2$ .
  - $\texttt{prv}[i] = \texttt{dp1}[x].\texttt{end} = 1$ .
$\texttt{dp1}[a_3 = 4] = \{4, 3\}$ .
- aquí, $x \in \{0, 1, 2, 3\}$ y $\texttt{dp1}[x = 3]$ tiene el mayor valor, así que:
  - $\texttt{dp1}[a_3]. \texttt{len} = \texttt{dp1}[x].\texttt{len} + 1 = 4$ .
  - $\texttt{dp1}[a_3].\texttt{end} = i = 3$ .
  - $\texttt{prv}[i] = \texttt{dp1}[x].\texttt{end} = 2$ .
Respuesta final: el máximo valor len de DP, $\boxed{4}$ .

Implementación

Complejidad temporal: $\mathcal{O}(NM)$

Código

C++


#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int B = 8;
struct State {
	int len, end;
};
int main() {
	// preprocess:
	// bc[i][j] = bit_count(i & j)
	vector<vector<int>> bc(1 << B, vector<int>(1 << B));
	for (int i = 0; i < (1 << B); i++) {
		for (int j = 0; j < (1 << B); j++) { bc[i][j] = __builtin_popcount(i & j); }
	}
 
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	vector<int> k(n);
	for (int i = 0; i < n; i++) cin >> k[i];
	int ans = 1;
	// best_i: índice más óptimo en el que terminar
	int best_i = 0;
	vector<int> prv(n);               // prv[i]: mejor índice a incluir antes de i
	iota(prv.begin(), prv.end(), 0);  // prv[i] = i
 
	vector<State> dp1(1 << B, State{-1, -1});
	for (int i = 0; i < n; i++) {
		if (dp1[a[i]].len == -1) {
			dp1[a[i]].len = 1;
			dp1[a[i]].end = i;
		}
		for (int j = 0; j < (1 << B); j++) {
			if (bc[j][a[i]] == k[i] && dp1[j].len + 1 > dp1[a[i]].len) {
				dp1[a[i]].len = dp1[j].len + 1;
				dp1[a[i]].end = i;
				prv[i] = dp1[j].end;
			}
		}
		if (dp1[a[i]].len > ans) {
			ans = dp1[a[i]].len;
			best_i = i;
		}
	}
 
	cout << ans << endl;
 
	vector<int> res;
	while (prv[best_i] != best_i) {
		res.push_back(best_i);
		best_i = prv[best_i];
	}
	res.push_back(best_i);
	reverse(res.begin(), res.end());
	for (int x : res) { cout << x + 1 << " "; }
}

Subtarea 3 (solución alternativa)

En nuestra solución previa para esta Subtarea 3, el bucle de $0...M$ parece repetitivo y motiva restringir de alguna forma el espacio de búsqueda de estados de DP. ¿Cómo podemos procesar rápido todos los $x$ en $\texttt{trans}_{k_i}(a_i)$ ?

La forma más extrema de optimizar las transiciones es incrustar las restricciones de $x$ directamente en el estado de DP.

Concretamente, definimos $\texttt{dp2}[i][k]$ como el valor máximo de $\texttt{dp1}[x]$ sobre todos los $x$ en $\texttt{trans}_k(i)$ .

Para entender mejor esta redefinición de nuestro estado de DP, miremos de nuevo el ejemplo. Notemos que, en el cálculo de $\texttt{dp1}[a_3 = 4]$ , procesamos todos los $x \in \{0, 1, 2, 3\}$ uno por uno. Sin embargo, en nuestro estado recién definido, podemos obtener la solución más óptima sobre todos los valores $x$ simplemente consultando $\texttt{dp2}[a_3][k_3]$ .

En general, $\texttt{dp2}[a_i][k_i]$ es ahora una transición $\mathcal{O}(1)$ para hallar la LBS más larga que termina en el índice $i$ .

Sin embargo, cada estado $\texttt{dp2}[i][k]$ ahora encapsula $|\texttt{trans}_k(i)| \leq M$ de nuestros estados $\texttt{dp1}$ originales. De forma similar, una LBS con valor final fijo $a_i$ afecta $M$ estados $\texttt{dp2}$ comparado con un estado $\texttt{dp1}$ : a saber, todos los estados $\texttt{dp2}[x][k]$ donde $x \in [0, M)$ y $k = \texttt{bc}[a_i][x]$ .

Implementación (`dp2`)

Código

C++


#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
 
const int B = 8;
struct State {
	int len, end;
};
int main() {
	// preprocess:
	// bc[i][j] = bit_count(i & j)
	vector<vector<int>> bc(1 << B, vector<int>(1 << B));
	for (int i = 0; i < (1 << B); i++) {
		for (int j = 0; j < (1 << B); j++) { bc[i][j] = __builtin_popcount(i & j); }
	}
 
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	vector<int> k(n);
	for (int i = 0; i < n; i++) cin >> k[i];
	int ans = 1;
	// best_i: índice más óptimo en el que terminar
	int best_i = 0;
	vector<int> prv(n);               // prv[i]: mejor índice a incluir antes de i
	iota(prv.begin(), prv.end(), 0);  // prv[i] = i
 
	vector<vector<State>> dp2(1 << B, vector<State>(B, State{0, -1}));
	for (int i = 0; i < n; i++) {
		// longitud de la LBS más larga que termina en i
		int len = dp2[a[i]][k[i]].len + 1;
		if (dp2[a[i]][k[i]].end != -1) { prv[i] = dp2[a[i]][k[i]].end; }
		for (int j = 0; j < (1 << B); j++) {
			State &affected_state = dp2[j][bc[a[i]][j]];
			if (len > affected_state.len) { affected_state = State{len, i}; }
		}
		if (len > ans) {
			ans = len;
			best_i = i;
		}
	}
 
	cout << ans << endl;
 
	vector<int> res;
	while (prv[best_i] != best_i) {
		res.push_back(best_i);
		best_i = prv[best_i];
	}
	res.push_back(best_i);
	reverse(res.begin(), res.end());
	for (int x : res) { cout << x + 1 << " "; }
}

Subtarea 4 (solución completa)

En resumen, si $x$ es el último número de una LBS:

$\texttt{dp1}$ (solo un valor posible de $x$ ) $\rightarrow$ transición $\mathcal{O}(M)$ , $\mathcal{O}(1)$ estados afectados
$\texttt{dp2}$ (hasta $M$ valores posibles de $x$ ) $\rightarrow$ transición $\mathcal{O}(1)$ , $\mathcal{O}(M)$ estados afectados

Notemos que, no importa cómo definamos el estado de DP, estas dos complejidades siempre se multiplicarán a $\mathcal{O}(M)$ . Por lo tanto, queremos hallar una restricción tal que ambas complejidades sean $\mathcal{O}(\sqrt{M})$ . Esto motiva usar una mezcla de $\texttt{dp1}$ y $\texttt{dp2}$ . Como $\texttt{dp1}2$ ya restringe bits, parece natural considerar aplicar $\texttt{dp1}$ sobre algunos bits de $x$ y $\texttt{dp2}$ sobre el resto.

Concretamente, sea $l_x = \texttt{l}(x, b)$ el número representado por los $b$ bits más a la izquierda de $x$ y $r_x = \texttt{r}(x, b)$ el número representado por los $\texttt{bit\\_count}(x) - b$ bits más a la derecha. En nuestro nuevo estado de DP $\texttt{dp}[i][j][k]$ , vamos a:

fijar $l_x = i$ (esta es la parte $\texttt{dp1}$ de nuestro nuevo estado)
restringir $r_x$ de modo que $r_x \in \texttt{trans}_k(j) \Rightarrow \texttt{bc}[r_x][j] = k$ (esta es la parte $\texttt{dp2}$ de nuestro nuevo estado)

¿Cuáles son ahora las complejidades temporales de transición y estados afectados?

Transición

Digamos que estamos procesando $a_i$ . Si tenemos $x$ tal que $x \in \texttt{trans}_{k_i}(a_i)$ , entonces $\texttt{bc}[x][a_i] = k_i$ . Al considerar los lados izquierdo y derecho de $x$ y $a_i$ por separado, podemos reescribir $\texttt{bc}[x][a_i]$ como $\texttt{bc}[l_x][l_{a_i}] + \texttt{bc}[r_x][r_{a_i}] = k_i$ .

Ejemplo: $x$ = 01010, $a_i$ = 01101, $b$ = 3


01010 & 01101 = 01000 -> 1

010   & 011   = 010   -> 1

   10 &    01 =    00 -> 0

$1 + 0 = \boxed1$ .

Como nuestro estado de DP $\texttt{dp}[l][r][k]$ fija $l_x = l$ , deberíamos reescribir esta ecuación para despejar $r_x$ : $\texttt{bc}[r_x][r_{a_i}] = k_i - \texttt{bc}[l_x][l_{a_i}]$ . Notemos que esta restricción coincide con nuestra restricción de $\texttt{dp}$ de $\texttt{bc}[r_x][j] = k$ , así que tenemos $r = r_{a_i}$ y $k = k_i - \texttt{bc}[l_x][l_{a_i}] = k_i - \texttt{bc}[x][l_{a_i}]$ . En cuanto a $l = l_x = \texttt{l}(x, b)$ , simplemente enumeramos las $2^b$ posibilidades; por lo tanto, $i \in [0, 2^b)$ .

En resumen, las transiciones hacia $a_i$ son todos los estados $\texttt{dp}[l][r_{a_i}][k_i - \texttt{bc}[l][l_{a_i}]]$ donde $l \in [0, 2^b)$ .

Como la única variable en el estado es $l$ , la complejidad de la transición es la cantidad de opciones para $l$ , que es $\boxed{2^b}$ .

Estados afectados

Ahora tenemos la longitud de la LBS más larga que termina en $a_i$ . ¿Qué estados $\texttt{dp}[l][r][k]$ afecta esto?

Empezando por lo obvio, $l = l_{a_i}$ . También tenemos la restricción de que $r_{a_i} \in \texttt{trans}_k(r) \Rightarrow k = \texttt{bc}[r_{a_i}][r]$ . Como $r_{a_i}$ es una constante, $k$ depende únicamente de $r$ .

En resumen, los estados afectados por $a_i$ son todos los estados $\texttt{dp}[l_{a_i}][r][\texttt{bc}[r_{a_i}][r]]$ .

$r$ tiene que tener la misma cantidad de bits que $r_{a_i} = \texttt{r}(a_i, b)$ , que tiene $\log_2{M} - b$ bits. Por lo tanto, $r$ tiene $2^{\log_2M - b} = \boxed{\frac{M}{2^b}}$ posibilidades.

Para resumirlo todo, la complejidad de la transición es $\mathcal{O}(2^b)$ y la complejidad de los estados afectados es $\mathcal{O}(\frac{M}{2^b})$ . Para minimizar la suma de estas complejidades, deberíamos igualarlas. Como $M = 2 ^{20}$ , hallamos que el valor óptimo de $b$ es $\boxed{10}$ .

Implementación

En la implementación de abajo:

$\texttt{l}(x)$ denota los 10 bits más a la izquierda de $x$
$\texttt{r}(x)$ denota los 10 bits más a la derecha de $x$

Complejidad temporal: $\mathcal{O}(N\sqrt{M})$

Código

C++


#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int N = 1e5;
const int B = 10;
int bc[1 << B][1 << B];  // bc[i][j] = bit_count(i & j)
struct State {
	int len;
	int end;
} dp[1 << B][1 << B][B + 1];
 
int main() {
	// preprocess:
	for (int i = 0; i < (1 << B); i++) {
		for (int j = 0; j < (1 << B); j++) { bc[i][j] = __builtin_popcount(i & j); }
	}
 
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	vector<int> k(n);
	for (int i = 0; i < n; i++) cin >> k[i];
	int ans = 1;
	// best_i: índice más óptimo en el que terminar
	int best_i = 0;
	vector<int> prv(n);               // prv[i]: mejor índice a incluir antes de i
	iota(prv.begin(), prv.end(), 0);  // prv[i] = i
 
	for (int i = 0; i < n; i++) {
		int l = a[i] >> B;        // l(a[i])
		int r = a[i] % (1 << B);  // r(a[i])
		int lbs = 1;              // longitud de la lbs más larga que termina en i
 
		// enumeramos todas las posibilidades para l(prev_num)
		for (int j = 0; j < (1 << B); j++) {
			// aquí, usamos el hecho de que
			// bc[x][y] = bc[l(x)][l(y)] + bc[r(x)][r(y)],
			// o bc[r(x)][r(y)] = bc[x][y] - bc[l(x)][l(y)]
 
			// valor requerido de bc[r(x)][r(y)]
			int needed = k[i] - bc[j][l];
			if (needed < 0 || needed > B) continue;
			if (dp[j][r][needed].len + 1 > lbs) {
				lbs = dp[j][r][needed].len + 1;
				prv[i] = dp[j][r][needed].end;
			}
		}
 
		if (lbs > ans) {
			ans = lbs;
			best_i = i;
		}
 
		// actualizamos todas las respuestas que a[i] afecta
		for (int j = 0; j < (1 << B); j++) {
			State &new_state = dp[l][j][bc[r][j]];
			if (lbs > new_state.len) {
				new_state.len = lbs;
				new_state.end = i;
			}
		}
	}
 
	cout << ans << endl;
 
	vector<int> res;
	while (prv[best_i] != best_i) {
		res.push_back(best_i);
		best_i = prv[best_i];
	}
	res.push_back(best_i);
 
	reverse(res.begin(), res.end());
	for (int x : res) { cout << x + 1 << " "; }
}

Longest Beautiful Subsequence

Explicación

Subtareas 1-2

Implementación

Subtarea 3

Implementación

Subtarea 3 (solución alternativa)

Implementación (dp2)

Subtarea 4 (solución completa)

Transición

Estados afectados

Implementación

Implementación (`dp2`)