El problema P9717 de la EC Final 2022 plantea una transformación en una cadena binaria circular donde cada ocurrenica simultánea del patrón 01 se convierte en 10. El objetivo es determinar el número total de estados únicos alcanzables a partir de una configuración inicial dada.
Modelo de Partículas y Estados
La transformación 01 → 10 puede interpretarse físicamente como el movimiento de partículas 1 hacia la izquierda y partículas 0 hacia la derecha. Dado que la cadena es circular, este proceso eventualmente alcanza un estado de equilibrio donde todos los 1 están agrupados, formando un bloque continuo. Este es el estado de máxima compresión.
El número total de estados alcanzables se define por la suma de dos componentes críticos:
- Longitud de la cadena de evolución ($T_{max}$): Representa cuántos pasos de "dispersión" (la operación inversa
10 → 01) se pueden realizar desde el estado más estable antes de alcanzar la configuración más extendida posible. - Periodo del estado canónico ($P$): Es el periodo mínimo del estado que representa la configuración más dispersa bajo rotaciones cíclicas.
La fórmula general es: Total = T_{max} + P.
Optimización por Simetría
Para simplificar el análisis, podemos asumir que estamos rastreando el movimiento del carácter menos frecuente. Si hay más ceros que unos, invertimos los bits (0 por 1 y viceversa) y revertimos la cadena. Esto permite que el algoritmo siempre trate a los 1 como las partículas móviles sobre un fondo de 0, sin perder generalidad.
// Normalización de la cadena según la densidad de bits
int count_zeros = 0;
for (char c : s) if (c == '0') count_zeros++;
if (count_zeros * 2 > n) {
for (int i = 0; i < n; i++) {
s[i] = (s[i] == '0' ? '1' : '0');
}
reverse(s.begin(), s.end());
}
Cálculo de la Evolución Máxima (T_max)
Para hallar $T_{max}$, utilizamos un enfoque de sumas prefijas transformando 1 en +1 y 0 en -1. Al procesar esta secuencia en una estructura de datos lineal (duplicando la cadena para simular el anillo), podemos identificar los intervalos de mayor "tensión" o distancia entre partículas utilizando una pila monótona.
// Implementación de búsqueda de T_max mediante sumas prefijas y pila monótona
vector<int> prefix_sum(2 * n);
prefix_sum[0] = (s[0] == '1' ? 1 : -1);
for (int i = 1; i < 2 * n; i++) {
prefix_sum[i] = prefix_sum[i - 1] + (s[i % n] == '1' ? 1 : -1);
}
vector<int> stack_indices;
long long max_steps = 0;
for (int i = 2 * n - 1; i >= 0; i--) {
while (!stack_indices.empty() && prefix_sum[i] >= prefix_sum[stack_indices.back()]) {
stack_indices.pop_back();
}
stack_indices.push_back(i);
if (i < n && s[(i + 1) % n] == '1') {
if (stack_indices.size() > 1) {
int target = stack_indices[stack_indices.size() - 2];
max_steps = max(max_steps, (long long)(target - i - 1) / 2);
}
}
}
Cálculo del Periodo mediante KMP
Una vez determinada la evolución máxima, construimos una cadena representativa del estado más disperso. El periodo de esta cadena se calcula eficientemente utilizando el vector de fallos (función next) del algoritmo KMP. El periodo mínimo de una cadena de longitud $N$ viene dado por $N - \pi[N-1]$, donde $\pi$ es el último valor del vector de fallos, siempre que este divida a $N$. En este problema, el "periodo" se refiere a la cantidad de rotaciones únicas.
// Construcción de la cadena canónica y cálculo de su periodo
string canonical(n, '0');
// ... lógica de posicionamiento de partículas basada en max_steps ...
auto compute_period = [&](const string& t) {
int m = t.length();
vector<int> pi(m);
for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && t[i] != t[j]) j = pi[j - 1];
if (t[i] == t[j]) j++;
pi[i] = j;
}
// Para cadenas circulares, el periodo mínimo es:
int smallest_unit = m - pi[m - 1];
return (m % smallest_unit == 0) ? smallest_unit : m;
};
long long P = compute_period(canonical);
long long total_ans = (max_steps + P) % 998244353;
Complejidad y Eficiencia
El algoritmo opera principalmente en tiempo lineal $O(N)$. La construcción de las sumas prefijas, el recorrido con la pila monótona y el pre-procesamiento del KMP son todos procesos que escalan proporcionalmente al tamaño de la cadena de entrada. Esto es esencial dado que el límite de tiempo en competencias internacionales como EC Final suele ser estricto para longitudes de cadena elevadas.