ANDNOR - Editorial

editorial
1

PROBLEM LINK:

Contest

Setter: a0n0k0i0t
Tester: a0n0k0i0t
Editorialist: a0n0k0i0t

PROBLEM

An operation ANDOR on an array B is defined as the value obtained by performing alternate bitwise OR and bitwise AND in the array in left precedence.
Formally for an array B having size M,
X= B_1 | B_2 \& B_3 | B_4 \& B_5 … B_M (In left precedence)
where | is Bitwise OR operator and \& is the bitwise AND operator and
X is the output of the ANDOR operation.
Eg: B=[4,1,3,6]
ANDOR(B) = 4|1\&3|6
\hspace{3cm}= 5\&3|6
\hspace{3cm}= 1|6
\hspace{3cm}= 7
You are given an array A of size N. Find the number of distinct values obtained by doing ANDOR operation on all possible subarrays of A

A subarray A_{i,j} where \leq i\leq j \leq N is a sequence of integers A_i,A_{i+1}, ... A_j.

DIFFICULTY:

Easy

PREREQUISITES:

Array & Bitwise operations

EXPLANATION:

Sub Task 1:

Generate all possible subarrays of A and do ANDOR operation on each subarray.
Count all distinct integers found.

Time complexity : O(N^3) for each test case.

Sub Task 2:

  • Let res1(i) be a set having all distinct values of ANDOR operation of all subarrays ending at i^{th} position and having size odd.
    res1(i)= (ANDOR(A_{j,i}) : 1\leq j \leq i and i-j+1 is odd )
  • Let res2(i) be a set having all distinct values of ANDOR operation of all subarrays ending at i^{th} position and having size even.
    res2(i) = (ANDOR(A_{j,i}) : 1\leq j \leq i and i-j+1 is even )
  • res1(i)=res2(i-1)\&A[i]
  • res2(i)=res1(i-1)|A[i]
  • Since A[i]\leq 10^3 , res1(i) and res2(i) can be replaced by two array pre1 and pre2 such that at the i^{th} iteration pre1 and pre2 can be calcuated as:
    for 0\leq j < 2^{10}

    • pre1[j]=1 \hspace{1cm} (j \in res1(i))
      pre1[j]=0 \hspace{1cm} (otherwise)

    • pre2[j]=1 \hspace{1cm} (j \in res2(i))
      pre2[j]=0 \hspace{1cm} (otherwise)

  • pre1 and pre2 can be updated for each i=1 to N at each itearation in O(2^{10})

Pseudocode:

int pre1[1024]; pre2[1024]; arr[1024];

for int i = 1 to n{
        cur1[1024];cur2[1024];
        for int j = 0 to 1023 {
            if(pre1[i]==1){cur2[j|a[i]]=1; arr[j|a[i]]=1;}
            if(pre2[i]==1){cur1[j&a[i]]=1; arr[j&a[i]]=1;}
        }
        cur1[a[i]]=1;
        arr[a[i]]=1;
        pre1=cur1; pre2=cur2;
    }
    ans=0;
    for int j = 1 to (1<<10)-1)
         if(arr[j])
         ans++;
    print(ans)

Time complexity : O(N*2^{10}) for each test case

SOLUTION

 #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a,b,c) for (int(a) = (b); (a) < (c); (a)++)
#define ff first
#define ss second
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pl> vpl;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef double ld;
const int mod = 1e9+7;


void solve(vl &a,ll n){
    vvl s1(2,vl((1<<10)));
    vl ans(1<<10);
    for(int i=0;i<n;i++){
        vvl s3(2,vl(1<<10));
        rep(j,0,(1<<10)){
            if(s1[0][j]==1){s3[1][j|a[i]]=1;ans[j|a[i]]=1;}
            if(s1[1][j]==1){s3[0][j&a[i]]=1;ans[j&a[i]]=1;}
        }
        s3[0][a[i]]=1;
        ans[a[i]]=1;
        s1=s3;
    }
    ll an=0;
    rep(i,0,1<<10)if(ans[i])an++;
    cout<<an<<"\n";
    return;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.precision(15);
    ll T;
    cin >> T;
    for(int _=0;_<T;_++) {
        ll n,q,k,m,u,v,w,x;
        cin>>n;
        vl a(n);
        rep(i,0,n)cin>>a[i];
        solve(a,n);
    }
    return 0;
}