11391 - Blobs in the Board

[RC's]

I want to ask about the third example
The initial position of the board should be like this

Code: Select all

..1
23.
...

with . is empty space on the board and numbers represent blobs

I wonder how the number of goals is 2.. I think the answer should be 1, that is 2 jumps over 3, so that the board will be

Code: Select all

..1
..2
...

and then after that, 1 jumps over 2..

Are there any other possibilities ??

[rio]

Code: Select all

..1
23.
...

...
2..
1..

1..
...
...

-----
Rio

[RC's]

sorry... it was my foolishness.. I think it can only move 4 directions..
thanks, rio..

[jvimal]

Will the naive 2**16 * 8 algorithm work? It gets TLEd for me

[Observer]

Make sure that your code do not do the calculations more than once.

[jvimal]

Make sure that your code do not do the calculations more than once.

Yeah, I made sure of that. But, it didnt strike me that the memoization could be done on [r][c][State]. Initially I had just done [State].

[RC's]

What is the output of this input :

Code: Select all

1
4 4 15
1 1
1 2
1 3
1 4
2 1
2 2 
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3

[tanaeem]

What is the output of this input :

Code: Select all

1
4 4 15
1 1
1 2
1 3
1 4
2 1
2 2 
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3

My ac code gives following output

Code: Select all

Case 1: 32090916

[Jehad Uddin]

i am getting tle please help

Code: Select all

code removed got acc after 16 submission  

[Farsan]

WA... used dp states as dp[no of jumps completed ][current board state ]

Code: Select all

ACED... could not determine the states correctly at first

[jddantes]

Why WA? Any more test cases?

Code: Select all

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long ul;
typedef bitset<16> bset;
typedef long long ll;

#define UNVISITED -1

int R, C, N;
int RC;

void toCoord(int index, int * i, int * j){
   *i = index/C;
   *j = index%C;
}

int toIndex(int i, int j){
   int ret = i*C + j;
   // if(ret >= RC){
   //    printf("RC is %d\n", RC);
   //    printf("%d %d is index %d\n", i,j,ret);
   //    printf("yolo\n");
   //    exit(0);
   // }
   return i*C + j;
}

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

ll arr[1<<16][4][4];

vector<vector<int>> grid, dummy_grid;

void fillGrid(bset bs){
   for(int index = 0; index<RC; index++){
      int i, j;
      toCoord(index, &i, &j);
      grid[i][j] = bs[index];
   }
}

bset get_bset(){
   bset bs;
   int index = 0;
   for(int i = 0; i<R; i++){
      for(int j = 0; j<C; j++){
         bs[index] = grid[i][j];
         index++;
      }
   }
   return bs;
}

void printBS(bset bs){
   for(int i = 0; i<R; i++){
      for(int j = 0; j<C; j++){
         cout << bs[toIndex(i,j)] << " ";
      }
      printf("\n");
   }
}
void printGrid(){
   for(int i = 0; i<R; i++){
      for(int j = 0; j<C; j++){
         printf("%d ", grid[i][j]);
      }
      printf("\n");
   }
}

ll f(bset bs){

   ul ulong = bs.to_ulong();
    
   
   int bits_set = bs.count();

   if(arr[ulong][R-1][C-1] != UNVISITED){
      // printf("Memoized. Returning %lld\n",  arr[ulong][R-1][C-1]);
      return arr[ulong][R-1][C-1];
   }

   if(bits_set == 1){
      // printf("1. Returning 1.\n");
      return arr[ulong][R-1][C-1] = 1;
   }

   bset dummy_bs = get_bset();
   fillGrid(bs);

   // printf("BS check:\n");
   // printBS(bs);
   // printf("Grid check:\n");
   // printGrid();
   // printf("=\n");

   ll ret = 0;

   for(int i = 0; i<R; i++){
      for(int j = 0; j<C; j++){
         if(grid[i][j]){

            for(int dir = 0; dir<8; dir++){
               int I = i + dy[dir];
               int J = j + dx[dir];
               if(I<0 || J<0 || I>=R || J>=C){
                  continue;
               }

               if(grid[I][J]){
                  int destI = I + dy[dir];
                  int destJ = J + dx[dir];

                  if(destI<0 || destJ<0 || destI>=R || destJ>=C){
                     continue;
                  }

                  if(grid[destI][destJ]){
                     continue;
                  }

                  // printf("Original is:\n");
                  // printGrid();
                  // printf("-\n");
                  // if(dir == 3 && i == 0 && j == 0){
                  //    printf("%d %d %d\n", grid[i][j],grid[I][J], grid[destI][destJ]);
                  // }
                  grid[i][j] = 0;
                  grid[I][J] = 0;
                  grid[destI][destJ] = 1;



                  bset new_bs = get_bset();

                  grid[i][j] = 1;
                  grid[I][J] = 1;
                  grid[destI][destJ] = 0;
                  
                  // printf("new bs check:\n");
                  // printBS(new_bs);
                  // printf("xxx\n");
                  // // printf("Jumping %d %d from dir %d\n",i,j, dir);
                  // printf("From %d %d dir %d skipping %d %d to %d %d\n", i,j, dir, I, J, destI, destJ);
                  ll this_ret = f(new_bs);
                  ret += this_ret;

               }

            }
         }
      }
   }

   // grid = dummy_grid;
   fillGrid(dummy_bs);
   // printf("Returning %lld\n", ret);
   // printf("Grid:\n");
   // printGrid();
   // printf("BS:\n");
   // printBS(bs);
   // printf("Shouldve been restored\n");
   return arr[ulong][R-1][C-1] = ret;
}

int main(){
   // bset x;
   // for(int y = 0; y<12; y++){
   //    x[y] = 1;
   // }
   // cout << x << endl;
   // cout << x.to_ulong() << endl;
   // return 0;
   // int limit = 1<<16;
   // for(int x = 0; x<limit; x++){
   //       arr[x] = UNVISITED;
   // }

   for(int r = 0; r<4; r++){
      for(int c = 0; c<4; c++){
         int limit = 1<<r*c;
         for(int i = 0; i<limit; i++){
            arr[i][r][c] = UNVISITED;
         }
      }
   }

   int cases;
   scanf("%d", &cases);


   for(int e = 0; e<cases; e++){
      bset bs;
      scanf("%d %d %d", &R, &C, &N);
     
      // printf("Scanned %d %d %d\n", R,C,RC);
      for(int x = 0; x<N; x++){
         int i, j;
         scanf("%d %d", &i, &j);
         i--;
         j--;
         int index = toIndex(i,j);
         bs[index] = 1;
         // printf("Setting index as %d\n", index);
      }

      int num_states = 1<<RC;
      
      grid.assign(R, vector<int>(C));
      // dummy_grid.assign(R, vector<int>(C));

      ll ret = f(bs);
      printf("Case %d: %lld\n", e+1, ret);

   }

   return 0;
}