Link del problema: 1010 - ACM contest and Blackout

Dificultad: Medio

Problema: El problema se resume a dar los dos árboles de expansión mínima o los árboles con el menor peso dada una entrada de N $ 3<= N <= 100 $ nodos (escuelas) y M aristas (conexiones).

Ejemplo: Para cada M línea sea darán 3 números Ai, Bi y Ci. Donde Ai y Bi serán las escuelas conectadas y Ci su precio para que estén conectadas.

4 5
4 1 4
4 2 7
1 3 1
1 2 5
3 2 6
Aquí el grafo original:

Las respuestas serían 10 y 11 ya que los arboles menos costosos se pueden formar así:



Ahora, ¿cómo conseguir esto?
Solución (algoritmo de Kruskal): 
Para los que no conozcan el algoritmo o no sepa como trabaja acá hay una buena explicación e incluso una implementación descargable muy entendible pues el mismo algoritmo usa la estructura de datos Union-Find.
Si bien obtener el MST (Minimum Spanning Tree) es fácil con Kruskal ¿como haríamos para asegurar el segundo árbol más barato? La idea básicamente es guardar las aristas con las que formamos nuestro primer MST y buscar formar árboles exceptuando cada una de las aristas una por una, es decir, quitamos una de las aristas y formamos un nuevo árbol, después la siguiente arista que guardamos y formamos otro árbol, siempre quedándonos con la MENOR.
Con una de las dificultades que me enfrenté es que al hacer kruskal omitiendo arista por arista no me aseguraba que se formara un árbol es ahí donde debemos comprobar que se forme un árbol efectivamente. ¿Cómo? en nuestro Union - Find podemos saberlo checando que solo haya una raíz, pues si solo hay una quiere decir que solo hay una componente conexa (que todos los nodos están conectados y forman el árbol).
Al hacer esto omitir arista por arista, checar que solo haya una componente conexa y quedarnos con la menor, nos dará el siguiente MST o árbol menos costoso.

En el siguiente fragmento de código lo que hago es conseguir omitiendo arista por arista tener el siguiente árbol de expansión mínima, checar que solo haya una componente conexa en el arreglo de padres y quedarme con la mínima:



Y bueno eso fue todo por esta ocasión, ya saben si gustan sugerir algún tema pueden hacerlo abiertamente y espero les haya gustado comenten si hay dudas y escriban. 
Adrián Fernández @ferprogramming

Dadas $N$, ($1 ≤ N ≤ 10000$) ubicaciones enteras $A_i$ ($0 ≤ A_i ≤ 10^9$) y un entero $K$ ($0 ≤ K ≤ 10^9$) para cada rana, determinar si la rana $A$ ubicada en la posición $i$ puede comunicarse con la rana $B$ en posición $j$. Las ranas en posicion $i$ y $j$ se pueden comunicar siempre que entre ellas la distancia sea  $ ≤ K$ o entre ellas existan otras ranas que cumplan con la anterior condición. Las ranas son muy amigas y entre ellas se pasan el mensaje.

Nos damos cuenta que cuando a una rana le llegue un mensaje esta se lo podría pasar a cualquiera otra que estuviera a menos de una distancia $K$ de su posición, por tanto partiendo de ese punto formaremos grupos de ranas que estarán comunicadas entre si, para lo cual usaremos union-find.

De entrada lo que debemos de hacer es ordenar las posiciones de cada rana, manteniendo el índice original en el cual estaban, posteriormente recorremos nuestro arreglo ya ordenado para unir a las ranas que se pueden comunicar.

Complejidad: $O(N log N)$ debido a la ordenación de las ubicaciones.

Para facilitarnos las cosas emplearemos un arreglo la clase pair, otro arreglo de enteros llamado roots (necesario para la estructura union-find y las funciones join y root habituales) y unas definiciones para darle un poco de claridad al código:

#define place second
#define distance first
typedef std::pair<int,int> frog;

for(int i = 1; i <= N; i++){
 roots[i] = i;
 scanf("%d", &frogs[i].distance);
 frogs[i].place = i;
}
std::sort(frogs+1, frogs+N+1);
for(int i = 1; i < N; i++){
 if(frogs[i + 1].distance - frogs[i].distance <= K){
  join(frogs[i + 1].place, frogs[i].place);
 }
}

Una vez terminada las uniones basta con leer las consultas y determinar si la rana $A$ se puede comunicar con la rana $B$:

