Chef and Digits (ADIGIT) - Editorial

Link al problema: ADIGIT (Practice)
Link al editorial en CodeChef: ADIGIT - Editorial

Dificultad: Fácil

Problema:

Dados $N$ ($N ≤ 10^5$) dígitos y $M$ ($M ≤ 10^5$) consultas que consisten en un entero $x$ ($1 ≤ x ≤ N$), que llamaremos step (paso), imprimir el resultado de $B1 - B2$, donde:

$B1$ := Sumatoria de todos los $b = a_x - a_y$ tal que $x > y$ y $b > 0$
$B2$ := Sumatoria de todos los $b = a_x - a_y$ tal que $x > y$ y $b < 0$

Solución:
Veamos el siguiente caso, con entrada a = 0123152397

Calculando los valores para todos los pasos tenemos lo siguiente:

En la tabla anterior he marcado dos casillas, para observar a detalle lo que sucede:

Para el paso 4 tenemos: $B1 = (3 -0) + (3 - 1) + (3 - 2) = 6$ y $B2 = 0$ lo cual nos da el valor de $6$
Para el paso 8 tenemos: $B1 = (3 - 0) + (3 - 1)+ (3 - 2) + (3 - 1) + (3 - 2) = 9$ y $B2 = (3 - 5) = - 2$, por lo tanto tenemos $B1 - B2 = 11$

Observando las ecuaciones anteriores, podemos notar que el paso 11 se compone del paso 3 en las sumas $(3 - 0) + (3 - 1)+ (3 - 2)$ más otras 3 sumas, así que ¿qué pasaría si los almacenamos para no volver a calcularlo todo? Basándonos en eso, almacenamos los resultados en otro arrelgo.

Ahora, ¿cómo es que sabemos que tenemos un valor ya calculado?, esto es sencillo de encontrar y ocurre cuando los números $a_x$ y $a_y$ son iguales. Si los calculamos de manera secuencial, es decir de 1 hasta N, estaremos garantizando que para cada paso los pasos previos ya estarían precalculados, como solo hay 10 dígitos distintos, en el peor de los casos terminaremos sumando 10 veces. Al terminar el precálculo, para cada consulta que nos hagan la respuesta será obtenida en tiempo constante

Complejidad: $O(10 * N) + O(M)$

Código (C++):
Definiremos un arreglo A, donde A[i] es es valor de paso i-ésimo del problema y s, un arreglo de char, donde s[j] es la posición del dígito j-esimo.

void precalc(){
 int t = 0;
 for(int step = 0; step < n; step++){
  int ans = 0;
  for(int i = step-1; i >= 0; i--){
   t = (s[step] - '0') - (s[i] - '0');
   if(t == 0){
    ans += A[i];
    A[step] = ans;
    break;
   }
   ans += abs(t);
   A[step] = ans;
  }
 }
}

Haciendo que para responder a las consultas q, solo será necesario imprimir el valor almacenado en A[q-1]

int main(){
 scanf("%d%d",&n,&m);
 scanf("%s",s);
 precalc();
 while(m--){
  scanf("%d",&q);
  printf("%d\n",A[q-1]);
 }
 return 0;
}

¡Saludos!
@fferegrino :)

El blog de Feregrino

a * (((a - b) >> 31) & 1) + b * (!(((a - b) >> 31) & 1))

Chef and Digits (ADIGIT) - Editorial

2 comments: