OROFAND - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Author: Harshil Tagadiya
Tester: Riley Borgard
Editorialist: Aman Dwivedi

DIFFICULTY:

Simple

PREREQUISITES:

Bitwise Operations, Observation

PROBLEM:

You are given an array A with N integers. An array’s score is defined as the bitwise AND of all its elements. You need to find the bitwise OR of the scores of all possible non-empty subarrays of A.

You are also asked Q queries. Each query is consists of two integers X and V. You need to change the value of the element at index X to V. After each query, you again need to find the bitwise OR of the scores of all possible non-empty subarray.

EXPLANATION:

We are given an array A of N integers. The first observation that we can make is that for each query our answer is the Bitwise OR of all its elements. Let’s prove how:

Proof

Suppose we have an array A of N intgers as A_1, A_2,\dots,A_N. There can be two cases possible:

Case 1: The i^{th} bit of all the elements is unset i.e. 0.

Consider any non-empty subarray S whose score is X. The score is defined as the bitwise AND of all its elements. Now the i^{th} bit of X will be set only and only if all the elements of this subarray have their i^{th} bit set. As:

0 \And 1 = 0 \\ 1 \And 1 = 1

Since no elements had their i^{th} bet set. Hence there exists no subarray whose i^{th} will be set.

Now let’s try to find the Bitwise OR of the scores of all possible non-empty subarrays of A. Suppose the value is Y. Now the i^{th} bit of Y will be set if there exists at least one score whose i^{th} bit is set. As:

0 \hspace{0.1cm}|\hspace{0.1cm} 1 = 1

As we had already proved that there exists no subarray whose i^{th} will be set. Hence the i^{th} bit of our final answer i.e. will be unset.

This means when the i^{th} bit of all the elements of the given array is unset then the i^{th} bit of our answer will be unset.

Case 2: There exists at least one element whose i^{th} bit is set i.e. 1.

Now, there exists at least one subarray whose score X has i^{th} bit set i.e. the subarray which consists of single element whose i^{th} is set.

Now let’s try to find the Bitwise OR of the scores of all possible non-empty subarrays of A. Suppose the value is Y. Now the i^{th} bit of Y will be set as there exists at least one score X whose i^{th} bit is set.

This means when the i^{th} bit of at least one of the elements is set then the i^{th} bit of our answer will be set.

Now, we are left with finding the BItwise OR of the array A for each query. Since the value of N and Q are large hence, we won’t be able to find the BItwise OR by traversing the array for each query.

We will again use the property of Bitwise OR, i.e. if there exists at least one element whose i^{th} bit is set, then the i^{th} bit will be set in our answer too. Since the maximum number of bits possible are 31, we will first find the answer in binary form and finally convert that into an integer

To do so, for every bit i we will store the count of elements whose i^{th} bit is set. Now if the count of i^{th} bit is greater than 0 then we will set the i^{th} bit of our answer. Finally, find the answer in integer form and output it.

For each query, we will remove the contribution of the previous element present at index X and add the contribution of V. Finally, we repeat the above procedure to find the answer.

TIME COMPLEXITY:

O(N*log2(A_i)+Q*log2(A_i)) per test case

SOLUTIONS:

Setter
#include <bits/stdc++.h>
using namespace std;


void solve() {
    int n, q;
    cin >> n >> q;
    int a[n], bitsCount[32] = {};

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        for (int j = 0; j < 31; j++) {
            if ((a[i] >> j) & 1) {
                bitsCount[j]++;
            }
        }
    }

    int answer = 0;
    for (int j = 0; j < 31; j++)
        answer += (1 << j) * (bitsCount[j] >= 1);
    cout << answer << '\n';

    while (q--) {
        int index, value;
        cin >> index >> value;
        --index;

        // remove old value.
        for (int j = 0; j < 31; j++) {
            if ((a[index] >> j) & 1) {
                bitsCount[j]--;
            }
        }

        a[index] = value;

        // add new value.
        for (int j = 0; j < 31; j++) {
            if ((a[index] >> j) & 1) {
                bitsCount[j]++;
            }
        }

        answer = 0;
        for (int j = 0; j < 31; j++)
            answer += (1 << j) * (bitsCount[j] >= 1);
        cout << answer << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}


Tester

#include <bits/stdc++.h>

#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;

