TOPCODER SRM 530 DIV 1

TOPCODER SRM 530 DIV 1

Ayer 19 de febrero se realizo el SRM 530, donde solo Vasyl[alphacom] pudo resolver todos los problemas.

Problema 250: GogoXCake

Para solucionar este problema habria uno que notar que como no se puede rotar el cortador entonces la unica forma que podemos comer el primero pedazo de pastel (En otras palabras el pedazo de pastel que tenga la fila mas pegada hacia arriba y si hay varias que tenga la columan mas pegada a la izquierda) y cumplir con lo que dice el problema, es colocar el cortador de igual manera en celda de uso que este en la fila 0 y columna mas a la izquierda ( en el problema indica que siempre en la primera fila va a existir por lo menos una celda que se debe usar), ya teniendo esto lo que hacemos es ver que las demas celdas del cortador qeu se tengan que usar tengan pastel, que ademas que el cortador no se salga del pastel, y cuando la celda se coma en el vector cake esa fila y columna tambien este vacia. Si realizamos ese procedimiento cada vez que encontremos un pedazo de pastel que no hemos comido y que deberiamos habernoslo comido ( y no encontramos ninguna inconsistencia antes mencionadas ) regresamos "YES", en otro caso regresamos "NO".

class GogoXCake {
public:
  string solve(vector , vector );
};
 
char O[100][100];
 
string GogoXCake::solve(vector  cake, vector  cutter) {
  int n = cake.size() , m = cake[ 0 ].size(), posy ;
  for( int x = 0; x < n; x++)
  for( int y = 0; y < m; y++)
    O[x][y] = 'X';
  
  for( int a = 0; a < n; a++){
      for(int b = 0; b < m; b++){
         if( cake[ a ][ b ] == '.' && O[a][b] != '.'  ){
             int x, y;
             for( x = 0; x < cutter[ 0 ].size() ;  x++) if( cutter[ 0 ][ x ] == '.' ) break;
             posy = ( b - x );
             if( posy < 0 ) return "NO";
             for( x = 0; x < cutter.size(); x++)
             for( y = 0; y < cutter[ 0 ].size() ; y++){
               if( cutter[ x ][ y ] == '.' ){
                 if( a + x >= n || posy + y >= m ) return "NO";
                 if( O[ a + x ][ posy + y ] == '.' || cake[a + x ][ posy + y ] == 'X' ) return "NO";
                 
                 O[ a + x ][ posy + y ] = '.';
               }
            }
         }
      }
  }
  return "YES";
}
//

Problema 500: GogoXMarisaKirisima

Este problema es un Greedy, primero hay que observar que para el primer paso que hay que dar es encontrar una solucion ( un camion del nodo 0 al nodo N - 1) si no existe por lo menos un camino entonces la respuesta es 0, en otro caso nosotros borramos de la matriz de adyacencia ( o marcamos como usados ) , las aristas de nuestro camino ( en el algoritmo marcamos en la matriz mat los usados ), tambien marcamos los nodos que ya estan en algun camino del nodo 0 al nodo N - 1. ( en el algoritmo marcamos los nodos usados en el arreglo mark )
El siguiente paso es darnos cuenta que si ya tenemos un camino de nodo 0 al nodo N - 1 entonces toda arista que salga de un nodo marcado a otro nodo marcado , indicaria que esta arista une una parte del camino de 0 a N - 1 con otra parte de ese mismo camino, o bien que conecta dos caminos distintos, en cualquiera de esos casos, podriamos encontrar una nueva forma de llegar de 0 a N - 1 con esa arista nueva, si eso pasa incrementamos el numero de formas ( cont++ ).
¿Que pasa cuando ya no encontramos aristas para agregar ? , bueno si no encontramos mas aristas que cumplan con eso, lo que tenemos que hacer es buscar otro camino del nodo 0 al nodo N - 1, sin usar las aristas ya utilizadas.

Nota: cuando busquemos un camino nuevo no necesariamente sale de 0 , si no de cualquiera de los nodos marcados ( aquellos que pertenecen a un camino ) y el destino no es N - 1, si no cualquier nodo que tambien pertenesca a un camino. ( la funcion F realiza esa funcion y verifica que por lo menos se agregue una arista nueva en la busqueda ).

class GogoXMarisaKirisima {
public:
  int solve(vector );
};
 
int mat[100][100];
vector  C;
int vis[100];
int mark[100];
int n;
 
int find( int nodo, int fin ){
  if( vis[ nodo ] == 1 ) {return 0 ; }
  vis[ nodo ] = 1;
  if( nodo == fin ){  mark[ nodo ] = 1; return 1;}
  for( int x = 0; x < n; x++)
    if( C[ nodo ][ x ] == 'Y' ){
      if( find(  x , fin ) ) {
        mat[nodo][x] = 1;
        mark[ nodo ] = 1;
        return 1;
      }
    }
    return 0;
}
 
int F( int a, int level ){
  if( vis[a] == 1) return 0;
  if( level > 0 )vis[ a ] = 1;
  if( level > 0 && mark[ a ] == 1 ) { mark[ a ] = 1; return 1; }
  for( int x = 0; x < n; x++ ){
     if(C[a][x] == 'Y' && mat[a][x] == 0  ){
        int r = F( x, level + 1);
        if( r > 0 ){
           mark[ a ] = 1;
           mat[a][x] = 1;
           return r + 1;
        }
     }
  }
  return 0;
}
 
int GogoXMarisaKirisima::solve(vector  choices) {
    int cont = 0;
     C = choices;
     n = choices.size();
     memset( mat, 0, sizeof( mat ));
     memset( vis, 0, sizeof( vis )); 
     memset( mark, 0,sizeof( mark ));
     if( find( 0 , n - 1 ) == 0 ) return 0;
 
     cont++;
     int ban = 1;
     for( ; ban == 1; ){
       ban = 0;
       for( int x = 0; x < n; x++)
       for( int y = 0; y < n; y++){
         if( C[x][y] == 'Y' && mat[x][y] == 0 ){
           if( mark[ x ] == 1 && mark[ y ] == 1 ){
             mat[x][y] = 1;
             cont++;
             ban = 1;
           }
         }
       }
       if( ban == 0 ){
       
         for( int x = 0; x < n; x++){ 
            if( mark[ x ] == 1  ) {
             memset( vis, 0, sizeof( vis ));
             if( F( x, 0 ) > 0 ){
              ban = 1;
              cont++;
              break;
             }
           }
         }
         
       }
     }
     return cont;
}
//

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