Increasing Frequency

Análisis oficial (C++) 

Explicación

Definamos $\texttt{freq}(l, r, x)$ como el número de veces que el valor $x$ aparece en el rango $[l, r]$.

Nuestra respuesta, como mínimo, será $\texttt{freq}(1, n, c)$, si no hacemos una operación. Así, nuestro objetivo es hallar un subarreglo que maximice las ocurrencias adicionales de $c$ que podemos agregar a nuestra respuesta.

Si queremos transformar todas las ocurrencias de un valor $v$ en $c$, entonces la contribución a nuestra respuesta será

porque cualquier valor de $c$ se verá alterado por la operación necesaria para transformar $v$ en $c$. Ahora, nuestro objetivo es hallar la tupla óptima $(l, r, v)$ y sumarla a nuestra respuesta mínima.

Consideremos todos los elementos $v$, donde transformamos $v$ en $c$, e intentemos hallar así nuestro mejor subarreglo. Nótese que en un subarreglo óptimo $[l, r]$, solo consideramos subarreglos donde $a[l] = a[r] = v$, lo que hace que, entre todos los valores de $v$, haya solo $\mathcal{O}(n)$ extremos a considerar.

Como queremos hallar la respuesta máxima entre todos los subarreglos, esto sugiere transformar nuestro problema en algo similar al clásico problema de suma máxima de subarreglo, que se cubrió en el módulo de sumas de prefijos.

Definamos $l$ como el arreglo ordenado de todas las ocurrencias de $v$ en nuestro arreglo $a$, y sea $b$ el arreglo sobre el que ejecutamos nuestro algoritmo de subarreglo máximo, donde $l[i]$ se corresponde directamente con $b[i]$. Inicialmente, cada elemento $b[i]$ se pone en $1$. Ahora, para manejar las ocurrencias de $c$ en un posible subarreglo, comprimimos los intervalos entre cada valor de $l$. Más específicamente, hacemos la siguiente operación para todo $i$ válido:

Con esta transformación, podemos aplicar el algoritmo de subarreglo máximo que elijamos para obtener nuestra respuesta.

Implementar de forma directa el enfoque de arriba alcanza para pasar todos los casos de prueba, y es la implementación que aparece en el editorial oficial. La implementación de abajo usa la misma idea que el enfoque descrito arriba, pero está modificada para ser considerablemente más concisa.

Recordemos el algoritmo de Kadane para la suma máxima de subarreglo. La idea es barrer de izquierda a derecha y, para cada índice, hallar el mejor subarreglo que termina en dicho índice. La estrategia voraz es la siguiente:

• Si estamos en el índice $i$, y el subarreglo máximo anterior que termina en $i-1$ es menor que cero, lo cortamos y empezamos un nuevo arreglo con el único elemento en $i$
• En caso contrario, extendemos el subarreglo desde $i-1$ anexando el elemento actual

Nuestro algoritmo de DP funciona de forma similar. Consideremos barrer de izquierda a derecha, y tener $\texttt{dp}[v]$ igual al número de ocurrencias de $v$ en nuestro prefijo actual, mientras también llevamos un contador de las veces que encontramos $c$. Entonces, para este prefijo, la contribución de este prefijo sería $\texttt{dp}[v] - \texttt{freq}(1, i, c)$, si estamos actualmente en el índice $i$.

Sin embargo, no siempre es óptimo tomar el prefijo entero al transformar ciertas ocurrencias de $v$ en $c$. Más específicamente, si $\texttt{dp}[v] < \texttt{freq}(1, i, c)$, entonces deberíamos cortar este prefijo actual y empezar un nuevo subarreglo. Así, nuestra transición de estado de DP es

Con esto, podemos calcular la mejor contribución como el valor máximo de $\texttt{dp}[a[i]] - \texttt{freq}(1, i, c)$, mientras barreemos de izquierda a derecha.

Implementación

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

#include <bits/stdc++.h>
 
 
constexpr int MAX = 5e5;
int dp[MAX + 1];
 
int main() {
	int n, c;
	std::cin >> n >> c;
 
	int num_c = 0;
	int best_sub = 0;
	for (int i = 0; i < n; i++) {
		int a;
		std::cin >> a;
 
		if (a == c) {
			// we have one more total c element
			// note that we don't care about dp[c]
			num_c++;
		} else {
			// here, we care about dp[a]
			// like Kadane's, we 'reset' here or we add on
			dp[a] = std::max(num_c, dp[a]) + 1;
		}
 
		// the contribution a subarray operation adds is the max # of
		// elements with the same value, minus the number of c values
		best_sub = std::max(best_sub, dp[a] - num_c);
	}
 
	std::cout << num_c + best_sub << '\n';
}