void solve() {
    int n, q;
    cin >> n >> q;
    vi a(n + 1);
    int ans = 0;
    vi cnt(31);
    auto del = [&](int val) {
        rep(i, 0, 31) {
            if(val >> i & 1) {
                cnt[i]--;
                if(cnt[i] == 0) ans ^= (1 << i);
            }
        }
    };
    auto add = [&](int val) {
        rep(i, 0, 31) {
            if(val >> i & 1) {
                if(cnt[i] == 0) ans ^= (1 << i);
                cnt[i]++;
            }
        }
    };
    rep(i, 1, n + 1) {
        cin >> a[i];
        add(a[i]);
    }
    cout << ans << '\n';
    while(q--) {
        int x, v;
        cin >> x >> v;
        del(a[x]);
        a[x] = v;
        add(a[x]);
        cout << ans << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int te;
    cin >> te;
    while(te--) solve();
}
Editorialist
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int mxN=35;
int two[mxN];

void pre()
{
  two[0]=1;

  for(int i=1;i<mxN;i++)
    two[i]=two[i-1]*2;
}

void solve()
{
  int n,q;
  cin>>n>>q;

  int a[n];

  int cnt[mxN]={};

  for(int i=0;i<n;i++)
  {
    cin>>a[i];
    int x=a[i];

    int ind=0;

    while(x)
    {
      if(x%2)
        cnt[ind]++;
      x/=2;
      ind++;
    }
  }

  int ans=0;

  for(int i=0;i<mxN;i++)
  {
    if(cnt[i]!=0)
      ans+=two[i];
  }

  cout<<ans<<"\n";

  while(q--)
  {
    int x,v;
    cin>>x>>v;
    x--;

    int temp=a[x];
    int ind=0;

    while(temp)
    {
      if(temp%2!=0)
        cnt[ind]--;
      temp/=2;
      ind++;
    }

    a[x]=v;
    temp=v;
    ind=0;

    while(temp)
    {
      if(temp%2!=0)
        cnt[ind]++;
      temp/=2;
      ind++;
    }

    ans=0;

    for(int i=0;i<mxN;i++)
    {
      if(cnt[i]!=0)
        ans+=two[i];
    }

    cout<<ans<<"\n";
  }
}

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  pre();

  int t;
  cin>>t;

  while(t--)
    solve();

return 0;
}

20 Likes

good editorial …nicely explained :slight_smile:

8 Likes

How to Solve it using Fenwick Tree.
Anyone?

answer will be OR of all elements of array. so for each query update array element (log n) and query the OR of all elements of array (log n).

Well I figured out the mistake. I was not updating the array after each query. As to your question, I am filling the bit_count table in a different (inefficient) way. (a[i] * 2) >> 1 will give you the LSB of a[i].

2 Likes

I did that too :stuck_out_tongue: , thank god i realised quicky but that ended up wasting my time :frowning:

1 Like

Can someone suggest sources to learn Bit Manipulation from scratch for CP?

5 Likes

This is I think will be a common mistake. I did the same.

“Since the value of N and Q are large hence, we won’t be able to find the BItwise OR by traversing the array for each query.”

then how my solution didn’t get TLE…
https://www.codechef.com/viewsolution/45192316

1 Like

Can someone tell me how " auto del = [&](int val){…} " this function works, i.e i’ve got the logic coded inside that i’m asking about the syntax of the function call and return. If someone can share the resources it would be better!

1 Like

This function is called lambda function, We can define this function inside main().

2 Likes

Those PrintWriter and FastReader are surely working Good.
Perhaps, The test cases does not really contain query of size (10^5).
Otherwise, It would have been (10^10) which is not computable within the given time constraint.

How can we say that the answer will be only the OR of all the elements? Since first we have to do the AND of all the sub-arrays and then we have to OR those results. How the AND of all the sub-arrays is contributing the result in answer? Please someone explain.

I did the same thing. still I got TLE

Since I am a beginner I have a doubt about the data type or data structure used in the following line of code

auto del = [&](int val) { rep(i, 0, 31) { if(val >> i & 1) { cnt[i]--; if(cnt[i] == 0) ans ^= (1 << i); } } };

What is auto keyword doing here and what does [&](int val) mean . Is it some new way of declaring a function or something else ?

Did you see the proof ? Let me know what you didn’t got from proof ??

Reread the editorial or watch the codechef video made on this problem.I think u will get it.

Bro, I got the editorial completely I was asking about the lambda function as I haven’t came across that before watching the editorial!

Brother can you tell me 10 15 very good questions on bits so that i can learn various good bit techniques we can come across in contests, from 2* to 5*!

can you please provide the code for the same??