El blog de Feregrino

En fin, la descripciones de las aplicaciones son:

Ubicadoen el servidor (este proyecto es una librería de clases), el código facilita la conexión a la base de datos alojada en azure, conexión hecha con la ayuda del Entity Framework V 6.1.1

Reference.WebRole
Este proyecto aloja el servicio web al cual se realizan las consultas, es decir, se conecta con Reference.Data.

Reference.Cloud
Es solo un proyecto que envuelve el WebRole y permite que sea publicado como un servicio de la nube de Azure.

Reference.Apps.Shared
Proyecto compartido que contiene todos los rescursos y clases que tienen en común las aplicaciones para Windows y Windows Phone, recursos como estilos, ViewModels y la conexión al servicio web.

Reference.Apps.Windows
El proyecto de la aplicación para Windows 8.1 que contiene código específico de para tablet/pc. Hace uso del paquete de Nuget MVVM Light (solo liberías).

Reference.Apps.WindowsPhone
El proyecto de la aplicación para Windows Phone 8.1 que contiene código específico de para el teléfono. Hace uso del paquete de Nuget MVVM Light (solo liberías).

Reference.Tools.CodeTransformer
Una herramient simple para transofrmar el código para que sea almacenado en la base de datos a algo que el servicio web y las aplicaciones puedan entender.

Otra cosa a resaltar es que todo el código está disponible en CodePlex para su descarga, y las aplicaciones están también en la tienda. Por el momento la app carece de contendio, cosa que espero ir ampliando a la par de mi aprendizaje en el Club de Algoritmia de ESCOM:

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.

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:

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

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;
  }
 }
}

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