### hackersarkar12's blog

By hackersarkar12, history, 6 weeks ago, Im unable to understand the solution logic of codeforces div2 664 problem c. http://codeforces.com/contest/1395/problem/C  Comments (7)
 » Auto comment: topic has been updated by hackersarkar12 (previous revision, new revision, compare).
 » Brute force the solution since 2^9 = 512. Test every a & b with each of these numbers to see if they match with the number, and pick the smallest of these numbers.
 » 6 weeks ago, # | ← Rev. 3 →   The way I did this, is, let's find a condition to see if we can check if answer X works. For answer X to work, this means that for each value a[i] & b[j] we choose, we know that (a[i] & b[j]) | X == X (the bits of a[i]&b[j] have to be a subset of the bits of X). So from this, for each i from 0..n-1 we can just check if there exists a b[j] such that this condition is true, that (a[i] & b[j]) | X == X, and if all of the numbers 0..n-1 have a b[j] that works, this means answer X works. We can then just brute force the answer from 1...512 The bound is 512 since worst case all numbers can have a 1 in every position of their binary representation, and since each a_i < 2^9 this means a[i] = 1 + 2 + 4 + ... + 2^8 = 2 ^ 9-1, so our bound is 2^9-1 to check if the answer exists
»

this is the simplest code

# define ll long long

using namespace std; int main(){ ios_base::sync_with_stdio(0); cin.tie(0);

int n, m;
cin >> n >> m;

vector<int> a(n), b(m), c(n);
for(auto & x: a) cin >> x;
for(auto & x: b) cin >> x;

int ans = (1<< 9) - 1;

for(int  i = ans; i >= 0; --i){

int count = 0;
for(int j = 0; j < n; ++j){

for(int k = 0; k < m; ++k){

if(((a[j] and b[k])or i ) == i){
count++;
break;
}
}
}

if(count == n){
ans = i;
}
}

cout << ans << endl;


}

 » SolutionLet us take this as an example: $n = 4 , m = 2$$a = [2 , 6 , 4 , 0]$$b = [2, 4]$ let us build all possible $&$ using two for loops. Build & table for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ c[i][j] = (a[i] & b[j]) } } this will create a 2D $4 \times 2$ table: $\begin{pmatrix}2 & 0\\\ 2 & 4\\\ 0 & 4\\\ 0 & 0 \end{pmatrix}$Now let us rephrase the problem, you need to pick exactly $1$ element from each row and make the operation $or$ between them. Find the minimum $or$ value. Here where the dp comes in. since the constraints are low, the problem is doable using DP. where the states of the dp are: curRow, curCol, curOrValue Full Solutionint n , m ; vector a , b; vector > g ; int dp ; int dfs(int x, int y, int cur){ if ( y == m ) { return INF ; } if ( x == n ){ return cur ; } if ( dp[x][y][cur] != -1 ) return dp[x][y][cur] ; int choice1 = dfs(x, y + 1, cur) ; int choice2 = dfs(x + 1, 0, g[x][y] | cur) ; return dp[x][y][cur] = min(choice1, choice2) ; } signed main(){ fastio cin >> n >> m; memset(dp, -1, sizeof dp) ; g = vector >(n, vector(m)) ; a = vector(n) ; b = vector(m) ; for(int i = 0; i < n; i++){ cin >> a[i] ; } for(int i = 0; i < m; i++){ cin >> b[i] ; } for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ g[i][j] = (a[i] & b[j]) ; } } int ans = dfs(0, 0, 0) ; cout << ans << endl; return 0; } Hope that will help you!
 » Anyone can help how this problem can be done by DP?
•  » »