Hola, en el Educational Round 55 de CodeForces apareció el siguiente problema que me pareció lindo.
Enunciado
Se tiene un arreglo a de largo n y un valor distinguido c. Se puede realizar una operación del siguiente tipo. Elegir un subarreglo [l,r] (1 \leq l \leq r \leq n), y un entero k (sin restricciones, puede ser positivo, negativo o cero). Una vez hecha esta elección, para cada l \leq i \leq r se cambia a_i := a_i+k.
¿Cuál es la máxima cantidad de índices que pueden quedar con valor c partiendo del arreglo original y realizando una operación descrita?
Entrada
La primera línea contiene dos enteros n y c \hspace{3pt}(1 \leq n \leq 5 \cdot 10^5, 1 \leq c \leq 5 \cdot 10^5), que son el largo del arreglo y el valor distinguido respectivamente.
La segunda línea contiene n enteros a_1,a_2, \dots, a_n \hspace{3pt}(1 \leq a_i \leq 5 \cdot 10^5), los enteros del arreglo a.
Salida
Se debe imprimir un entero con la máxima cantidad posible de elementos con valor c que se puede obtener luego de realizar una operación en el arreglo.
Entrada 1:
6 9
9 9 9 9 9 9Salida 1:
6
Entrada 2:
3 2
6 2 6Salida 2:
2
En el primer ejemplo se puede elegir cualquier subarreglo [l,r] y tomar k = 0, el arreglo no cambia y se obtiene la mayor cantidad de 9's posibles.
En el segundo ejemplo podemos elegir el subarreglo [1,3] y tomar k = -4, el arreglo resultante será [2,-2,2] que tiene la mayor cantidad de apariciones posibles del número c = 2.