El blog de Wewewew: Programación competitiva

Mostrando entradas con la etiqueta Programación competitiva. Mostrar todas las entradas

Puro AC, un nuevo blog

A pesar de mi poca experiencia en la solución de problemas de programación competitiva he decidido crear un blog para explicar algunos de los que vaya resolviendo de entre todas las plataformas que hay en línea tratando de explicar lo escencial del problema, detallar la solución, la complejidad de esta y el códdigo (o en su caso, pseudocódigo), siguendo la manera en que se escriben las editoriales de cada problema en Code Chef, como la entrada anterior a esta, mi editorial del problema Chef and Digits.

A esta iniciativa se sumará mi amigo y compañero de equipo Adrián Fernandez (@ferProgramming en Twitter), quien además propuso que en el blog también se explicaran además algunos algoritmos, estructuras y técnicas de programación que ambos estamos aprendiendo en el Club de Algoritmia, del que ya les había hablado antes.

En el blog he invertido algo de tiempo, dejándolo a punto con algunos extras y mejoras, como MathJax para que se vean mucho mejor las expresiones matemáticas, google-code-prettify para mejorar la apariencia del código escrito y el traductor de Google Translate, para traducir cualquier entrada a cualquier idioma disponible. Sin dejar de mencionar los plugins sociales para hacer que compartir una entrada en particular sea sencillo y a la vez descriptivo para quien lo lea.

Otro punto importante es que modifiqué la plantilla para que fuera adaptable a dispositivos móviles con un diseño responsivo. Además es posible imprimir la explicación ya que con el uso de @media queries pude crear una versión del blog que fuera amigable para imprimir (tamaño adecuado, colores en blanco y negro, etc...)

Sin más les dejo el enlace al blog, que hasta el momento cuenta con 3 entradas explicando soluciones a problemas, a la espera de que mi compañero publique algo más.

PuroAC

PD: Si te gustaría anexarte a la iniciativa, deja un mensaje en esta entrada o escríbeme por donde quieras. Entre más seamos, mejor.

¡Saludos!
@fferegrino :)

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

El Club de Algoritmia de la ESCOM y mi arrepentimiento

[Se supone que la primera regla del club es no hablar de él, pero meh]

A partir de este semestre por fin entré al Club de Algoritmia de la ESCOM, al cual desde mi llegada a la ESCOM tuve ganas de entrar pero por motivos laborales no podía asistir regularmente... tiempo después, cuando ya no tenía tanta carga en el trabajo, ese impedimento más bien se convirtió en un pretexto para mi desidia, sentía que quienes estaban ahí sabían más que yo y que podría no encajar con ellos, que nunca entendería nada de lo que estaban viendo, o que eso de la algoritmia nada más no era para mi.

Que equivocado estaba.

Hay pocas cosas de las que me arrepiento, y créanlo o no, el no haber entrado desde antes a participar en él es una de ellas, todo por mi desidia. Hasta ahora que llevo ya un poco más de un mes asistiendo a las sesiones me doy cuenta de lo equivocado que estaba, he aprendido bastante, los compañeros son de lo mejor y cada vez me motivo más. De vez en vez me haré un tiempo para escribir sobre lo que he visto y me ha fascinado.

Definitivamente enfrentarte a estos tipos de problemas, te abre la mente, te enseña a pensar de maneras distintas para resolver no solo retos de programación, si no de otras áreas. No solo es complicarse la vida o resolver problemas solo por hacerlo como muchos erróneamente dicen.

Seguramente hay personas que piensan lo que yo pensaba pero hay que atreverse, no es tan difícil hacerlo. No te esperes "tanto" (porque nunca es tarde, pero si es posible hay que hacerlo cuanto antes). Si tu, al igual que yo y muchas personas más, tienes interés en la programación competitiva no dudes en acercarte ya sea a este o a uno más cercano a ti. Acá están los capítulos estudiantiles de la ACM en México para que sepas a quién acercarte para ver qué es lo que ofrecen.

¡Saludos!
@fferegrino :)