Translate

viernes, 16 de diciembre de 2011

Ball Stacking ( Latino America 2011 ACM)


Ball Stacking



Introduccion


Este problema solo lo pudo resolver un equipo en la region de mexico.
El problema practicamente consiste en dado una piramide de numeros , uno puede escojer cualquiera de los numeros, pero cuando uno escoje alguno simpre debe escojer los dos que se encuentran arriba de el , para el caso de los elementos que se encuentran en las orillas, por ejemplo todos los que estan en la columna 0 solo tienen un numero superior y no dos.
Tu tarea es de que manera escojerias los numeros ( con la restriccion antes mencionada de que debes tomar los dos numero arriba de el, y si tomas estos numero los dos de arriba y asi sucesivamente) de tal forma que maximises la suma de los numero repetidos.

Solucion Lenta


Lo primero que se nos viene a la cabeza es que es Programacion Dinamica, pero como logro que se pueda hacer esta programacion dinamica, bueno para todo problema lo primero hay que hacer es dibujarlo y ver su forma, lo primero que ami se me ocurrio ( que si hubiera estado en el concurso eso me hubiera hecho perder como una hora del cocurso), es que note que que se forman triangulos, y para evitar recontar los triangulos de abajo, yo manejo la fila y el rango que puedo formar hacia abajo, (ROW, A, B) donde A B, es la base del triangulo que que esta libre, si empiezo de arriba hacia abajo, cuando uno selecciona una posicion C de este rango, nuevamente puedo formar dos triangos que no han sido selecionados (ROW, A, C - 1) y (ROW, C + 1, A ) , entonces si recorro esta C y guardo el mejor resultado para todas las C aue esten en el rango [ A, B], entonces puedo obtener la mejor forma de selecionar numeros culla base es la fila ROW en el rango A, B
La complejidad de este algoritmo es O( N x N x N x N ) que es aproximadamnte 10^12, lo cual no sale a tiempo, lo implemente y perdi mas de una hora por suponer que ya implementado veria alguna manera de reducirlo, a aqui el codigo:
/*Autor: Rodrigo Burgos Dominguez */
# include 
# include 

long long balls[1002][2002];
long long din[2][1002][2002];
long long scanning[1002][2002];
int n;

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

long long procesa( int row, int a, int b, int c ){
 long long res = scanning[ row ][ c ];
 int lrow, lcol, rrow, rcol, irow, icol;
 lrow = row - ( c - a + 1) ;
 lcol = a - 1;
 rrow = row - ( b - c + 1);
 rcol = c;
 irow = row - (b - a) - 2;
 icol = a - 1;
 if( lrow >= 0 && lcol >= 0 ) res -= scanning[ lrow ][ lcol ];
 if( rrow >= 0 && rcol >= 0 ) res -= scanning[ rrow ][ rcol ];
 if( irow >= 0 && icol >= 0 ) res += scanning[ irow ][ icol ];

 return res;
}

main(){
  int currentRow, column, row, a, b, c;
  while( scanf("%d", &n) != EOF && n ){
   for( row = 0; row < n; row++)
   for( column = 0; column <= row; column++) scanf("%lld", &balls[ row ][ column ]);
    memset( din, 0, sizeof( din ));
    memset( scanning, 0, sizeof( scanning ) );
    for( row = 0; row < n; row++)
    for( column = 0; column <= row; column++ ){
       scanning[ row ][ column ] = balls[ row ][ column ];
       if( row > 0 ){
         scanning[ row ][ column ] += scanning[ row - 1 ][ column ];
         if(column > 0 )
           scanning[ row ][ column ] += scanning[ row - 1 ][ column - 1];
         if( row > 1 && column > 0 ){
          scanning[ row ][ column ] -= scanning[ row - 2 ][ column - 1];
         }
       }
    } 
    din[ 0 ][ 0 ][ 0 ] = max( (long long)0 , (long long)balls[ 0 ][ 0 ] );
    for( row = 1; row < n; row++){
      currentRow = ( row % 2 );
      memset( din[ currentRow ], 0, sizeof( din[ currentRow ] ) );
      for( a = row; a >= 0 ; a--){
        for( b = a; b <= row; b++){
          if( b > 0 ) din[currentRow][a][b] = max( 0 , din[ (currentRow + 1) % 2][ a ][ b - 1] ) ;
          for( c = a; c <= b; c++){
           din[currentRow][a][ b ] = max( din[currentRow][a][ b ] ,
               ( ( c > 0 ) ? din[ currentRow ][a][ c - 1 ] : 0 ) + din[currentRow % 2][c + 1][ b ] + procesa( row, a, b, c )); 
          }
        }
      }
    }
    printf("%lld\n",din[(n - 1) % 2 ][ 0 ][ ( n - 1 ) ]);
  }
  return 0; 
}

Solucion Correcta ( no necesariamente unica ni la mejor)



Si me hubiera puesto a analizar que otros patrones encontraba, hubiera notado algo que me podria haber ayudado muchisimo para resolver el problema, si nosotro no dibujamos el triangulo si no que vamos haciendo los ejemplos con la entrada tal y como nos las dan, cada triangulo que formamos , se puede ver como una linea vertical que va desde el pico de la piramide ( ROW , COL ) y baja por toda esa columna hasta ROW = 0, para la columna anterior siempre es (ROW - 1 , COL - 1), bueno asi se va formando, de ahi viene la idea, que para que yo pueda forma una piramide cuyo pico es (ROW , COL ), entonces en la columna anterior por lo menos debo tener una piramide que tenga como pico ( ROW - 1, COL - 1), si yo tuviera una piramida en la columna anterior con pico mayor a ROW - 1, entonces quiere decir que esa piramide es mayor a la que estoy colocando en este momento, la idea es que la mejor forma de construir una piramide en con pico ( ROW , COL ) es igual a la suma de toda la columna desde ROW hasta 0 mas (+) el pico de mayor suma que se pudo generar en la columan anteriro que sea mayor a ( ROW - 1, COL - 1), si eso lo hacemos para todas las filas y columnas obtendremos el resolutado.