root(a) == root(b) ? printf("Yes\n") : printf("No\n");

Dada una cadena $E$, ($|E| ≤ 500$) compuesta por los símbolos #, + y - (La cadena no contendrá más de 7 # juntos) y una cadena de dígitos S, ($|S| =$ número de '#' en $E$). Acomodar cada uno de lo dígitos en $S$ en cada posición # en $E$ para que la operación que representa nos de como resultado el valor máximo.

Para mejor claridad veamos el caso de prueba:

##+##
1234

La mejor forma de acomodarlos para obtener el máximo es $32+41$ lo que nos da $73$ como resultado.

Para encontrar el valor máximo de una suma tenemos que maximizar el valor de sus operandos mientras que para las restas tenemos que minimizarlo. Una forma de hacerlo es separar la cadena $E$ en grupos de #, de tal manera que llevemos la cuenta de qué tan grande es el número (cantidad de dígitos) y podamos identificar entre los que son positivos o negativos. Sabiendo esto repartiremos los números en $E$ haciendo que los de mayor valor queden en los grupos positivos con mayor cantidad de dígitos y los de menor valor queden en los negativos con mayor cantidad de dígitos.

Los dígitos se deben repartir en un orden peculiar para que el resultado nos de la solución deseada, y es que primero se deben repartir la cantidad más grande (en el caso del ejemplo anterior son las decenas, números 4 y 3) y luego las unidades. Una vez que se hizo esto se deben repartir a los grupos negativos los dígitos con menor valor siguiendo lo anteriormente dicho.

Después bastara con sumar/restar los valores resultantes de la operación anterior para obtener el resultado.

Complejidad: $O(N log N)$ debido a la ordenación de los dígitos en $E$.

struct Group{
 int o; // Original index
 int v; // Value of the group  
 int d; // Digit amount
 int s; // Positive or negative: 1 or -1
 int value(){ // Return the final value
  return s * v;
 }
};

Definimos además un arreglo nums de tamaño k donde se almacenarán los dígitos de la cadena $E$ ordenados de manera descendente, un arreglo G de tamaño p de la estructura Grupo donde almacenaremos nuestros grupos ordenado del número positivo con mayor cantidad de dígitos al número negativo con menor cantidad de dígitos.

En el siguiente fragmento de código se reparten los dígitos a los grupos positivos:

  int n = -1;
  int neg;
  int ii = 0;
  int ix = 0;
  n = G[0].d;
  while(n > 0 && G[0].s > 0){
   for(ix = 0; G[ix].d == n && ix <= p; ix++){
    if(G[ix].s < 0) { break; }
    G[ix].d--;
    G[ix].v = (nums[ii] * pow(10,n-1)) + G[ix].v;
    ii++;
   }
   n = G[0].d;
  }

   reverse(nums+ii, nums+k);
   neg = ix;
   n = G[ix].d;
   while(n){
    for(; G[ix].d == n && ix <= p; ix++){
     G[ix].d--;
     G[ix].v = (nums[ii] * pow(10,n-1)) + G[ix].v;
     ii++;
    }
    n = G[neg].d;
   }

  int res = 0;
  for(i = 0; i <= p; i++){
   res += G[i].value();
  }
  printf("%d\n", res);

Link del problema: 1079 - Sums In a Triangle I

Dificultad: Fácil

Problema: Dado un número $N$ donde $1<=N<=100$ se tienen $N$ niveles en un triangulo, así el primer nivel tiene 1 número, el segundo nivel tiene 2 números, el tercero 3, etc. El programa debe encontrar la máxima suma desde el primer nivel hasta el último pudiendo tomar una ruta tal que solo se acceda al número de abajo o al de abajo y una posición a la derecha...

Ejemplo:
Con $N = 3 $
Tenemos el siguiente triángulo:
1
1 2
2 3 1

La respuesta es 6 ya que primero solo tomamos el primer elemento pues no hay más opción ya que es el único elemento en la fila en la siguiente podemos tomar el 1 o 2

1
1 2  //La mejor opción aquí es tomar el de abajo y a la derecha que es  el mayor

2 3 1

Hasta este punto llevamos la "mejor" ruta posible habiendo tomado los elementos de mayor prioridad entonces en la siguiente iteración solo podemos tomar dos elementos:

1
1 2  

2 3 1 //La mejor opción aquí es tomar el de abajo que es  el mayor
Y así por fin llegar a nuestro cometido que era tomar la ruta tal que la suma sea la mayor...

