CAC3 - Editorial

editorial
,
1

PROBLEM LINK:

Practice Link
Aliens Vs Humans

Author: hellb0y_suru

PROBLEM:

Given a matrix n*m, which consist of some free cells and some cells being occupied by mines, an operation is defined as moving a mine from its current position denoted by ( x, y ) to either of the 4 adjacent neighbour cells. After that, we want to know the maximum number of free cells in our matrix, by applying the given operation on a mine at most once.

PREREQUISITES:

  • Dynamic Programming with bit-masking

DIFFICULTY:

MEDIUM

EXPLANATION:

Let us assume that n \leq m. (If this is not the case then we will rotate the matrix because n*m\leq 40)

Let dp[i][currMask][nextMask] be the minimum number of occupied cells in the first i-th columns with the restrictions that the i-th column is described by currMask and i+1-st column is described by nextMask (ones correspond to occupied cells and zeroes correspond to free cells). To make a transition from dp[i-1][-][currMask] we can iterate over all possible masks for the i-1-st column, check whether we can distribute mines in i th column knowing the nextMask for i+1-st and currMask for i-st column respectively and find the minimal value of dp[i-1][-][currMask] for all such masks.

So our final answer will be, minimum value of n*m - dp[m][-][0] , where ’ - ’ denotes all possible masks.

Time complexity : O( m*n* 2^{3*n} ) for each test case.

SOLUTION:

Setter's Solution in C++ 
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007 
#define oo 1000000000000000000
#define forr(i,n) for(int i=0;i<n;i++)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define FF first
#define SS second
#define mem(a,v) memset(a,v,sizeof(a))
#define pb push_back
#define popcount(x) __builtin_popcount(x)

using namespace std;

vector<vector<int>> v;

bool valid(const int &last,const int &cur,const int &next,const int &n,const int &j){
   forr(i,n){
       if(!((1<<i)&cur) && v[i][j]){
           bool f = 0;
           if( i && ((1<<(i-1))&cur) ) f = 1;
           else if( i+1<n && ((1<<(i+1))&cur) ) f = 1;
           else if((1<<i)&last)  f = 1;
           else if((1<<i)&next) f = 1;
           if(!f) return false;
       }
   }
   return true;
}

void __sol(){
   int n,m; cin >> n >> m;
   vector<vector<int>> temp(n,vector<int>(m+1,0));
   forr(i,n) forr(j,m) cin >> temp[i][j+1];
   if(n>m){
       v.assign(m,vector<int>(n+1,0));
       forr(i,n) forr(j,m) v[j][i+1] = temp[i][j+1];
       swap(n,m);
   }
   else v = temp;
   int dp[m+2][1<<n][1<<n];
   forr(i,m+2) forr(j,1<<n) forr(k,1<<n) dp[i][j][k] = INT_MAX/1000;
   for(int i=1;i<=m;i++){
       forr(pm,1<<n){
           forr(nm,1<<n){
               forr(lm,1<<n){
                   if(i==1 && valid(0,pm,nm,n,i)) dp[i][pm][nm] = min( dp[i][pm][nm], popcount(pm) );
                   else if(i==m && valid(lm,pm,0,n,i)) dp[i][pm][0] = min(dp[i][pm][0], popcount(pm) + dp[i-1][lm][pm] );
                   else if(i!=1 && i!=m && valid(lm,pm,nm,n,i)) dp[i][pm][nm] = min(dp[i][pm][nm] , popcount(pm) + dp[i-1][lm][pm]);
               }
           }
       }
   }
   int ans = INT_MAX/1000;
   forr(i,1<<n) ans = min(ans,dp[m][i][0]);
   cout << n*m - ans <<"\n";
   return;
}


int main(){    
   fastio;
   int tc=1; cin >> tc;
   while(tc--) __sol();
   return 0;
}