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 :)

Leyendo de la entrada estándar con scanf y fgets

Hace tiempo, les contaba que me inicié en la programación competitiva, en la cual, la mayoría de problemas nos piden leer información de la entrada estándar o stdin seguramente me lo van a creer... yo no sabía cómo hacerlo de una manera "correcta" (._. ), en especial cuando de cadenas se trataba. En este post trataré de explicar cómo es que lo hago (y he aprendido que lo hacen) en C o C++.

La función scanf

Esta función mágica llega a nosotros gracias a la librería <stdio.h> en C o <cstdio> en C++, resulta la manera básica de recuperar valores. Nos sirve para todo tipo de entradas y si no tienes algo muy complicado de leer, esta es tu mejor opción, recuerda que esta función trata de leer el tipo de dato que le especifiques hasta que encuentra un salto de línea o un espacio en blanco. El uso de esta función depende de los especificadores de formato para recuperar los valores que deseas.

Por ejemplo, supongamos que tenemos la siguiente entrada
10 3161565164181
aab baa aba
y este código para leerlo
int a;
long long int b;
char cadena[15];
scanf("%d %lld", &a, &b); 
scanf("%s", cadena); // 'cadena' es ya una referencia a memoria
Una vez que se ejecute, en a tendremos 10, en b tendremos 3161565164181 y cadena será "aab" (¡porque solo lee hasta el espacio en blanco!).

La función fgets

Pero, qué pasa si la entrada es un poco más complicada, como la del problema Wetlands of Florida en la que vienen secuencias de caracteres seguidas inmediatamente por un par de números enteros:
// ...
LLLLLLLLL
3 2
// ...
Para ello se ocupa la función fgets (que es parecida a gets, solo que más segura), en combinación con sscanf que funciona de manera similar a scanf solo que esta "lee" de una secuencia de caracteres y no de stdin. En cuanto a fgets, sus parámetros son: la dirección de memoria, la cantidad de caracteres que esperamos leer como máximo, y el flujo del que los vamos a extraer, de tal manera que tenemos algo así: 
int i, j;
char entrada[10];
fgets(entrada,10,stdin);
// Procesamos 'entrada', que contiene la siguiente secuencia de caracteres: 
// 'L','W','W','W', 'L', 'L', 'L', 'L', 'W' y '\n' <= ¡Sí! el salto de línea
// Recuperamos los enteros:
fgets(entrada,10,stdin);
sscanf(entrada,"%d %d",&i,&j);
Ya para finalizar es necesario remarcar esto: fgets recupera hasta que encuentra el salto de línea. Repito: fgets recupera hasta que encuentra el salto de línea por lo que es necesario eliminarlo "a manita" con '\0' si es que no es lo que deseamos de él. 
Espero que les sirva como a mi me ha servido, ya que hay que recordar que una parte importante de resolver los problemas es saber interpretar de manera adecuada la entrada que nos dan, así como saber introducirla dentro de nuestra probable solución a este.


¡Saludos!
@fferegrino :)
Newer Posts
Home
Older Posts