Link al editorial en CodeChef: ADIGIT - Editorial
Dificultad: Fácil
Problema:
Dados $N$ ($N ≤ 10^5$) dígitos y $M$ ($N ≤ 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
- 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 caso 3 más otras 3 sumas, en las sumas $(3 - 0) + (3 - 1)+ (3 - 2),$ 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.
Complejidad: $O(10 * N)$
Complejidad: $O(10 * N)$
Código (C++):
Definiremos un arreglo A, donde A[i] es es valor de paso i-ésimo del problema y s de char, donde s[j] es la posición del dígito j.
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 :)
No hay comentarios:
Publicar un comentario