La complejidad del algoritmo hasta este punto es de O( N x N x N ) que ya es mucho menor 10^9, pero aun asi es costoso, si nosotros implementamos un interval tree o una tecnica para poder obtener el mejor valor de la columna anterior mayor a ( ROW - 1, COL - 1) en un tiempo log2 N, entonces la complejidad seria de O( N x N x LOG2 N ) , que seria aproximadamento 10^7 en el caso mas grande.

Eh aqui una implementacion


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

#define INFINITY (((long long)1)<<50)

typedef struct { int izq, der; long long maximo; } INTERVAL;

INTERVAL MEM[ 1000000 ];
int nmem;

long long best[ 1002 ], tmpbest[ 1002];
long long balls[ 1002 ][ 1002 ];

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

/*Crea un interval tree basado en lo que hay en el arreglo best*/
long long makeInterval( int *pt, int a, int b){
 int med; 
 if( a > b ) return -INFINITY;
 if( *pt == -1 ){
   *pt = nmem++;
   MEM[*pt].izq = -1; 
   MEM[*pt].der = -1; 
   MEM[*pt].maximo = 0; 
 }
    if( a == b ){
      return MEM[*pt].maximo = best[ a ];
    }
    med = (a + b) / 2;
    MEM[*pt].maximo = max( makeInterval( &MEM[*pt].izq, a, med ) , makeInterval( &MEM[*pt].der, med + 1, b ));
    return MEM[*pt].maximo;
}

/* del intreval tree creado se consulta el rango A, B, y se obtiene el elemento mas grande*/
long long getMax(int pt, int a, int b, int A, int B){
  int med = ( a + b ) / 2;
  if( pt == -1 || B < a || A > b ) return -INFINITY;
  if( A <= a && B >= b ) return MEM[pt].maximo;
  return max( getMax( MEM[pt].izq, a, med, A, B) , getMax(MEM[pt].der, med + 1, b, A, B ) );
}

main(){
  int row, col, n, indice;
  long long sum, sol;
  while( scanf("%d", &n) != EOF && n ){
   for( row = 0; row < n; row++){
    for( col = 0; col <= row; col++){ 
     scanf("%lld", &balls[ row ][ col ]);
    }
   }
   /* best contiene la mejor mander de ralizar la operacion en la correspondiente columna, 
      y la posicion de best[ row ]*/
   best[ 0 ] = 0;
   sol = 0;
   for( row = 0; row < n; row++){
     best[ row + 1 ] = balls[ row ][ 0 ] + best[ row ];
     sol = max( sol, best[ row + 1]);
   }
   for( col = 1; col < n; col++){
     sum =0;
     nmem = 0;
     indice = -1,
     makeInterval( &indice, col - 1, n);
     for( row = col; row <= n ;row++){
      tmpbest[ row ] = sum + getMax(indice, col - 1, n , row - 1 , n );
      sol = max( sol, tmpbest[ row ]);
      sum += balls[ row ][ col ];
     } 
     for( row = col; row <= n ; row++) best[ row ] = tmpbest[ row ];
   }
   printf("%lld\n", sol);
  }
  return 0; 
}

Una mejor solucion


Esta solucion es practicamente la misma que la de arriba, pero de igual manera por programar rapido y resolver que la mejor manera de sacar el mejor valor de un arreglo es con un interval tree, no considere que es estatico este arreglo y con un simple barrido del arreglo puedo saber cual es el mayor eh aqui el codigo, con complejidad O( N x N )
#include 
#include 

#define INFINITY (((long long)1)<<50)

typedef struct { int izq, der; long long maximo; } INTERVAL;

INTERVAL MEM[ 1000000 ];
int nmem;

long long best[ 1002 ], tmpbest[ 1002];
long long balls[ 1002 ][ 1002 ];

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

main(){
  int row, col, n;
  long long sum, sol;
  while( scanf("%d", &n) != EOF && n ){
   for( row = 0; row < n; row++){
    for( col = 0; col <= row; col++){ 
     scanf("%lld", &balls[ row ][ col ]);
    }
   }
   /* best contiene la mejor mander de ralizar la operacion en la correspondiente columna, 
      y la posicion de best[ row ]*/
   best[ 0 ] = 0;
   sol = 0;
   for( row = 0; row < n; row++){
     best[ row + 1 ] = balls[ row ][ 0 ] + best[ row ];
     sol = max( sol, best[ row + 1]);
   }
   for( col = 1; col < n; col++){
     sum =0;
     nmem = 0;
     
     for( row = n - 1; row >= 0 ; row--){
        best[ row ] = max(best[ row ], best[ row + 1]);
     }
     for( row = col; row <= n ;row++){
      tmpbest[ row ] = sum + best[ row - 1 ];
      sol = max( sol, tmpbest[ row ]);
      sum += balls[ row ][ col ];
     } 
     for( row = col; row <= n ; row++) best[ row ] = tmpbest[ row ];
   }
   printf("%lld\n", sol);
  }
  return 0; 
}

Conclusion


Para los concursos de programacion uno debe analizar, la mayoria de los problemas se puede resolver sencillamente, el truco es buscar la idea correcta, tomense su tiempo para encontrar la idea correcta y no implemntar cosas que puedan harcerlos perder el tiempo.


Saludos

No hay comentarios: