Блог пользователя elements

The smallest subset with maximum bitwise OR.
Автор elements, история, 5 лет назад, По-английски

Can someone help me with this problem.

Given an array A of N numbers. We are required to find the size of the smallest subset of the array such that Bitwise OR is maximum possible.

$$$1 \leq N \leq 10^5$$$

$$$1 \leq A[i] \leq 10^6$$$

Sample input:
5
1 2 3 4 5


Sample output:
2
  • Проголосовать: нравится
  • +20
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Post the link to the original problem.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I couldn't find any. This was one of the questions asked for Round 1 of HackwithInfy conducted by Infosys.

    → Ответить
»
5 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

This has been asked before here.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Oh sorry. I didn't find it. Thank you.

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      This problem has A[i]<=10^6. So, I think its possible to solve it in A[i]log(A[i])^2. We can create polynomial where exponent is equal to value and coefficient is equal to one if that value is present in the array and otherwise 0. Then, we perform or convolutions repeatedly until the element corresponding to maximum or has non-zero coefficient. It will take obviously <= log(A[i]) steps atmax and each step costs A[i]log(A[i]).
      Edit: Using binary lifting kind of thing you can achieve complexity O(A[i]log(A[i])log(log(A[i]))). Not sure if that would be much faster.

      → Ответить
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +13 Проголосовать: не нравится

        Whatever you said is quite above my level. I think I should leave this problem.

        → Ответить
        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +23 Проголосовать: не нравится

          Suppose input is: $$$A[] = {1,2,8,7}$$$

          max or is 15

          Consider Polynomial: $$$P$$$ = 0 $$$x^0$$$ + 1 $$$x^1$$$ + 1 $$$x^2$$$ + 0 $$$x^3$$$ ... 1 $$$x^7$$$ + 1 $$$x^8$$$ + 0 (Coefficient of $$$x^i$$$ is count of i in $$$A$$$)

          Define Multiplication Operation on Polynomials:

          $$$A[0..n] , B[0..n]$$$ and $$$C = A * B$$$

          where $$$C[z]$$$ = $$$\sum_{z = x|y} A[x] B[y]$$$

          (Coefficient of $$$x^i$$$ is count of $$$j,k$$$ such that $$$A[j]|B[k] = i$$$)

          Now back to Question, If $$$P$$$ is the polynomial defined above coefficient of $$$x^i$$$ in $$$P*P$$$ is the number of $$$j,k$$$ such that $$$A[j]|A[k] = i$$$ (you will get all possible ORs after taking two elements from P)

          similarly in $$$P*P*P$$$ coefficient of $$$x^i$$$ is number of $$$j,k,l$$$ such that $$$A[j]|A[k]|A[l] = i$$$

          you need to repeatedly multiply $$$P$$$ until coefficient of $$$P^{n}[max Or]$$$ is non zero then report index of {n}

          Ok, all this is fine but can we do this multiplication fast? Yes, we can!

          to learn more about this algorithm open this

          → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +16 Проголосовать: не нравится

        You can actually optimize that to O(A[i]log(A[i])). Using the transform for OR convolution you have something like a[i] = number of ways to get exact mask of i, transformed to A[i] = number of ways to get submasks of i, since the or of submasks of i are also submasks of i. You can convolute it using exponentiation then you can extract the a[maximum size of mask using or possible] in O(A[i]) using inclusion-exclusion, so you get O(A[i]log(A[i])) for the initial transformation and O(A[i]) for finding if that certain mask was possible to get * O(log(A[i])) being the maximum size of the set.

        → Ответить
»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

If you want to master binary search or segment tree then this is one of the best questions. Binary search on answer can be used.

What is the maximum OR?
 It is the OR of all the elements. Let it be MaxOR.
Maintain a segment tree to find bitwise OR for any given range.

Now do binary search with l=1 and r=N.
In each step, find if there exists any subarray that has OR=MaxOR by traversing through the array and using the segtree to compute OR of range (i,i+mid), where mid is the value of binary step.
→ Ответить
  • »
    »
    5 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    He's asking about subset and not subarray. Then why do we need segment tree? Sorry if i am missing something.

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      My bad. Extremely sorry, misread the question, unable to delete.

      → Ответить
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится

        It's okay. Don't be sorry. Your answer was helpful for me even though you answered a different question. Thanks.

        → Ответить
»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

This problem was also asked in Google Internship Online Coding Round.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I found this, but it is too simple to be correct. Can anyone verify?

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    It is incorrect. Take [12, 10, 5] for example, that algorithm will output 3 while the answer is 2.

    → Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If I remove the numbers whose mask is a subset of an already existing number. Would this be a correct solution.

For Example if we have A=[1,3,4,2] then here 1 is a submask of 3 so I remove it 2 is a submask of 4 Hence my final subset will be [4,3]

I would like to know if this solution is correct. Can anybody please help me here?

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Sorry for necroposting, but I had a similar idea; my idea is that as usual I find the maximum OR by finding the OR of all the elements of the array.

    And then I take the element with the maximum number of set bits and then at every iteration I remove those submasks from all the numbers in the array and keep on doing this till I hit the required maximum OR.

    So I wanted to ask if this approach is correct; can someone please confirm? If it is incorrect, please tell me a testcase where this approach would fail.

    Thanks in advance!

    → Ответить
  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I had the same idea too. Could you please let me know if you were able to find if this is a right approach or not?

    → Ответить
»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

ll n; cin >> n; vectorv(n); for(ll i=0;i<n;i++) cin >> v[i];

    ll orr=0;
for(ll i=0;i<n;i++) {(orr|=v[i]);}debug(orr)
    vector<ll>bt(32);

for(ll i=0;i<n;i++){
    for(ll j=0;j<31;j++){
       if((v[i]&(1<<j))==(1<<j)) bt[j]++;
    }
}
debug(bt)
ll ans=0;
for(ll i=0;i<n;i++){
    ll nm=0;
    for(ll j=0;j<31;j++){
       if((v[i]&(1<<j))==(1<<j)){
         bt[j]--;
         if(bt[j]>0) nm+=(1<<j);
       }
       else{
         if(bt[j]>0) nm+=(1<<j);
       }
    }
    if(nm!=orr){
       for(ll j=0;j<31;j++){
         if((v[i]&(1<<j))==(1<<j)){
          bt[j]++;
         }
       }
    }
    else ans++;
}   

cout << sz(v)-ans << "\n";
→ Ответить