Translate

lunes, 11 de noviembre de 2013

Problema E : Eleven (Regional Latinoamerica 2013)

Escrito por Rodrigo Burgos Domínguez

Problema E : Eleven

La redacción del problema es muy simple, aun que el problema no lo es, lo que dice el problema que dado un número N hay que encontrar todos los anagramas de N (que no tengan dígitos ceros a la izquierda) , tal que sean divisibles por 11, la solución de programación dinamica se ve obvia, pero la forma de hacerla no lo es, un comentario de Ulises Méndez sobre la propiedad del 11 me ayudo a ver una solución no tan complicada, si buscan en internet encontraran que para que un numero sea divisible por 11 basta con sumar los dígitos que están en posiciones pares y resta le todos los dígitos que están en posiciones impares, si el resultado es divisible por 11 entonces el numero de divisible por 11.

Por ejemplo: 4785 , sumamos las posiciones impares 4 + 8 = 12 y luego sumamos las posición pares 7 + 5 = 12, restamos el segundo al primero 12 - 12 = 0 , y como 0 % 11 = 0, por tanto es divisible por 11.

Ya que tenemos este concepto solo nos tenemos que preocupar que la diferencia entre los pares eh impares sea divisible entre 11. Existe otro detalle, ya que nos piden que los anagramas sean numero sin ceros a la izquierda, esto es sencillo ( aun que no trivial de ver) , nosotros forzamos al numero que vamos a generar a que su primer dígito sea diferente de cero, es por eso que van a ver en el codigo esta parte ( countDigit es una arreglo donde guardamos el numero de 0, 1, 2 , 3, .. 9 que hay en el numero que leemos al inicio)
   for( digit = 1; digit <= 9; digit++) 
     if( countDigits[ digit ] > 0 ){
        countDigits[ digit ]--; 
        memset( vis, 0, sizeof( vis ));
        res = ( res + solve( 0 , pares, impares - 1, 11 - digit)) % MOD;
        countDigits[ digit ]++;
     }