Solución: (DP)

Este problema se resuelve con Programación Dinámica (DP) ya que tenemos que tomar una decisión en cada nivel (la mejor) y así ir tomar la mejor ruta que podamos, entonces como se mencionó en nuestra otra publicación de DP tenemos que establecer los ESTADOS de la DP y las DECISIONES para lo cual nuestros estados tendremos:

 int dp(int i,int j){
 }

if(i==n)
   return 0;

Vemos que si nuestro apuntador llega a la última columna tendremos que detener la DP.

Por último necesitamos nuestras decisiones, aquí solo basta con devolver el MÁXIMO entre tomar el de abajo dp(i+1,j) y tomar el de abajo y una posición a la derecha dp(i+1,j+1) y sumar en cada decisión el elemento que corresponde a esa posición de la siguiente manera:

return max(dp(i+1,j)+piramide[i+1][j],dp(i+1,j+1)+piramide[i+1][j+1]);

Y así se resolvería el problema, cabe decir que mis números los guarde en un arreglo llamado pirámide para así poder usarlos después y sumarlos. Ahora un punto IMPORTANTE al final a la respuesta que devuelva esta función tenemos que sumarle el primer elemento del triángulo ya que aquí NO estamos considerándolo.

res = dp(0,0);
printf("%d\n",res + piramide[0][0]);

Y bueno eso fue todo por esta ocasión, ya saben si gustan sugerir algún tema pueden hacerlo abiertamente y espero les haya gustado comenten si hay dudas y escriban.
Adrián Fernández @ferprogramming

Un punto lattice $(x, y)$ en el primer cuadrante ($x, y0$ son números enteros mayores o iguales a 0), que no sea el origen, es visible desde el origen si la línea de $(0, 0)$ a $(x, y)$ no pasa a través de cualquier otro punto lattice. Escriba un programa que, dado un valor para el tamaño $N$ ($1 ≤ N ≤ 1000$), calcula el número de puntos visibles $(x, y)$ con $0 <= x, y <= N$.

Para resolver este problema trazaremos las rectas (imaginariamente) desde todos los puntos que pueden existir en la cuadrícula hacia el origen. Dichas rectas, además de pasar siempre por el origen, la coordenada $(x_2 = 0, y_2 = 0)$, también deberán pasar por el punto $(x_1 = x, y_2 = y)$ donde $0 ≤ x, y ≤ N$. Recordemos la ecuación de la recta: $(x_2 - x_1) / (y_2 - y_1) + b$, por tanto para nuestras rectas la ecuación se reducirá a $x / y$.
Podemos ver que algo sucede con los puntos que no son visibles, y es que la recta que los une puede ser expresada por un múltiplo de la recta de uno que si es visible. El caso más sencillo: tomando el punto visible $(1, 1)$ y el punto no visible $(3, 3)$, tenemos que las coordenadas del punto no visible es tan solo $(3 * 1) / (3 * 1)$, la forma para identificar esto es obtener el MCD de $x$ y $y$, mientras que para el punto visible $MCD(x, y) = 1$, para el no visible $MCD(x, y) > 1$.

Ahora solo hay que obtener todos los puntos dentro de nuestra cuadrícula cuyo MCD sea igual a 1 para cada consulta que nos hagan. Esto es sencillo pero es un gasto inecesario de recursos, por lo que lo mejor es realizar un precálculo partiendo de que para $N = 0$ la respuesta es $0$ y para $N = 1$ la respuesta es $3$. Otro punto a considerar es que podemos solo calcular la mitad de los puntos ya que los puntos son simétricos.

a[0] = 0;
a[1] = 3;
for(int x = 2; x <= 1000; x++){
 int sum = 0;
 for(int y = 1; y < x; y++){
  if(mcd(x,y) == 1) sum++;
 }
 a[x] = a[x-1] + 2 * sum;
}

Dado un conjunto de $N$ ($1 ≤ N ≤ 2000$) ciudades y $M$ ($0 ≤ M ≤ 50000$) carreteras cada una con un costo $P_i$ ($0 ≤ P_i ≤10^7$) de construcción distinto y un costo $C$ ($0 ≤ C ≤10^7$) por construir un aeropuerto, determinar el menor costo para conectar las $N$ ciudades. En este problema el aeropuerto cumple una función peculiar, ya que una carretera que va de una ciudad A a una ciudad B funciona como una arista bidireccional en un grafo; mientras que colocar un aeropuerto en una ciudad A forma una arista bidireccional con cualquiera otra ciudad que tenga un aeropuerto.

