Planteamiento del Sistema

Se requiere resolver un problema de optimización sobre una secuencia de N enteros positivos, donde 2 ≤ N ≤ 262144. Cada elemento posee un valor inicial acotado en el intervalo [1, 40]. La mecánica permite seleccionar dos valores contiguos idénticos y reemplazarlos por un único elemento cuyo valor es el original incrementado en una unidad. El objetivo algorítmico es determinar el entero de mayor magnitud que puede existir en la secuencia tras ejecutar todas las fusiones válidas de forma estratégica.

Especificación de Interfaz de Datos

Entrada: La primera línea indica N. Las siguientes N líneas contienen los valores que componen la configuración inicial.

Salida: Un único número entero que corresponde al valor máximo alcanzable.

Caso de Prueba

Entrada:
4
1
1
1
2

Salida:
3

La secuencia óptima combina el segundo y tercer 1 para obtener 2, transformando el arreglo en 1 2 2. Posteriormente, los dos 2 adyacetnes se fusionan en un 3. Fusionar los primeros dos 1 inicialmente impide alcanzar este techo.

Diseño Algorítmico

La magnitud de N invalida los esquemas clásicos de programación dinámica por intervalos, cuya complejidad cuadrática excede los límites de ejecución. La estrategia viable redefine los estados para operar en O(N · V_max).

Se establece una tabla limite_derecho[valor][indice_inicio] que registra la posición final más alejada a la que puede extenderse la construcción del número valor, partiendo exclusivamente desde indice_inicio.

Estado base: Para cada posición k con valor v en la entrada, limite_derecho[v][k] = k.

Transición: Para sintetizar un valor v comenzando en j, se requieren dos segmentos consecutivos de valor v-1. Si el primer segmento cubre [j, limite_derecho[v-1][j]], el segundo debe iniciarse en limite_derecho[v-1][j] + 1. La relación se expresa como:

limite_derecho[v][j] = limite_derecho[v-1][ limite_derecho[v-1][j] + 1 ]

Si la referencia resultante es positiva, valida la fusión. Al iterar v ascendente y j sobre la secuencia, se actualiza el registro del valor máximo generado exitosamente. Dado que el valor inicial máximo es 40 y el tamaño permite como mucho 18 duplicaciones, el techo teórico se sitúa cerca de 60.

Implementación en C++

#include <iostream>
#include <vector>
#include <algorithm>

int ejecutar_optimizacion() {
    int cantidad_elementos;
    if (!(std::cin >> cantidad_elementos)) return 0;

    std::vector<int> secuencia(cantidad_elementos + 1);
    int valor_piso = 0;

    for (int pos = 1; pos <= cantidad_elementos; ++pos) {
        std::cin >> secuencia[pos];
        valor_piso = std::max(valor_piso, secuencia[pos]);
    }

    constexpr int COTA_SUPERIOR = 65;
    std::vector<std::vector<int>> alcance_dcho(COTA_SUPERIOR, 
                               std::vector<int>(cantidad_elementos + 1, 0));

    for (int k = 1; k <= cantidad_elementos; ++k) {
        alcance_dcho[secuencia[k]][k] = k;
    }

    int resultado_optimo = valor_piso;

    for (int val = valor_piso + 1; val < COTA_SUPERIOR; ++val) {
        bool existe_progreso = false;
        for (int origen = 1; origen <= cantidad_elementos; ++origen) {
            int fin_primer_segmento = alcance_dcho[val - 1][origen];

            if (fin_primer_segmento == 0 || fin_primer_segmento >= cantidad_elementos) {
                continue;
            }

            int inicio_segundo = fin_primer_segmento + 1;
            int alcance_final = alcance_dcho[val - 1][inicio_segundo];

            if (alcance_final > 0) {
                alcance_dcho[val][origen] = alcance_final;
                resultado_optimo = val;
                existe_progreso = true;
            }
        }
        if (!existe_progreso) break;
    }

    std::cout << resultado_optimo << "\n";
    return 0;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return ejecutar_optimizacion();
}