Como ven descartamos un dígito el 1 o el 2, o el 3, ... al 9, dependiendo cual tratamos de forzar a que sea el primer digito de nuestro posible anagrama. Posteriormente resolvemos nuestra dinamica mandando ( digitoInicial ( siempre se empieza en cero para recorrer de cero a nueve), Numero de elementos pares que nos faltan, numero de elementos impares ( como ven se resta el primero que ya utilizamos) , modulo que llevamos hasta el momento (como ven es 11 - digito, ya que los impares se restan ).

La dinamica es de la siguiente forma:
  solve( int posDigit, int pares, int impares, int mod)

Nosotros nos vamos a estar moviendo de dígito en dígito, primero en el cero, luego en el uno,... , hasta el nueve, para eso es posDigit también llevamos el número de elementos pares que nos hace falta colocar en nuestro anagrama factible, así como los impares , el mod solo contendrá la suma de las diferencia de los dígitos pares e impares.

Lo siguiente para resolver el problema es darse cuenta que si tenemos 5 dígitos de un tipo, solo los podemos colocar de la siguiente manera, { (0 pares , 5 impares), ( 1 par, 4 impares), ( 2 pares, 3 impares), ( 3 pares, 2 impares), ( 4 pares, 1 impar) , ( 5 pares, 0 , impares) }, no son muchas en el peor de los casos vamos a tener 100 dígitos iguales, en esta parte hago uso de un for con la variable slice esta variable va a cortar y determinar cuantos impares y pares:
for( slice = 0; slice <= countDigits[ posDigit ]; slice++){

Dependiendo del numero de elementos del dígito vamos a partilos como se los había mencionado , el numero de pares seria igual a slice y numero de impares seria igual a countDigits[ posDigit ] - slice , agregando estos dígitos tenemos que calcular nuestro nuevo modulo, ya que al agregar digitos pares e impares se modifica:
newmod = ((mod + ( slice * posDigit ) - ( (countDigits[ posDigit ] - slice ) * posDigit )) % 11 + 11 ) % 11 

Se suma el modulo que tenemos y se agregan los dígitos pares e impares, pueden notar que se restan los impares, también van a ver varios módulos 11, esto es por que la resta puede quedar un numero negativo y debemos asegurarnos que sea siempre positivo.
Ya que tenemos nuestro nuevo modulo podemos contar cuantos resultados tenemos si escogemos esa cantidad de pares eh impares con el digito en cuestión, lo que hacemos es invocar el solve para que calcula el siguiente dígito posDigit + 1 , también hay que restar nuestros pares usados en este momento, así como los impares y lo invocamos con nuestro nuevo modulo.
R = solve( posDigit + 1, pares - slice, impares - ( countDigits[ posDigit ] - slice ) , newmod ) % MOD;
Todavía no se acaba, ya colocamos el numero de dígtos pares, pero en el numero pueden estar distribuidos en cualquier posición disponible para dígitos pares, es por eso que se hacen las combinaciones de numeroParesDisponibles en paresAAgregar, lo mismo para los impares y estos dos resultados se multiplican el numero de soluciones factibles que obtuvimos del proximo digito.
R = ( R * ( ( comb(pares, slice) * comb( impares, ( countDigits[ posDigit ] - slice ) )) % MOD) ) % MOD;

( si es complejo de enterder pero espero les sirva el post, si tienen dudas o quieren que aclare algo mas, no duden en solicitarlo a rodrigo.burgos@gmail.com).
Aquí les dejo el código completo para que lo analicen:

/* Rodrigo Burgos Dominguez */
# include "stdio.h"
# include "string.h"

# define MOD ((long long)1000000007)

char num[200];
int length, countDigits[10];
long long dinComb[102][102];

long long din[11][102][102][12];
int vis[11][102][102][12];

long long comb(int a, int b){
  if( a == 0 &&  b == 0 ) return 1;
  if( b > a  ) return 0;
  if( b == 0 ) return 1;
  if( b < 0 ) return 0;
  if( dinComb[a][b] != -1 ) return dinComb[a][b];
  return dinComb[a][b] = (comb(a - 1, b - 1) + comb(a - 1, b)) % MOD;
}

long long solve( int posDigit, int pares, int impares, int mod){
   long long res = 0, R;
   int newmod, slice;
   if( pares < 0 || impares < 0 ) return 0;
   if( posDigit == 10 ) {
      return (pares == 0 && impares == 0 && mod == 0) ? 1 : 0 ; 
   }
   if( vis[posDigit][pares][impares][mod] == 1) return din[posDigit][pares][impares][mod];
   vis[posDigit][pares][impares][mod] = 1;
   for( slice = 0; slice <= countDigits[ posDigit ]; slice++){
     newmod = ((mod + ( slice * posDigit ) - ( (countDigits[ posDigit ] - slice ) * posDigit )) % 11 + 11 ) % 11;
     R = solve( posDigit + 1, pares - slice, impares - ( countDigits[ posDigit ] - slice ) , newmod ) % MOD;
     R = ( R * ( ( comb(pares, slice) * comb( impares, ( countDigits[ posDigit ] - slice ) )) % MOD) ) % MOD;
     res = (res + R) % MOD;
   }
   return din[posDigit][pares][impares][mod] = res % MOD;
}


main(){
  int pares, impares, digit, x;
  long long res;
  memset( dinComb, -1, sizeof( dinComb ) );
  while( scanf("%s", num) != EOF ){
   length = strlen( num );
   memset( countDigits, 0, sizeof( countDigits ));
   for( x = 0 ; x < length ; x++) countDigits[ num[x] - '0']++;
   pares = ( length / 2 );
   impares = ( length / 2) + ( length % 2);
   res = 0;
   for( digit = 1; digit <= 9; digit++) 
     if( countDigits[ digit ] > 0 ){
        countDigits[ digit ]--; 
        memset( vis, 0, sizeof( vis ));
        res = ( res + solve( 0 , pares, impares - 1, 11 - digit)) % MOD;
        countDigits[ digit ]++;
     }
   printf("%lld\n", res);
  }
  return 0; 
}

sábado, 9 de noviembre de 2013

Problema A : Attacking rooks (Regional Latinoamerica)

Escrito por Rodrigo Burgos Domínguez

Problema A : Attacking rooks ( Regional Latino America 2013) Un problema un poco complejo de regional 2013 de Mexico, practicamente trata de dado una cuadricula de N x N , y unas celdas bloqueadas, es colocar el maximo numero de torres ( torre de ajedrez se mueve en toda su columna y toda su fila si no encuentra obstáculo), de tal manera que ninguna torre se ataque entre si.

Lo primero que uno debe observar que una torre puede bloquear una columna completa y una fila completa, entonces por cada posición del tablero si uno coloca una torre en esa posición bloquea la columna y fila de dicha posición, estas filas y columnas que nos referimos no es la fila completa del tablero si no una subparte de dicha fila ya que puede estar delimitada por puntos bloquedos ( o peones en el problema).

Para formar todos las sub filas y utilizo estos fors:

   newFil = 0;
      for( r = 1; r <= n; r++){
       for( c = 1; c <= n; c++){
        if( map[r][c] != 'X'){
         if( fils[r][c - 1] == 0 ) fils[r][c - 1] = ++newFil;
         fils[r][c] = fils[r][c - 1];
        }
       }
      }
      


como se puede analizar lo que hace es marcar como una nueva fila, las subpartes cada que encuentra una posición bloqueada incrementa en esa posición un nueva fila y para todas las demás le asigna el numero de la fila de la posición bloqueada. ( en el caso de ser inicio de fila tambien se asigna una nueva fila).

Ya con eso podemos hacer una relación de subFiles y subColumnas, y lo que hay que maximizar es el numero de conexiones que hay entre las filas y columnas, en pocas palabras utilizar maximo matching.

Les comporta la solucion general del problema:

/* Rodrigo Burgos */

# include 
# include 

# define MAX 100
char map[MAX + 3][MAX + 3];
int cols[MAX + 3][MAX + 3];
int fils[MAX + 3][MAX + 3];
int mark[MAX * MAX + 2], vis[ MAX * MAX + 2];
char graph[MAX*MAX/2+1][MAX*MAX/2+1];

int newFil, newCol;

int match(int nodo ){
  int x;
  if( vis[nodo] == 1 ) return 0;
  vis[nodo] = 1;
  for( x = 1; x <= newCol; x++)
    if( graph[nodo][x] == 1 && ( mark[ x ] == -1 || match( mark[ x ])) ){
       mark[x] = nodo;
       return 1; 
    }
  return 0;
}

main(){
  int r, c, cont, x, n; 
   while( scanf("%d", &n) != EOF ) {
      memset( cols, 0, sizeof( cols ) );
      memset( fils, 0, sizeof( fils ) );
      for( x = 1; x <= n; x++) scanf("%s", map[x] + 1);
      newFil = newCol = 0;
      for( r = 1; r <= n; r++){
       for( c = 1; c <= n; c++){
        if( map[r][c] != 'X'){
         if( cols[r - 1][c] == 0 ) cols[r - 1][c] = ++newCol;
         cols[r][c] = cols[r - 1][c];
        }
       }
      }
      for( r = 1; r <= n; r++){
       for( c = 1; c <= n; c++){
        if( map[r][c] != 'X'){
         if( fils[r][c - 1] == 0 ) fils[r][c - 1] = ++newFil;
         fils[r][c] = fils[r][c - 1];
        }
       }
      }
      memset( graph, 0, sizeof( graph ) );
      for( r = 1; r <= n; r++){
       for( c = 1; c <= n; c++)
         if( map[r][c] != 'X'){
          graph[fils[r][c]][cols[r][c]] = 1;
         }
      }
      memset( mark, -1, sizeof( mark ) );
      cont = 0;
      for( x = 1; x <= newFil; x++){
        memset( vis, 0, sizeof( vis ) );
        if( match( x ) ) cont++;
      }
      printf("%d\n", cont);
   }
   return 0; 
}

Resultado online Regional 2013 America Latina, Mexico, Venezuela, Cuba .



  Les dejo la liga donde pueden ver el scoreboard:

http://score.bombonera.org/

problemas:

Problema A

Problema B

problema C

Problema D

Problema E


Problema F


Problema G


Problema H


Problema I

Problema J

martes, 5 de noviembre de 2013

2533 - Connecting Cities (Kruskal)

Escrito por Rodrigo Burgos Domínguez

2533 - Connecting Cities (Kruskal)

Este problema se presento en un concurso de preparación para el regional 2013, el problema nos decía que hay costos de conectar una ciudad a otra, y te dan todas las posible aristas y sus costos que puedes utilizar, tu tarea es encontrar el mínimo costo de conectar todas las ciudades, esto parecería directamente un Kruskal, pero ademas de eso puede colocar aeropuertos y el costo de colocar un aeropuerto en cualquiera de la ciudades es C.

Para el caso simple nosotros podemos utilizar kruskal, suponiendo que no colocamos ningún aeropuerto, pero que pasa cuando es necesario colocar lo, lo que debemos observar que colocar una unión de una ciudad a otra por medio de un aeropuerto nos cuesta 2C, ya que no existen entre ellas un aeropuerto , pero cuando colocamos la unión de otra, por ejemplo tenemos un aeropuerto del en el nodo A y B, y ahora queremos conecta Q con P, realmente no importa la conexión de Q con P, haciendo un aeropuerto en P, podemos conectar tanto A y B con P , con el único costo C, con esta hipótesis, lo que hacemos es agregar todas las aristas de todos los nodos contra todos los nodos con costo C, y aplicar kruskal, el resultado le sumamos el costo de la primera arista que generó dos aeropuertos C.

de ahi tenemos el siguiente codigo:

/*
  Rodrigo Burgos Dominguez
*/

# include "stdio.h"
# include "string.h"

# define MAX_ARISTAS 5000000
# define MAX_NODES 2000

typedef struct { int a, b, cost; } ARISTA;

ARISTA A[MAX_ARISTAS + 1];


int set[MAX_NODES + 1];

int min( int a, int b){ return a < b ? a: b; }

int getSet( int nodo ){ 
  return set[ nodo ] == nodo ? nodo : (set[nodo] = getSet( set[nodo] ) );
}

int compare(ARISTA *a, ARISTA *b){ return a->cost - b->cost; }

int kruskal(int N, int M){
  int x, sol = 0, a, b, contAristaAgregadas  = 0;
  for( x = 0 ; x <= N; x++) set[x] = x;
  qsort( A, M, sizeof( ARISTA ), compare );
  for( x = 0; x < M; x++){
     a = getSet( A[x].a);
     b = getSet( A[x].b);
     if( a != b){
       contAristaAgregadas ++;
       set[a] = b;
       sol += A[x].cost; 
     }
  }
  return ( contAristaAgregadas  == N - 1 ) ? sol : (1<<28);
}

main(){
  int sol, ncases, cases, x, y;
  int N, M, C; 
  for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
     scanf("%d %d %d", &N, &M, &C); 
     for( x = 0; x < M; x++){
      scanf("%d %d %d", &A[x].a, &A[x].b, &A[x].cost);
     }
     sol = kruskal(N, M);
     for( x = 1; x <= N; x++)
     for( y = x + 1; y <= N ; y++) {
        A[ M ].a = x;
        A[ M ].b = y; 
        A[ M ].cost = C;
        M++;
     }
     sol =  min( sol, kruskal(N, M) + C);
     printf("%d\n", sol);
  }

Algoritmo de Kruskal

Escrito por Rodrigo Burgos Domínguez

Algoritmo de Kruskal Kruskal es una algoritmo muy utilizado en los concursos para la resolución de problemas que tiene que ver con el árbol de expansión mínima( MST) , la técnica de Kruskal, es ordenar todas las aristas ( dependiendo si uno quiere la expansión mínima o máxima) , al ordenar las aristas con el menor costo se va agregando la arista menor formando un árbol, en el momento que al agregar una arista se agregue un ciclo esta arista no es considerada parte de la solucion.

Vamos a elaborar el código paso por paso:

Creamos una estructura de datos llamada Arista:

typedef struct { int a, b, cost; } Arista;


en esta estructura de datos vamos a guardar la información de cada arista, el nodo origen 'a', el nodo destino 'b' y obviamente el costo de la arista 'cost', posteriormente declaramos el arreglo donde vamos a guardar todas nuestras aristas:

# define MAX_ARISTA 100000 // dependiendo el numero de aristas:

Arista[MAX_ARISTA +1] A;  


Bueno eso es solo una parte del problema el como guardar la información ahora veamos el algoritmo:

Supongamos que N es el numero de nodos y M el numero de aristas, tenemos el siguiente seudocódigo ( como aparece en Wikipedia http://en.wikipedia.org/wiki/Kruskal's_algorithm ):

KRUSKAL(G):
1 A = ∅
2 foreach v ∈ G.V:
3   MAKE-SET(v)
4 foreach (u, v) ordered by weight(u, v), increasing:
5    if FIND-SET(u) ≠ FIND-SET(v):
6       A = A ∪ {(u, v)}
7       UNION(u, v)
8 return A


Vamos a seguir este algoritmo, la única diferencia que nosotros nada mas vamos a regresar el costo

int kruskal(int N, int M){
  int x, sol = 0, a, b, contAristaAgregadas = 0;
  for( x = 0 ; x <= N; x++) set[x] = x;
  qsort( A, M, sizeof( ARISTA ), compare );
  for( x = 0; x < M; x++){
     a = getSet( A[x].a);
     b = getSet( A[x].b);
     if( a != b){
      contAristaAgregadas++;
       set[a] = b;
       sol += A[x].cost; 
     }
  }
  return ( contAristaAgregadas == N - 1 ) ? sol : (1<<28);
}


como puedes observar, creamos nuestro conjunto o mejor dicho lo inicializamos:

for( x = 0; x <= N; x++) set[x] = x;


este arreglo lo que quiere decir es que el conjunto 0 pertenece al conjunto 0, el conjunto 1 al conjunto 1, en pocas palabras cada conjunto contiene solo un elemento, el mismo, al inicio todos los nodos perteneces a su correspondiente conjunto, nodo 0 al conjunto 0 , nodo 1 al conjunto 1, etc.

posteriormente se ordenan las aristas:

qsort( A, M, sizeof( ARISTA ), compare );


Esta función es parte de ANSI C , y lo único que se tiene que agregar es la función comparar que seria de la siguiente manera:

int compare(ARISTA *a, ARISTA *b){ return a->cost - b->cost; }


Esta función compara *a y *b, si *a es menor a *b debe regresar un numero negativo, si es mayor un positivo y si es igual debe regresar 0.

Para el caso de c++, también se puede ordenar con la función sort

# include "algorithm"

bool compare(ARISTA a, ARISTA b){ return a.cost < b.cost; }

// ordenacion

sort( A, A + M , compare);

El siguiente paso es iterar todas las aristas, como ya están ordenadas van de menor a mayor:

  for( x = 0; x < M; x++){
     a = getSet( A[x].a);
     b = getSet( A[x].b);
     if( a != b){
      contAristaAgregadas++;
       set[a] = b;
       sol += A[x].cost; 
     }
  }


aquí hay algo curioso y esta parte amerita una explicación mas profunda ya que es lo que hace posible el la unión de conjunto el getSet , ¿que es esta función?

Esta función lo que hace es lo siguiente:

int getSet( int conjunto) { 
   if( set[conjunto] == conjunto) return nodo;
   set[conjunto] = getSet( set[conjunto]);
   return set[conjunto];
}


Lo que valida es si el conjunto que esta preguntando pertenece al mismo conjunto del que empezó,esto quiere decir que nadie a movido a ese conjunto, en otro caso si lo han movido y ahora el conjunto pertenece a otro conjunto, en ese momento podemos regresar que pertenece al conjunto guardado pero puede ser que el conjunto al que apunta ahora pertenezca a otro conjunto, entonces recursivamente se mueve al siguiente conjunto getSet( set[conjunto]), y así aseguramos que regresemos realmente el conjunto que pertenece el nodo en cuestión.

Como se observa al regresar el siguiente conjunto actualizamos el valor
   set[conjunto] = getSet( set[conjunto]);


Esto es para que la búsqueda sea optima, si por ejemplo el conjunto 1 apunta al 2, el 2 al 3, el 3, al 4, … y el 9999 al 10000 , se procesaría cada consulta del nodo 1 diez mil veces, pero al agregar esta actualización la siguiente vez que se pregunte sobre el nodo 1, solo se consultaría el conjunto 1 y el 10000 y validaría si el 10000 no ha sido modificado.

Esta parte es crucial en el algoritmo y deben entender bien la función getSet.

siguiendo con el algoritmo de Kruskal:

  // RECORDANDO 
  for( x = 0; x < M; x++){
     a = getSet( A[x].a);
     b = getSet( A[x].b);
     if( a != b){
      contAristaAgregadas++;
       set[a] = b;
       sol += A[x].cost; 
     }
  }
  


lo que sigue es validar que el conjunto de la arista de ‘a’ sea diferente de la arista de ‘b’ , por tanto se realiza por medio de esto:
     a = getSet( A[x].a);
     b = getSet( A[x].b);
     if( a != b){
     }


si a ¡= b entonces no perteneces al mismo conjunto y se agrega la arista como parte de la solución:

       contAristaAgregadas++;
       set[a] = b;
       sol += A[x].cost; 


en conAristasAgregadas, el nombre lo dice todo , contamos el numero de aristas agregadas, hacemos el conjunto ‘a’ que pertenesca al conjunto de 'b':

set[a] = b;  // si, así de fácil.


y sumamos la arista:

sol += A[x].cost; 


al final del algoritmo debemos garantizar que sea conexo, y para eso validamos el numeró de aristas agregadas sean igual al N – 1 :

  return ( contAristaAgregadas == N - 1 ) ? sol : (1<<28);


si es igual a N – 1, regresamos la solución que llevamos, en otro caso regresamos infinito en este caso 2 a la 28 ( este valor puede no ser suficiente si el costo de las aristas es muy grade, hay que tener cuidado en esto).

al final nuestro algoritmo queda de la siguiente manera:


# include "stdio.h"
# include "string.h>
# define MAX_ARISTAS 5000000
# define MAX_NODES 2000

int set[MAX_NODES + 1];

int getSet( int conjunto ){ 
  return set[ conjunto ] == conjunto ? conjunto : (set[conjunto] = getSet( set[conjunto] ) );
}

typedef struct { int a, b, cost; } ARISTA;

ARISTA A[MAX_ARISTAS + 1];


int compare(ARISTA *a, ARISTA *b){ return a->cost - b->cost; }

int kruskal(int N, int M){
  int x, sol = 0, a, b, contAristaAgregadas  = 0;
  for( x = 0 ; x <= N; x++) set[x] = x;
  qsort( A, M, sizeof( ARISTA ), compare );
  for( x = 0; x < M; x++){
     a = getSet( A[x].a);
     b = getSet( A[x].b);
     if( a != b){
       contAristaAgregadas ++;
       set[a] = b;
       sol += A[x].cost; 
     }
  }
  return ( contAristaAgregadas  == N - 1 ) ? sol : (1<<28);
}



Un ejemplo de kruskal es este 2533 - Connecting Cities



Cualquier duda o sugerencia pueden escribirme a rodrigo.burgos@gmail.com

jueves, 31 de octubre de 2013

2457 - Piece Creation (Programación Dinamica COJ)

2457 - Piece Creation

Este problema nos dice que teniendo puntos en un tablero, nosotros podemos trazar líneas horizontales y verticales que conecten el punto con el extremo del tablero, con la restricción de que no toque otro punto o otra línea que conecte otro punto con la orilla del tablero ( Esto es un circuito electrónico que conecta un punto del circuito con la orilla ya que en la orilla esta la corriente). La tarea es encontrar el costo mínimo de hacer esto, ya que cada cm de línea que utilicemos tiene un costo.

Lo primero que se me ocurrió fue hacer un flujo máximo a costo mínimo, cada punto del tablero serian dos nodos un nodo incidente y otro adyacente, donde cada nodo incidente y adyacente que represente un nodo tendría una arista de costo 1 o de capacidad 1 , esto para evitar que pasara por el mas de un cable , si existiera un punto en esta coordenada simplemente esta arista no existiría, y de hecho resolvía el problema general, de conectar con el mínimo cable todos los puntos, pero el problema tiene una restricción, que solo pueden ser líneas rectas, esta solución encuentra un cableado donde se puede modificar la dirección del cable.

Después de pensar un rato mas encontré algo interesante, que es el tamaño del chip ( o del tablero) es menor a 30, y solo hay 50 puntos , si nosotros ordenamos de menor a mayor , por coordenadas Y y posteriormente por X, tenemos que cuando coloquemos un punto P[pos] después de P[pos - 1 ], este punto o esta arriba ( P[pos-1].y < P[pos - 1].Y ) o esta a la derecha ( P[pos-1].x < P[pos].x) , con esto podemos saber dos cosas, primero si puedo conectar el punto P[pos] a la derecha , ya que si P[pos-1].y == P[pos].y no es posible, y llevando el control del rango [A,B], donde A es el punto donde inicia el tablero visible de arriba y B es la posición del tablero donde termina el espacio visible, a que me refiero con campo visible, por ejemplo el campo visible al inicio es de 0 a 31, si un punto esta en la coordenada X = 5 y se conecta con otro a la izquierda tapa todos los nodos del 0 al 5 entonces el campo visible de tablero superior es de 6 al 31, si existiera otro que fuera a la derecha a partir de X = 9 , se tendría un campo visible de 6 al 8, entonces si nosotros llevamos esto en nuestra dinámica o mejor dicho en nuestra memorización , podríamos saber si puedo conectarme arriba y a la izquierda y como siempre se puede conectar a la derecha , casi se tiene resuelto el problema, para resolver el problema de si puede ir hacia abajo , simplemente llevamos otro rango [a,b], este rango es el rango permitido de colocar un punto, si nosotros colocamos un punto que va hacia abajo partiría en dos el tablero, y si un punto se quiere conectar al a izquierda solo podría hacerlo si el b = 31 , o si quiere ir a la derecha tendría que a ser igual a cero ( a=0) , si garantizamos que al partir el tablero ( conectarlo hacia abajo no hay un punto en ese trayecto) entonces solo restaría agregar los puntos siguiente dependiendo si están de lado de una partición o si están del otro lado. Aquí les dejo el código:

/*Autor: Rodrigo Burgos Dominguez*/

# include "stdio.h"
#include "string.h"

typedef struct { int x,  y;  } POINT;

POINT p[100];
int AA, n;

int compare( POINT *a, POINT *b){
  if( a->y != b->y)
   return a->y - b->y; 
  return a->x - b->x;
}

int min( int a, int b){ return a < b ? a: b;}
int max( int a, int b){ return a > b ? a: b;}

int din[51][32][32][32][32];
int mapMax[100];
int mapMin[100];

int ladosMax[100];
int ladosMin[100];

int solve( int position, int A, int B, int a, int b){
  int res = (1<<22), path = -1, tres, cst = 0;
  if( position >= n ) return 0;
  if( din[position][A][B][a][b] != -1) return din[position][A][B][a][b];
  if( p[position].x <= a || p[position].x >= b ) 
    return din[position][A][B][a][b] = solve( position + 1, A, B, a, b);
   /* ARRIBA */
  if( p[position].y <= mapMin[ p[ position ].x ] && p[ position ].x < B && p[ position ].x > A){
    tres = solve( position + 1 , A, B, a, b ) + p[ position ].y ;
    if( tres < res ){
       res = tres;
       path = 0;
       cst = p[ position ].y;
    }
  }
  /* IZQUIERDA */
  if( p[position].x <= ladosMin[ p[ position ].y ] && a == 0 ){
    tres = solve( position + 1 , max( A, p[ position].x), B, a, b ) + p[ position ].x ;
    if( tres < res){
       res = tres;
       path = 1;
       cst = p[ position ].x; 
    }
  }
  /* DERECHO */
  if( p[position].x >= ladosMax[ p[ position ].y ] && b == 31 ){
    tres =  solve( position + 1 , A, min( B, p[position].x ), a, b ) + ( AA - p[ position ].x);
    if(tres < res){
      res = tres;
      path = 2;
      cst =  ( AA - p[ position ].x);
    }
  }
  /* ABAJO */
  if( p[position].y >= mapMax[ p[ position ].x ]){
    tres = solve( position + 1 , A, B, a, p[ position].x  )  + solve( position + 1, A, B, p[ position ].x , b)+ ( AA - p[ position ].y );
    if( tres < res){
       res = tres;
       path = 3; 
       cst = ( AA - p[ position ].y );
    }
  }
/*  printf("(%d %d) %d %d %d %d %d -> %d -> path %d cost %d\n", p[position].x, p[ position].y, position, A, B, a, b, res, path, cst);*/
  return din[position][A][B][a][b] = res; 
}

main(){
  int x, res;
  while( scanf("%d %d", &AA, &n) != EOF ){
     memset( din, -1, sizeof( din ));
     for( x = 0; x <= AA; x++){
      mapMax[ x ] = -(1<<22);
      mapMin[ x ] = (1<<22);
      ladosMax[x] = -(1<<22);
      ladosMin[x] = (1<<22);
     }
     for( x = 0; x < n; x++){
      scanf("%d %d", &p[x].x, &p[x].y); 
      mapMax[ p[x].x ] = max(mapMax[ p[x].x ], p[x].y);
      mapMin[ p[x].x ] = min(mapMin[ p[x].x ], p[x].y);
      ladosMax[ p[x].y ] = max(ladosMax[ p[x].y ] ,  p[x].x);
      ladosMin[ p[x].y ] = min(ladosMin[ p[x].y ] ,  p[x].x);
     }
     qsort( p, n, sizeof( POINT ), compare );
     res = solve( 0, 0, 31, 0, 31);
     if(res >= (1<<22))
       printf("No solution\n");
     else
       printf("The total length of wire used is %d\n", res);
  }
  return 0; 
}

martes, 14 de agosto de 2012

UVA 10407 Simple division

UVA 10407 Simple division


http://uva.onlinejudge.org/external/104/10407.html
Buenos dias a todos, les comparto este problema, practicamente se trata de encontrar un numero que al dividir a toda una lista de numeros regresen todos el mismo residuo, en el algoritmo que expongo abajo se puede ver que la solucion la pongo como un "Fuerza Bruta pero no tanto" ya que mi idea no se basa tanto en las propiedades de la division del numero y como no soy un matematico puro no se me ocurre directamente como sacar una solucion con estas propiedades.
Esta solucion radica en el hecho si tomo dos numeros distintos la cantidad de numeros que al dividirlo me resulte el mismo residuo no son muchos, por tal motivo lo primero que hago es quitar todos los numero repetidos:
  // ESTO VA FUERA DEL MAIN
  int compare( int *a, int *b){ return *a - *b; }
  // FIN DE LO QUE VA FUERA DEL MAIN
  
  
    qsort( list, n, sizeof( int ), compare );
    nsize = 1;
    for( x = 1; x < n; x++){
       if( list[ x ] != list[ x - 1]){
           list[ nsize++ ] = list[x];
       }
    }


Primero ordeno, y luego si son distintos los guardo en la ultima posicion libre que tengo, primero n es el tamaño de mi lista y al final nsize sera mi nuevo tamaño de la lista.
Dejo reposar el algoritmo por unos segundos, y despues calculo todos los numeros que dividen a los numeros mas pequeños, ya que trato de procesar la menor cantidad de operaciones:
  // ESTO VA FUERA DEL MAIN
  int compare2( int *a, int *b){ return abs(*a) - abs(*b); }
  // FIN DE LO QUE VA FUERA DEL MAIN

    qsort( list, nsize, sizeof( int ), compare2 );
    npa = 0;
    for( div = 1; div <= max( abs(list[0]) , abs(list[ 1 ]) ); div++)
       if( ((list[ 0 ] % div) + div ) % div == ((list[ 1 ] % div) + div ) % div) posibleAnswer[ npa++ ] = div;
Orderno la nueva lista sin elementos repetidos, pero en vez de ordenarlo de menor a mayor, los ordeno de menor a mayor, pero aplicando la funcion de valor absoluto a los numeros. Despues procedo a fuerza bruta ver todos los numero que su residuo sea igual del primer y el segundo elemento de la lista,

Por que hago (( A % div) + div) % div ?

Cuando era niño me preguntaba si los numero negativos al dividirlos sus residuos eran positivos, bueno asi es, pero cuando lo haces en C/C++ eso no es cierto, el residuo es negativo y lo tienes que volver positivo, por eso primero saco el residuo de A / div , despues le sumo div, esto asegura que se vuelva positivo, y por ultimo le vuelvo a sacar el residuo, ya que si era positivo el residuo al sumarle div se saldria del rango de [0, div - 1].
Ya despues de que cuajo la solucion, lo que resta es hacer un barrido con todos los numeros pero en vez de checar todos los divisores posibles, solo revisamos las pisibles soluciones ( en este caso las guarde en posibleAnswer ), y al momento de varificar si el nuevo numero tambien tiene como resuduo una posible solucion, se van eliminando los que no cumplen.
    for( x = 2; x < nsize; x++){
      nextsize = 0;
      for( div = 0; div < npa; div++){
        if(  ((list[ 0 ] % posibleAnswer[ div ])+ posibleAnswer[ div ] ) % posibleAnswer[ div ] 
             == ( ( list[ x] % posibleAnswer[div]) + posibleAnswer[ div ] ) % posibleAnswer[ div ] ){
           posibleAnswer[ nextsize++ ] = posibleAnswer[ div];
        }
      }
      npa = nextsize;
    }

Al final solo hay que imprimir el ultimo valor de nuestras posibles soluciones posibleAnswer[ npa - 1]

/* 
 Autor: Rodrigo Burgos Dominguez
 Problema: UVA 10407 Simple division
 Solucion: Fuerza Bruta pero no tanto.
*/

# include "stdio.h"
# include "string.h"


int max( int a, int b ){ return a > b ? a : b; }
int abs( int a ){ return a < 0 ? -a : a; }

int compare( int *a, int *b){ return *a - *b; }
int compare2( int *a, int *b){ return abs(*a) - abs(*b); }

int list[ 1002 ], n;
int posibleAnswer[1000*1000], npa;

main(){
  int a, b, x, y,  nsize, nextsize, div;
  while(1){
    for( n = 0; scanf("%d", &list[ n ]) != EOF && list[ n ] != 0 ; n++);
    if( n == 0 ) break;
    qsort( list, n, sizeof( int ), compare );
    nsize = 1;
    for( x = 1; x < n; x++){
       if( list[ x ] != list[ x - 1]){
           list[ nsize++ ] = list[x];
       }
    }
    qsort( list, nsize, sizeof( int ), compare2 );
    npa = 0;
    for( div = 1; div <= max( abs(list[0]) , abs(list[ 1 ]) ); div++)
       if( ((list[ 0 ] % div) + div ) % div == ((list[ 1 ] % div) + div ) % div) posibleAnswer[ npa++ ] = div;
    for( x = 2; x < nsize; x++){
      nextsize = 0;
      for( div = 0; div < npa; div++){
        if(  ((list[ 0 ] % posibleAnswer[ div ])+ posibleAnswer[ div ] ) % posibleAnswer[ div ] 
             == ( ( list[ x] % posibleAnswer[div]) + posibleAnswer[ div ] ) % posibleAnswer[ div ] ){
           posibleAnswer[ nextsize++ ] = posibleAnswer[ div];
        }
      }
      npa = nextsize;
    }
    printf("%d\n", posibleAnswer[ npa - 1]);
  }
  return 0; 
}
Cualquier duda o sugerencia contactarme a rodrigo.burgos@gmail.com
Manuel me copartio su solucion ya reducida matematicamente, vean como el algoritmo que el muestra es corto y elegante basandose en las propiedad de los numeros: http://thnkndblv.blogspot.mx/2012/08/10407-simple-division.html

lunes, 13 de agosto de 2012

UVA 12444 Bits and Piecest (Greedy)

UVA 12444 Bits and Piecest


http://uva.onlinejudge.org/external/124/12444.html
Este problema a simple vista parece difícil, pero al analizar un poco como se comporta los operadores binarios de AND y OR, nos damos cuenta que siempre debe tener los dos números, tanto A como B, los mismo bits de C, si existiera un bit en C que no estuviera prendido en D entonces hay un error, para encontrar el número cuya diferencia de |B - A| sea mínima, solo hace falta notar que todos los bits que no están C pero si están en D, el bit con valor mas alto se asigna a el valor de B y todos los demás bits se suman a A.

/*
  Problem: UVA 12444 Bits and Pieces
  Autor: Rodrigo Burgos Dominguez
  Problem: Let A and B be non-negative integers and let C = A&B and D = A|B. Given C and D, 
           can you find A and B such that the absolute difference (|A-B|) is minimal?
  Solution: greedy
*/

# include "stdio.h"
# include "string.h"

int transform[2][32];

long long max( long long a, long long b){ return a > b ? a : b; }
long long min( long long a, long long b){ return a < b ? a : b; }

void trans(int indice, long long number){
  int pos;
  memset( transform[ indice ], 0, sizeof( transform[ indice ]));
  for( pos = 0; number > 0 ; pos++){ 
    transform[indice][pos] = (number % 2);
    number /= 2;
  }
}

main(){
  int cases, ncases, notSolution, x;
  long long C, D, A, B, pot, last;
  for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
   scanf("%lld %lld", &C, &D);
   trans( 0, C );
   trans( 1, D );
   notSolution = A = B  = last = 0;
   for( x = 0, pot = 1; x < 32; x++, pot *= 2){
     if( transform[ 0 ][ x ] > 0 && transform[1][x] == 0 )  notSolution = 1;
     if( transform[ 0 ][ x ] > 0 ){
        A += pot;
        B += pot;
     }else if( transform[ 1 ][ x ] > 0 ){
       A += last;
        last = pot;
     }
   }
   B += last;
   if( notSolution == 1 ) printf("-1\n");
   else printf("%lld %lld\n", min(A,B), max(A,B));
  }
  return 0; 
}

Cualquier duda o sugerencia contactarme a rodrigo.burgos@gmail.com

miércoles, 25 de julio de 2012

Uva Online Judge 11691 - Allergy Test

Uva Online Judge 11691 - Allergy Test


http://uva.onlinejudge.org/external/116/11691.html

Al leer este problema, inmediatamente me di cuenta que se podía resolver con programación dinámica utilizando una mascara de bits, esta mascara de bits representaría las pruebas que ya eh utilizado, adicional a eso necesitaría llevar en mi programación dinámica, el espacio en días que la prueba anterior ocupa de tal manera que yo puedo hacer una prueba en cualquiera de esos días sin que impida saber si hay una reacción en la prueba anterior.

Al implementarlo fue un rotundo tiempo de ejecución excedido, paso bastante tiempo en que volviera a tratar de resolver el problema, después de meditar un rato, no era necesario saber si una prueba ya fue utilizada, si no podría diferenciarla por tamaño de días que dura su reacción y no individualmente, esto me dejaría que el numero de estados posibles no eran de 2^20 si no de las combinaciones de 20 en 7 que es muchísimo menor, para implementar la solución utilicé un map de c++ para llevar la información.

/*
Autor: Rodrigo Burgos Dominguez
Problem: 11691 - Allergy Test
Algoritm: Programacion Dinamica
*/

# include "stdio.h"
# include "string.h"
# include "algorithm"
# include "map"

using namespace std;

typedef struct { int values[8]; } DATA;

bool operator < ( DATA A, DATA B ){
  int x;
  for( x = 0; x < 8; x++) if( A.values[x] != B.values[x]) return A.values[x] < B.values[x];
  return 0; 
}

map< DATA, int > din[8];
map< DATA, int > vis[8];

int solve( int sizePrevius, DATA currentState){
  int res = (1<<30), x, cnt = 0, y;
  DATA next;
  if( vis[ sizePrevius][currentState] == 1)
     return din[sizePrevius][currentState];  
  vis[ sizePrevius][currentState] = 1;
  for( x = 0; x < 8; x++) if( currentState.values[x] > 0 ){
   cnt++;
   for( y = 0; y <= sizePrevius; y++) if( x - y > 0){
     next = currentState;
     next.values[x]--,
     res = min( res, solve( (x - y) - 1 , next) + sizePrevius + 1);
   }
  }
  if(cnt == 0 ) res = sizePrevius;
  return din[sizePrevius][currentState] = res;
}

main(){
  int ncases, cases, x, n, val;
  DATA empty;
  memset( empty.values, 0, sizeof( empty.values ));
  for( scanf("%d", &ncases), cases = 1; cases <= ncases; cases++){
     for( x = 0; x < 7; x++){
      map< DATA, int > visEmpty;
      vis[x] = visEmpty;
     }
     scanf("%d", &n);
     DATA ini = empty;
     for( x = 0; x < n; x++){
      scanf("%d", &val);
      ini.values[ val ]++;
     }
     printf("%d\n", solve( 0 , ini ));
  }
  return 0; 
}

Cualquier duda o sugerencia contactarme a rodrigo.burgos@gmail.com

jueves, 19 de julio de 2012

UVA Online Judge 12125 - March of the Penguin

UVA Online Judge 12125 - March of the Penguins


http://uva.onlinejudge.org/external/121/12125.html
Es un problema clasico de Flujos, en este problema para cada pedazo de hielo es representado por dos nodos, el primero nodo seria el nodo en el que pueden llegar los pinguinos, todas las aristas que llegan a estos nodos, son de capacidad infinita, el segundo nodo son todas las pinguinos que pueden salir, aqui la capacidad tambien es infinita, el truco para evitar que mas de los pinguinos especificados puedan salir del pedazo de hielo es crear una arista entre estos dos nodos que lo representan, con capacidad igual a la que se proporciona en la entrada, al final solo hay que gener un nodo inicial y crear aristas con la capacidad que se especifica en la entrada (esta capacidad es la cantidad de pinguinos que se encuentran en cada pedazo de hielo al inicio ), se ejecuta el algoritmo de flujo maximo poniendo como nodo final cada uno de los nodos incidentes ( Nodos que solo reciben las aristas), y de esta manera si el flujo maximo es igual al total de pinguinos entonces ese nodo es un posible nodo final de reunion de todos los pinguinos.
Para este problema especifico en vez de utilizar una busqueda en amplitud para el flujo utilzo una busqueda en profundidad.
Les dejo el código:

# include "stdio.h"
# include "string.h"


typedef struct { double x, y; int numPenguins, mtime; } PENGUINS;

PENGUINS peng[102];
int graph[204][204], fnet[204][204], vis[204];

double distPenguins( PENGUINS A, PENGUINS B ){
   return (A.x - B.x)*(A.x - B.x) + (A.y - B.y)*(A.y - B.y); 
}

int min( int a, int b ){ return a < b ? a : b; }

int busquedaEnProfundidad(int currentNode, int destiny, int n, int flow ){
   int r, x;
   if( currentNode == destiny ) return flow;
   if( vis[currentNode] == 1 ) return 0;
   vis[currentNode] = 1;
   for( x = 0; x < n; x++) 
     if( graph[currentNode][x] - fnet[currentNode][x] > 0 ){
      r = busquedaEnProfundidad( x, destiny, n, min(flow, graph[currentNode][x] - fnet[currentNode][x]) );
      if( r > 0 ){
          fnet[currentNode][x] += r;
          fnet[x][currentNode] -= r;
          return r;
      }
     } 
    return 0;
}

int fordFulkerson(int inicio, int destino, int n) {
  memset( fnet, 0, sizeof( fnet ));
  int currentFlow, flow = 0;
  do{
    memset( vis, 0, sizeof( vis ));
    currentFlow = busquedaEnProfundidad( inicio, destino, n, (1<<22));
    flow += currentFlow;
  }while( currentFlow > 0 );
  return flow;
}

main(){
  int cases, ncases, x, y, ini, sumAllPenguins, n, r, cont;
  double dist;
  for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
    scanf("%d %lf", &n, &dist);
    sumAllPenguins = 0;
    for( x = 0; x < n; x++){
      scanf("%lf %lf %d %d", &peng[ x ].x, &peng[ x ].y, &peng[ x ].numPenguins, &peng[x].mtime );
      sumAllPenguins += peng[x].numPenguins;
    }
    memset( graph, 0, sizeof( graph ));
    for( x = 0; x < n; x++)
    for( y = 0; y < n; y++)
      if( x != y && distPenguins( peng[x], peng[y]) <= dist*dist ){
        graph[x*2+1][y*2] = (1<<22);
      }
    for( x = 0; x < n; x++){
       graph[x*2][x*2 + 1] = peng[x].mtime; 
    }
    ini = n*2;
    for( x = 0; x < n; x++)
      graph[ini][ x*2 ] = peng[x].numPenguins;
    cont = 0;
    for( x = 0; x < n; x++){
      r = fordFulkerson( ini, x*2, n * 2 + 3);
      if( r == sumAllPenguins){
       if(cont > 0 ) printf(" ");
       printf("%d", x);
       cont++;
      }
    }
    if( cont == 0 ) printf("-1");
    printf("\n");
  }
  return 0; 
}
Cualquier duda o sugerencia contactarme a rodrigo.burgos@gmail.com

martes, 22 de mayo de 2012

Problema B: Adding New Machine (ACM Dalian Regional 2011)


Problema B: Adding New Machine

Les comparto un problema con su explicación del concurso de Dalian en China.

Descripción

  Increíble loca Compañía progresista ( ICPC por sus siglas en ingles), sufre demasiado por su lenta producción. Después de una investigación, ellos encontraron que el embotellamiento estaba en el Absulutely Crowded Manufactory (ACM). Para acelerar el procedimiento, ellos compraron otra maquina para el ACM. Pero un nuevo problema apareció, ¿como poner esta nueva maquina en el ACM?.

   ACM es un complejo rectangular, que esta dividido en W*H celdas. Existen N viejas maquinas rectangulares,  y la nueva maquina no puede ocupar ninguna celda donde existan maquinas viejas. La nueva maquina necesita M celdas consecutivas. Celdas consecutivas significan una línea de celdas adyacentes. Tu tarea es calcular el numero de formas diferentes en las que se pueden colocar la nueva maquina.

Entrada

   Hay múltiples casos de prueba ( no mas de 50). La primera línea de cada caso de prueba contiene 4 enteros W, H, N , M ( 1 <= W, H  <= 10^7 , 0 <= N <= 50000, 1 <= M <= 1000), indicando el ancho y el largo de el ACM , el numero de maquinas viejas  y el tamaño de la nueva maquina. Las siguientes N líneas, cada una contiene 4 enteros Xi1, Yi1 , Xi2 y Yi2 ( 1 <= Xi1 <= Xi2 <= W, 1 <= Yi1 <= Yi2 <= H), indicando las coordenadas de la i-e sima maquina vieja. Se garantiza que no hay celdas ocupadas por dos maquinas viejas.

Salida

Imprimir el numero de formas de colocar la nueva maquina en el ACM.

Entrada Ejemplo
Salida Ejemplo
3 3 1 2
2 2 2 2
3 3 1 3
2 2 2 2
2 3 2 2
1 1 1 1
2 3 2 3
8
4
3




Solución:


 La primera solución que se nos presenta a simple vista es colocar en todas las posiciones vacías la nueva maquina, y contar cuantas veces se puede colocar esta maquina, el único problema es que W y H son muy grandes, y el costo de hacer esto es W*H*M ( 10^17 ), por lo tanto no es una solución viable,  pero de esta solución podemos sacar algunos conclusiones que nos pueden ser útiles, por ejemplo cuando exploramos todas las posibilidades solo existen dos maneras de colocar una maquina iniciando en una posiciones (fila, columna), una es colocándola horizontalmente y la otra es verticalmente.

Para resolver un problema complicado primero hay que irnos a lo particular, y de ahí movernos a lo general y es por eso que vamos a resolverlo parte por parte de este problema.

Primero supongamos que solo es una línea sin obstáculos, si la línea es de tamaño H y la longitud de la maquina es M, el numero de formas que podemos colocar M es H – M + 1 , siempre y cuando M sea menor a H.

Si todas las celdas de la matriz estuvieran libres de obstáculos entonces podríamos contar  con facilidad de cuantas maneras podemos colocar esta nueva maquina en toda la matriz.  Suponiendo que la colocamos de manera vertical, podemos calcular cada columna en 10^7 operaciones ( bueno pero como todos es lo mismo podría ser con tan solo una multiplicación para todas las columnas), para en este caso nos conviene realizar columna por columna, en el caso de las filas cuando la maquina se coloca horizontalmente también se puede contar fila por fila, en a lo mas 10^7 operaciones.

Esto es para el caso en que toda están vacías, con una sola resta funciona, pero ¿que pasa cuando existen maquina ya colocadas y cuando son 50000 de ellas?. Para ese caso debemos primero observar un ejemplo, vean la imagen siguiente:







Como pueden ver, ningún rectángulo se empalma, si nosotros vamos de izquierda a derecha, por cada columna vemos que en el a primera columna no hay nada que nos limite, nosotros calculamos cuantas maquinas nuevas podemos colocar en esta columna con una simple resta, pero en la segunda existe dos rectángulos, cuando inician los rectángulos nosotros debemos calcular exactamente los intervalos vacíos para calcular el numero de maquinas a colocar, existen dos intervalos de 1 y 2, como nuestras maquina es de tamaño 2 , entonces podemos colocar  0 y 1 maquinas nuevas, si nosotros nos movemos a la tercera columna el numero de maquina que vamos a colocar es la misma que en la segunda, ya que no hay ningún rectángulo que termine o inicie, pero en la cuarta columna nos encontramos que uno de los rectángulos se termina, y hay que calcular de nuevo la cantidad de maquinas a colocar. En este caso quedaría un intervalo de 5, la cantidad de maquinas que debemos colocar en esta columna es de 4.

  ¿Que es lo que podemos rescatar de esta parte?
  Nosotros podemos ver que solamente hay que calcular las posiciones donde exista un cambio, donde se agregue un nuevo rectángulo o donde se termine uno, en total el máximo numero de posiciones donde pudiera ocurrir es esto son 100,000 ( ya que hay 50,000 rectángulos  por dos ya que es donde inicia un rectángulo y donde termina).

¿Pero como podemos calcular cada columna el numero de nuevas maquina que debemos colocar? La respuesta es utilizar una estructura de datos para contarlas.

¿Qué estructura de datos utilizaríamos para contar los segmentos unidos y restara M a cada uno de ellos?

Un Árbol de Intervalos nos serviría para nuestros propósitos,(Véase el capítulo de estructura de datos avanzadas), el Árbol de Intervalos nos puede ayudar al conteo de estos segmentos, ya que para cada nodo podemos guardar:

1 – numero de maquinas que podemos contar sin contar la de los extremos.
2 – numero de posiciones no marcadas pegadas a la izquierda .
3 – numero de posiciones no marcadas a la derecha.

Supongamos que tenemos una maquina de tamaño 1x2, este es el tamaño de la maquina que queremos insertar, la siguiente figura muestra una fila vacía, sin ningún rectángulo en ella.


Si nosotros queremos insertar una maquina que va de la columna 2 a la columna 6 y otra maquina de la 8 a la 10 quedaría de  esta manera.

En nuestro árbol de intervalos, quedaría de la siguiente manera:




Cado nodo padre puede sacar la información de sus hijos, por ejemplo en el nodo que tiene la información del segmento [1, 8] , puede calcularlo con sus dos hijos, el [1,4] y el [5,8], para calcular la información se sigue los siguientes pasos.

·       Cuadros izquierdos : Son los cuadros izquierdos del hijo izquierdo.
·       Cuadros derechos: Son los cuadros derechos del hijo derecho.
·       Numero de maquinas:  La suma del numero de maquinas de los dos hijos mas la suma de los  cuadros derechos del hijo izquierdo y los cuadros izquierdo del hijo derecho menos M ( M es el tamaño de la nueva maquina), si el resultado es negativo entonces colocar 0.

¿Que pasa cuando uno de los dos hijos nodos esta completamente lleno?

En ese caso el calculo es distinto, el hijo que tiene todos los cuadros llenos, no tiene un lado izquierdo o derecho con cuadros , si no todo el segmento esta completo y tanto el lado izquierdo como derecho son los mismos cuadros.

Para el caso especifico del nodo que representa el segmento [1,4] del ejemplo anterior, que se muestra en la siguiente figura:


Se calcula de la siguiente manera

·       Cuadros izquierdos:  cuadros izquierdos del hijo izquierdo.
·       Cuadros derechos: la suma de los cuadros del hijo derecho mas los cuados derecho del hijo izquierdo.
·       Numero de maquinas: El numero de maquinas del lado izquierdo.

Como pueden ver se tiene que validar si esta completo alguno de sus hijos o si los dos están llenos, en el caso de que alguno este vacío aplica los mismo que en el primer escenario.

¿Pero por que es tan rápido un árbol de intervalos en este problema?

Cuando agregamos un nuevo cuadrado al árbol, iniciamos de la raíz el nodo que representa a todo el intervalo [1,N],  y nos movemos por sus hijos, ya en los hijos nos vamos recursivamente por todos las ramas del árbol hasta el final. Con las siguiente condiciones:


1.     Si el nodo donde estamos su intervalo ya no esta dentro del que queremos hacer una modificación , no seguimos exploras.
2.     Si el nodo donde estamos su intervalo queda absorbido por el intervalo donde vamos a modificar entonces solo modificamos ese nodo, y dejamos una bandera ahí, diciendo que todos los cuadros de este segmento o están usados o están libres, y ya no seguimos con los demás.
3.     Si no pasa ninguna de las anteriores, entramos a los hijos del nodo actual y realizamos el paso 1 y 2.

Y como pueden ver no se explora todo el árbol en cada modificación si no solo una parte de el, que seria dos veces el largo de las ramas y dependiendo del la longitud del segmento seria la longitud de la rama igual a  log( longitud del segmento ).

Para saber después de nuestras inserciones y eliminaciones cuantas maquinas caben en la fila o columna procesando, seria de la siguiente manera:

El numero de maquinas es igual a el numero de maquinas de la raíz mas max( 0,  los cuadros del lado izquierdo – M) + max( 0, los cuadros del lado derecho – M ) , donde M es el tamaño de la maquina.


Nuestra bandera seria un nuevo elemento del árbol.

Cuadro de texto: La complejidad de este algoritmo es la siguiente  O( N  x log max( W, H) ).




Nota: Uno debe notar que cuando M es 1 solo hay que explorándolo vertical o horizontalmente, ya que su rotación vertical u horizontal es la misma, y solo contaríamos el doble.

Código

# include <stdio.h>
# include <string.h>

#define MAXRECTANGLES 50002

int W, H, N, M, nbreakp, memtree;

typedef struct { int X[2], Y[2];} RECTANGLE;
typedef struct { int izq, der, countL, countR, count, delete, fill; } INTERVALTREE;
typedef struct { int coorden, position, accion; } BREAKPOINT;

INTERVALTREE MEM[ MAXRECTANGLES * 30 ];
RECTANGLE R[MAXRECTANGLES + 1];
BREAKPOINT BP[ (MAXRECTANGLES + 1) * 2];

int comparebp( BREAKPOINT *A, BREAKPOINT *B ){
  if(A->coorden != B->coorden ) return A->coorden - B->coorden;
  return B->accion - A->accion;
}

int min(int a, int b ){ return a < b ? a : b; }
int max(int a, int b ){ return a > b ? a : b; }

INTERVALTREE getNode(int punter, int A, int B){
  INTERVALTREE tmp;
  tmp.countL = 0;
  tmp.countR = 0;
  tmp.count = 0;
  tmp.fill = 0;
  tmp.delete = 0;
  if( punter != -1 && MEM[punter].delete == 0 ) return MEM[ punter ];
  if( punter == -1 || MEM[punter].delete == 2 ){
    tmp.countL = B - A + 1;
    tmp.fill = 1;
  }
  return tmp;
}

void insert( int *punter, int A, int B, int a, int b, int type){
  int med = (A + B ) / 2;
  INTERVALTREE left, rigth;
  if( B < a || b < A ) return;
  if(*punter == -1 ){
     *punter = memtree++;
     MEM[*punter].izq = -1;
     MEM[*punter].der = -1;
     MEM[*punter].count = 0;
     MEM[*punter].countR = 0;
     MEM[*punter].fill = 1;
     MEM[*punter].countL = ( B - A + 1);
     MEM[*punter ].delete = 0;
  }else
     if( MEM[*punter ].delete >= 1){
       if( MEM[*punter].izq != -1) MEM[MEM[*punter].izq].delete = MEM[*punter ].delete;
       if( MEM[*punter].der != -1) MEM[MEM[*punter].der].delete = MEM[*punter ].delete;
       MEM[*punter ].delete = 0;
     }
  if( a <= A && B <= b ){
     MEM[*punter].countL = (  type == 0 ? 0 : B - A + 1);        
     MEM[*punter].fill = type;  
     MEM[*punter].countR = 0;
     MEM[*punter].count = 0;
     if( MEM[*punter].izq != -1) MEM[MEM[*punter].izq].delete = 1 + type;
             if( MEM[*punter].der != -1) MEM[MEM[*punter].der].delete = 1 + type;
     return;
  }
  insert(&MEM[*punter].izq, A, med, a, b, type);
  insert(&MEM[*punter].der, med+1, B, a, b, type);
  /* Calcular */
  left = getNode(MEM[*punter].izq , A, med);
  rigth = getNode(MEM[*punter].der, med +1 , B );
  if( left.fill == 1 && rigth.fill == 1 ){
    MEM[*punter].fill = 1;
    MEM[*punter].countL = B - A + 1;
            MEM[*punter].countR = 0;     
            MEM[*punter].count = 0;
  }else if( left.fill == 1 ){
       MEM[ *punter].fill = 0;
       MEM[*punter].countL = left.countL + rigth.countL;
       MEM[*punter].countR = rigth.countR;
       MEM[*punter].count= rigth.count;
  }else if( rigth.fill == 1 ){
       MEM[ *punter].fill = 0;
       MEM[*punter].countR = left.countR + rigth.countL;
       MEM[*punter].countL = left.countL;
       MEM[*punter].count= left.count;
  }else{
         MEM[*punter].fill = 0;
                 MEM[*punter].countL = left.countL;
                 MEM[*punter].countR = rigth.countR;
                 MEM[*punter].count = left.count+ rigth.count+
                                       max( 0, left.countR + rigth.countL - M + 1) ;
  }
}

int count( int punter, int A, int B){
  if( punter == -1 ) return ( B - A + 1 ) - M + 1;
  if( MEM[punter].delete == 2 ) return ( B - A + 1 ) - M + 1;
  if( MEM[punter].delete == 1 ) return 0;
  return MEM[punter].count + max( 0 , MEM[punter].countL - M + 1) + max( 0, MEM[punter].countR - M + 1);     
}

long long process( int axis , int width, int length){
   int lastpos = 1, cpos, indice = -1, A, B, pos;
   long long currentCont, response = 0;
   memtree = 0;
   for( pos = 0; pos < nbreakp; pos++){
             if( lastpos != BP[pos].coorden ){
       currentCont = (long long)count( indice, 1, length);
       response += currentCont * (long long)( BP[ pos ].coorden - lastpos);
             }
             cpos = BP[ pos ].coorden;
             A = ( axis == 0 ) ? R[ BP[ pos ].position ].Y[ 0 ] : R[ BP[ pos ].position ].X[ 0 ];
             B = ( axis == 0 ) ? R[ BP[ pos ].position ].Y[ 1 ] : R[ BP[ pos ].position ].X[ 1 ];
             insert( &indice , 1, length, A, B, BP[ pos ].accion );
             lastpos = cpos;
   }
   currentCont = (long long)count( indice, 1, length);
   response += currentCont * (long long)( width - lastpos + 1);
  
   return response;
}

main(){
  int rec, nc;
  long long cont;
  while( scanf("%d %d %d %d", &W, &H, &N, &M) != EOF ){
    for( rec = 0; rec < N; rec++)
       scanf("%d %d %d %d", &R[ rec ].X[0], &R[ rec ].Y[0], &R[ rec ].X[1], &R[ rec ].Y[1]);
    for( nbreakp = rec = 0; rec < N; rec++){
       for(nc = 0; nc < 2; nc++){
         BP[ nbreakp  ].position = rec;
         BP[ nbreakp  ].accion = nc;
         BP[ nbreakp++].coorden = R[rec].X[ nc ] + nc;
       }
    }
    qsort(BP, nbreakp, sizeof( BREAKPOINT ), comparebp );
    cont = process( 0, W , H);
    for( nbreakp = rec = 0; rec < N; rec++){
       for(nc = 0; nc < 2; nc++){
         BP[ nbreakp  ].position = rec;
         BP[ nbreakp  ].accion = nc;
         BP[ nbreakp++].coorden = R[rec].Y[ nc ] + nc;
       }
    }
    qsort(BP, nbreakp, sizeof( BREAKPOINT ), comparebp );
    if( M > 1 )
      cont += process( 1, H, W);
    printf("%lld\n", cont);
  }
  return 0;       
}




Cualquier duda o sugerencia escribirme a rodrigo.burgos@gmail.com















Factors in Bin-packing instances

ACM Mexico Centro America y el Caribe 2004, Factors in Bin-packing instances


http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1100
Estaba recordando el regional cuando pasamos en primer lugar en una competencia donde al final del concurso teníamos 3 problemas y en el que estábamos peleándonos por tres mas pos-concurso, al final acabamos con 5 problema y pasamos al mundial.
Ese concurso fue inolvidable, como la BUAP gano con 5 problemas y también otro equipo de la BUAP intento con éxito hackear el PCS^2, al final los descubrieron pero fue épico, ya que en la lista del regional aparecía la BUAP en primer lugar con los alfalfas y en ultimo lugar con los BUAPandrosos.
Y es por ello que volví a ver los problemas del concurso y hay uno que no leí y que tampoco resolvimos por un solo caso de prueba, nos comentaron después los jueces, prácticamente el problema es dada un numero div = [n*f + .99999 ] que se calcula de multiplicar dos variables que te dan en el problema, hacer que una lista dada tenga exactamente el numero div de elementos que sean divisores de una variable C (dada en la entrada) .
Entonces para resolver el problema es ver cuantos números ya dividen a C, y ver si necesitamos mas divisores o menos, también nos pide el problema que sea el menor numero de unidades que se tengan que restar o sumar a los números.
Ya que sabemos si el numero de divisores es menor o mayor al valor esperado ( div ), entonces para cada numero en la lista calculamos el costo de transformarlo a un divisor o bien a un no divisor si queremos incrementar o decrementar los divisores.
Ordenamos por costo, y al final con un for vamos marcando el numero de divisores que nos sobran o nos hacen falta para que se impriman con el cambio, siempre de menor a mayor, si el costo es 0, entonces no podemos usar esos números por que ya son o divisores o no divisores.
Les dejo el código:

# include "stdio.h"
# include "string.h"

typedef struct { int value, nextValue, cost, position, changed; } TYPE;

TYPE types[1000000];

int solution[100000];

int min( int a, int b ){ return a < b ? a : b; }

int compare( TYPE *a, TYPE *b){
  if( a->cost != b->cost) return a->cost - b->cost;
  return a->position - b->position;
}

main(){
  int n, c, contDivisors;
  int expectedValue, x, c1, c2, r;
  double value;
  while( scanf("%lf", &value ) != EOF ){
     scanf(" %d , %d", &n, &c);
     expectedValue = (int)(value * (double)n + (double)0.9999999999999);
     contDivisors = 0;
     for(x = 0; x < n; x++){
       scanf("%d", &types[ x ].value);
       contDivisors += (types[x].value != 0 && (c % types[x].value) == 0) ? 1 : 0;
     }
     for(x = 0; x < n; x++){
       types[x].position = x;
       if( contDivisors <= expectedValue ){
        /* UP */
        c1 = c2 = 0;
        for( r = types[x].value ; r <= c; r++ ){
         if( r != 0 &&  (c % r) == 0 ) break;
         c1++;
        }
        /* DOWN */
        for( r = types[x].value ; ; r-- ){
         if( r != 0 && (c % r) == 0 ) break;
         c2--;
        }
        types[x].cost = min( c1, -c2);
        if( -c2 < c1 ) types[x].nextValue = types[x].value + c2;
        else types[x].nextValue = types[x].value + c1;
        types[x].changed = 0;
       }else{
        /* UP */
        c1 = c2 = 0;
        for( r = types[x].value ; r <= c; r++ ){
         if( r == 0 && (c % r) != 0 ) break;
         c1++;
        }
        if( r > c ) c1 = (1<<28);
        /* DOWN */
        for( r = types[x].value ; ; r-- ){
         if(r == 0 && (c % r) != 0 ) break;
         c2--;
        }
        types[x].cost = min( c1, -c2);
        if( -c2 < c1 ) types[x].nextValue = types[x].value + c2;
        else types[x].nextValue = types[x].value + c1;
        types[x].changed = 0;
       }
     }
     qsort( types, n, sizeof( TYPE ), compare );
     for( x = 0; x < n && contDivisors != expectedValue ; x++){
      if( types[x].cost == 0 ) continue;
      contDivisors += ( contDivisors > expectedValue ) ? -1 : 1;
      types[x].changed = 1;
     }
     for( x = 0; x < n; x++){
       solution[types[x].position ] = ( types[x].changed ) ? types[x].nextValue : types[x].value;  
     }
     printf("%d, %d\n", n, c);
     for( x = 0; x < n; x++){
      printf("%d\n", solution[ x ]);
     }
  }
  return 0; 
}
Cualquier duda o sugerencia contactarme a rodrigo.burgos@gmail.com

sábado, 24 de marzo de 2012

10358 Matrix ( MINIMAX )

http://uva.onlinejudge.org/external/103/10358.html Estaba revisando este problema y recordando cuando intente resolverlo hace ya mas de 8 años no tenia ni idea de como resolver un problema de este tipo, cuando aprendi a resolverlos con la tecnica de minimax, me tope con que como podia hacer un minimax sobre este problema si puede haber ciclos, ya que el minimax se resuelve con una dinamica y una dinamica para poder resolver el problema no debe tener ciclos, ahora que lo vuelvo a leer, es obvio que cuando se hacen mas de 32 movimientos entonces ya no lo pueden atrapar y por tanto se envia el mensaje "You are trapped in the Matrix.", y para evitar los ciclos enviamos en la dinamica el nivel, este nivel es el numero de pasos, si es par entonces se mueve neo en otro caso se mueven los agentes, los agentes tratan de minimizar y neo trata de maximizar. Al final si el valor que regresa la dinamica es 0 , indica que no lo pueden atrapar pero tampoco pudo escapar, si es -1 entonces lo atraparon, y si es 1 puede escapar. aqui les dejo el codigo.
/* Autor: Rodrigo Burgos Dominguez */

# include 
# include 

char map[10][10];

int dx[5]={0, 1, -1, 0, 0};
int dy[5]={0, 0, 0, 1, -1};

int din[40][8][8][8][8][8][8];
int vis[40][8][8][8][8][8][8], cases;

int max(int a, int b ){ return a > b ? a : b; }
int min(int a, int b ){ return a < b ? a : b; }

void find( int a, int b, int *A,int *B, char ch ){
  int cont = 0;
  for( ; a < 8; a++, cont++)
  for(b = ( cont == 0 ) ? b : 0 ; b < 8 ; b++, cont++)
    if( map[a][b] == ch ){
      *A = a; 
      *B = b;
      return;
    }
}

int canWalk(int ax, int ay, int aX, int aY, int nx, int ny){
  if( ax < 0 || ay < 0 || nx < 0 || ny < 0 || aX < 0 || aY < 0 ) return 0;
  if( ax >= 8 || ay >= 8 || nx >= 8 || ny >= 8 || aX >= 8 || aY >= 8 ) return 0;
  if( map[ax][ay] == '#' || map[aX][aY] == '#' || map[nx][ny] == '#') return 0;
  return 1;
}

int solve( int level, int ax, int ay, int aX, int aY, int nx, int ny){
  int res, d1, d2;
  if( level >= 40 ) return 0;
  if( ax == nx && ay == ny ) return -1;
  if( aX == nx && aY == ny ) return -1;
  if( map[nx][ny] == 'P' ) return 1;
  
  if( vis[level][ax][ay][aX][aY][nx][ny] == cases) return din[level][ax][ay][aX][aY][nx][ny];
  vis[level][ax][ay][aX][aY][nx][ny] = cases;
  if( level % 2 == 0 ){ /* Move neo */
    res = -1;
    for(d1 = 0; d1 < 5; d1++) 
      if( canWalk( ax, ay, aX, aY, nx + dx[ d1 ], ny + dy[ d1 ])){
       res = max( res, solve(level + 1, ax, ay, aX, aY, nx + dx[ d1 ] , ny + dy[ d1 ]) );
      }
  }else{  /* move agents */
   res = 1;
   for( d1 = 0; d1 < 5; d1++)
   for( d2 = 0; d2 < 5; d2++)
     if( canWalk( ax + dx[d1], ay + dy[d1 ], aX + dx[d2], aY + dy[d2], nx, ny ) ){
       res = min( res, solve( level + 1, ax + dx[d1], ay + dy[d1 ], aX + dx[d2], aY + dy[d2], nx, ny) ) ;
     }
  }
  return din[level][ax][ay][aX][aY][nx][ny] = res;
}

main(){
  int ncases, ax,ay,aX,aY,nx,ny, x, r;
  for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
   for( x = 0; x < 8; x++) scanf("%s", map[ x ]);
   find( 0, 0 , &ax, &ay, 'A');
   find( ax, ay+1 , &aX, &aY, 'A');
   find( 0, 0 , &nx, &ny, 'M');
   r = solve(0, ax, ay, aX, aY, nx, ny);
   if( r == 0 ) printf("You are trapped in the Matrix.\n");
   else if( r < 0 ) printf("You are eliminated.\n");
   else printf("You can escape.\n");
  }
  return 0;
}
//

Cualquier duda o sugerencia pueden escribirme a rodrigo.burgos@gmail.com