Planteamiento del Problema

El problema de la expansión de doble secuencia conisste en dadas dos secuencias iniciales \(X\) e \(Y\), reemplazar cada elemento por múltiples copias idénticas para generar dos secuencias expandidas \(F\) y \(G\), ambas de longitud \(10^{100}\). La condición fundamental es que para cualquier par de índices \(i, j\), se cumpla que \((f_i - g_i)(f_j - g_j) > 0\).

Desde una perspectiva matemática, la condición \(xy > 0\) implica que \(x\) e \(y\) comparten el mismo signo. Por lo tanto, la restricción exige que la diferencia entre los elementos correspondientes de \(F\) y \(G\) mantenga un signo constante a lo largo de toda la secuencia. Esto se traduce en que o bien \(f_i > g_i\) para todo \(i\), o bien \(f_i < g_i\) para todo \(i\). Dado que ambos casos son simétricos, podemos asumir sin pérdida de generalidad que buscamos construir las secuencias de manera que \(f_i < g_i\) para todo \(i\).

Enfoque Inicial: Programación Dinámica con Bitset

Para una comprensión básica, podemos ignorar la magnitud de \(10^{100}\) y enfocarnos en la validez de las transiciones entre pares de elementos. Si consideramos añadir elementos de \(X\) e \(Y\) paso a paso, el problema se puede modelar mediante Programación Dinámica (DP) bidimensional.

Definimos un estado \(dp[i][j]\) que indica si el par \((x_i, y_j)\) puede formar parte de una expansión válida. La transición requiere que el elemento actual cumpla \(x_i < y_j\) y que exista al menos una transición válida desde los estados anteriores adyacentes:

\[ dp[i][j] = (x_i < y_j) \land (dp[i-1][j] \lor dp[i][j-1] \lor dp[i-1][j-1]) \] Para optimizar el espacio y el tiempo de ejecución, podemos utilizar la estructura std::bitset de C++, lo que reduce la complejidad temporal a \(O(\frac{nm}{w})\), donde \(w\) es el tamaño de la palabra del sistema.

#include <bitset>
#include <vector>

const int MAX_LEN = 2005;
std::bitset<MAX_LEN> dp[MAX_LEN];

bool solveBasicDP(const std::vector<int>& seqX, const std::vector<int>& seqY) {
    int lenX = seqX.size() - 1; // Asumiendo indexación base 1
    int lenY = seqY.size() - 1;
    
    for (int i = 0; i <= lenX; ++i) {
        dp[i].reset();
    }
    dp[0][0] = 1;
    
    for (int i = 1; i <= lenX; ++i) {
        for (int j = 1; j <= lenY; ++j) {
            if (seqX[i] < seqY[j]) {
                if (dp[i-1][j] || dp[i][j-1] || dp[i-1][j-1]) {
                    dp[i][j] = 1;
                }
            }
        }
    }
    return dp[lenX][lenY];
}

Optimización para Propiedades Especiales: Alcanzabilidad en Cuadrículas

Cuando se garantizan propiedades específicas, como que \(x_1 < y_1\), que el último elemento de \(X\) es su mínimo único y que el último elemento de \(Y\) es su máximo único, el enfoque de DP resulta ineficiente para tamaños grandes.

Podemos reformular el problema como la búsqueda de caminos en una cuadrícula 2D. Definimos una celda \((i, j)\) como "válida" (o transitable) si \(x_i < y_j\). Bajo las propiedades especiales, la última fila y la última columna de esta cuadrícula estarán completamente compuestas por celdas válidas. Esto crea un efecto de "embudo": si logramos alcanzar cualquier celda de la última fila o columna, el camino hacia el destino final \((n, m)\) está garantizado.

Para aprovechar esto, calculamos los índices de los valores mínimos y máximos en los prefijos de ambas secuencias. Si el mínimo del prefijo de \(X\) es menor que el mínimo del prefijo de \(Y\), podemos "saltar" directamente a esa coordenada. Esto permite realizar una Búsqueda en Profundidad (DFS) que reduce drásticamente el espacio de estados, logrando una complejidad de \(O(n + m)\).

struct Extrema {
    int minIdx, maxIdx;
};

Extrema combineExtrema(const std::vector<int>& seq, Extrema a, Extrema b) {
    Extrema res;
    res.minIdx = (seq[a.minIdx] < seq[b.minIdx]) ? a.minIdx : b.minIdx;
    res.maxIdx = (seq[a.maxIdx] > seq[b.maxIdx]) ? a.maxIdx : b.maxIdx;
    return res;
}

