hackersarkar12's blog

By hackersarkar12, history, 6 weeks ago, In English

Im unable to understand the solution logic of codeforces div2 664 problem c. http://codeforces.com/contest/1395/problem/C

 
 
 
 
  • Vote: I like it
  • +13
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by hackersarkar12 (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

this is the simplest code

include<bits/stdc++.h>

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; 

}

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it
Solution

Hope that will help you!

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone can help how this problem can be done by DP?