Del problema mismo sabemos que para que dos ciudades se consideren conectadas debe existir una o varias aristas entre ellas. También sabemos que para obtener el costo mínimo la forma final de las conexiones debe ser un árbol (para evitar ciclos y por tanto aristas innecesarias), ya que en un árbol solo ocuparíamos $N - 1$ aristas. De inmediato el problema nos suena como a un simple árbol de mínima expansión... pero, ¿qué sucede con los aeropuertos?

El problema nos indica que pueden existir desde $0$ hasta $50000$ carreteras, por lo cual nosotros podemos esperar que existan ciudades a las cuales no es posible llegar por ninguna carretera y por lo tanto tratar de considerarlos en un árbol de mínima expansión es imposible (llamaremos componente conexa a un conjunto de $n$ ciudades unidas con $n - 1$ carreteras), es ahí donde los aeropuertos tienen una de sus funciones principales. Otra función de los aeropuertos se da cuando construir una carretera entre A y B es más costoso que construir un áeropuerto en A y B.

Recapitulando: sabemos que pueden existir varias componentes conexas, sabemos que construyendo un aeropuerto en cada una de ellas garantizaría que estén conectadas, sabemos que a veces el costo de construir una carretera entre dos ciudades es mayor al de poner aeropuertos en ellas y por último sabemos que queremos obtener el menor costo para conectarlas todas.

Para resolverlo, partiremos de que cada una de las $N$ ciudades tiene un áeropuerto y por tanto están todas conectadas lo cual tendrá un costo $C_0$, posteriormente iremos uniendo (como si estuvieramos formando un árbol de mínima expansión) a cada unión quitaremos un aeropuerto, ya que no es necesario una vez que exista una carretera entre dos ciudades, porque estas estarían conectadas de todos modos, al hacer esto obtendremos un costo $C_i$ ($1 ≤ i ≤ Z$, $Z$ es el número de uniones que es posible realizar), lo que nos queda por hacer extraer el valor mínimo de todos los $C_i$ para obtener la respuesta.

Lo único que resta por considerar es que de este modo de resolver el problema puede suceder que al final nos quede una sola componente conexa y por tanto un solo aeropuerto, lo cual representa un gasto innecesario y por tanto no debe ser parte de nuestra solución.

long long int ans = N * C;
long long int roadCost = 0;
int airports = N;
for(int i = 0; i < roads.size(); i++){
 if(join(roads[i].o, roads[i].d)){
  roadCost += roads[i].c;
  airports--;
  ans = min(ans, roadCost + airports * C);
 }
}
if(airports == 1)
 ans = min(ans, roadCost);
pritnf("%lld\n", ans);

Link del problema: 2858 - Parsing Binary Strings

Problema: Dada una cadena S que solo tiene números binarios y letras minúsculas de la 'a' a la 'z' imprimir todos los caracteres excepto las cadenas de números binarios, a estas cadenas convertirlas a su representación decimal e imprimirlas junto a la cadena. A lo más serán 10,000 caracteres para lo cual es necesario sacar modulo 1000000007 (10^9 + 7) ya que el número puede ser muy grande.

Ejemplo:
Input:

saludosamis11amigosqueestana1010kilometrosdedistancia

Output:

saludosamis3amigosqueestana10kilometrosdedistancia

Complejidad: O(N) donde $1<=N<=10000$ es el número de caracteres dentro de la cadena.

Solución:

Este problema es muy simple ya que basta con ir recorriendo caracter a caracter y checar que si no es 1 ó 0 solo lo imprimamos el caracter pero ¡¿que pasa cuando es Binary String!?
Lo primero que se nos ocurriría es tratar la Binary String con corrimientos pero dado que el número puede ser muy grande esto no funcionaría así que con una simple operación de multiplicar por 2 cada que haya 0 o 1 será suficiente. 
Primero hacemos un define de nuestro modulo para no tener que estar poniendo tanto 0 xD:

#define modulirri 1000000007

Así pues tendríamos dos decisiones:

numerote = 0;
if(S[i]=='1'){
    numerote *= 2;
    numerote += 1;
    numerote %= modulirri;
}

else if(S[i]=='0'){
   numerote *= 2;
   numerote %= modulirri;
}