bool searchGridSpecial(const std::vector<Extrema>& prefX, const std::vector<Extrema>& prefY, 
                       int x, int y, const std::vector<int>& X, const std::vector<int>& Y) {
    if (x == 1 || y == 1) return true;
    
    if (X[prefX[x-1].minIdx] < Y[prefY[y-1].minIdx]) {
        return searchGridSpecial(prefX, prefY, prefX[x-1].minIdx, y, X, Y);
    }
    if (X[prefX[x-1].maxIdx] < Y[prefY[y-1].maxIdx]) {
        return searchGridSpecial(prefX, prefY, x, prefY[y-1].maxIdx, X, Y);
    }
    return false;
}

Solución General: División de Prefijos y Sufijos

En el caso general, sin las restricciones de mínimos y máximos únicos al final de las secuencias, la cuadrícula ya no garantiza que los bordes sean completamente transitables. Sin embargo, la estructura subyacente de "embudo" sigue existiendo en torno a los extremos globales.

La estrategia óptima consiste en dividir la cuadrícula en dos regiones utilizando los índices del mínimo global de \(X\) y el máximo global de \(Y\) como punto de cruce. 1. Fase Directa: Se evalúa la alcanzabilidad desde el inicio \((1, 1)\) hasta el punto de cruce utilizando los prefijos de las secuencias. 2. Fase Inversa: Se evalúa la alcanzabilidad desde el punto de cruce hasta el final \((n, m)\) utilizando los sufijos de las secuencias.

Si ambas fases reportan un camino válido, entonces existe una expansión válida para las secuencias completas. Este enfoque mantiene la complejidad lineal \(O(n + m)\) y cubre todos los casos posibles.

template <int direction>
bool bidirectionalSearch(const std::vector<Extrema>& extX, const std::vector<Extrema>& extY, 
                         int x, int y, int targetX, int targetY, 
                         const std::vector<int>& X, const std::vector<int>& Y) {
    if (x == targetX || y == targetY) return true;
    
    int nextStep = x + direction;
    int nextStepY = y + direction;
    
    if (X[extX[nextStep].minIdx] < Y[extY[nextStepY].minIdx]) {
        return bidirectionalSearch<direction>(extX, extY, extX[nextStep].minIdx, y, targetX, targetY, X, Y);
    }
    if (X[extX[nextStep].maxIdx] < Y[extY[nextStepY].maxIdx]) {
        return bidirectionalSearch<direction>(extX, extY, x, extY[nextStepY].maxIdx, targetX, targetY, X, Y);
    }
    return false;
}

bool solveFullExpansion(const std::vector<int>& X, const std::vector<int>& Y) {
    int n = X.size() - 1;
    int m = Y.size() - 1;
    
    std::vector<Extrema> prefX(n + 1), prefY(m + 1);
    std::vector<Extrema> sufX(n + 2), sufY(m + 2);
    
    for (int i = 1; i <= n; ++i) {
        prefX[i] = (i == 1) ? Extrema{1, 1} : combineExtrema(X, Extrema{i, i}, prefX[i-1]);
    }
    for (int j = 1; j <= m; ++j) {
        prefY[j] = (j == 1) ? Extrema{1, 1} : combineExtrema(Y, Extrema{j, j}, prefY[j-1]);
    }
    
    for (int i = n; i >= 1; --i) {
        sufX[i] = (i == n) ? Extrema{n, n} : combineExtrema(X, Extrema{i, i}, sufX[i+1]);
    }
    for (int j = m; j >= 1; --j) {
        sufY[j] = (j == m) ? Extrema{m, m} : combineExtrema(Y, Extrema{j, j}, sufY[j+1]);
    }
    
    if (X[prefX[n].minIdx] >= Y[prefY[m].minIdx] || X[prefX[n].maxIdx] >= Y[prefY[m].maxIdx]) {
        return false;
    }
    
    bool forwardPath = bidirectionalSearch<-1>(prefX, prefY, prefX[n].minIdx, prefY[m].maxIdx, 1, 1, X, Y);
    bool backwardPath = bidirectionalSearch<1>(sufX, sufY, prefX[n].minIdx, prefY[m].maxIdx, n, m, X, Y);
    
    return forwardPath && backwardPath;
}