MYSARA - Editorial

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author: Hasin Rayhan Dewan Dhruboo
Tester: Raja Vardhan Reddy
Editorialist: William Lin

DIFFICULTY:

Easy

PREREQUISITES:

Bits, Basic Combinatorics

PROBLEM:

You are given an array B which represents the bitwise-ors of the prefixes of A. Find the number of possible A.

QUICK EXPLANATION:

If there exists an i such that the set bits in B_i is not a subset of the set bits in B_{i+1}, then the answer is 0. Otherwise, let x be the total number of set bits in all elements of B except for the last element. The answer is 2^x.

EXPLANATION:

Notice that B_{i+1}=B_i \bigvee A_{i+1} (we get a prefix of i+1 by adding element i+1 to the prefix of i). If some bit is set in B_i, then it must also be set in B_{i+1} because bits in x can’t be unset by taking the bitwise-or of x and some other value y. So the first thing we check is that the bits which are set in B_i are a subset of the bits which are set in B_{i+1} for all valid i, and if this condition is not true for some i, the answer is 0.

Code for checking subset

x is a subset of y is equivalent to the condition (x&y)==x (this is a well-known bit trick).

Assume that B_0=0 (this makes sense since the empty prefix should have a bitwise-or value equal to the identity of the operation bitwise-or, which is 0).

For all valid i, we need to make sure that B_{i+1}=B_i \bigvee A_{i+1}. Let’s split the bits into three types:

  1. The bit is not set in both B_i and B_{i+1}.
  2. The bit is not set in B_i but it is set in B_{i+1}.
  3. The bit is set in both B_i and B_{i+1}.

Note that there isn’t a fourth case, otherwise the set bits of B_i would not be a subset of the set bits of B_{i+1}.

For a bit of type 1, the bit in A_{i+1} can only be 0. If it is 1, the bit would be 1 in B_{i+1}.

For a bit of type 2, the bit in A_{i+1} can only be 1. If it is 0, the bit would be 0 in B_{i+1}.

For a bit of type 3, the bit in A_{i+1} can be anything.

Let x be the total number of bits of type 3 over all pairs (B_i, B_{i+1}). Since we have 2 choices for each bit, the answer will be 2^x. It remains to find x.

We can find x simply by iterating over each pair (B_i, B_{i+1}) and counting the bits of type 3. However, there is a more elegant solution.

A bit p will appear in B_i for all i in the range [l, N]. The total count of bits in this range is N-l+1. However, only the bits in range [l+1, N] will be of type 3, so we need to subtract 1 for each bit p. Summing up over each bit p, x is the total count of bits in all elements of B subtracted by the number of bits p which ever appear in the elements of B. If a bit appears in B, it must also appear in the last element of B, so the number of bits p which ever appear in the elements of B is equivalent to the number of bits in the last element of B. Thus, x is the total number of bits in B except for the last element.

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 9;
const int mod = 1e9 + 7; 
 
inline int mul(int a, int b) {return (a * 1LL * b) % mod;}
 
int ara[maxn];
 
int bigMod(int n, int k)
{
    if(k == 0) return 1;
    int val = bigMod(n, k / 2);
    val = mul(val, val);
    if(k&1) val = mul(val, n);
    return val;
}
 
int main()
{
    int t, cs = 1;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        int ans = 1;
        scanf("%d", &ara[1]);
        for(int i = 2; i <= n; i++){
            scanf("%d", &ara[i]);
            if((ara[i] & ara[i - 1]) != ara[i - 1]) ans = mul(ans, 0);
            else ans = mul(ans, bigMod(2, __builtin_popcount(ara[i - 1])));
        }
        printf("%d\n", ans);
    }
 
    return 0;
}
Tester's Solution
//raja1999
 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
 
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string> 
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
 
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll
 
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
 
 
//std::ios::sync_with_stdio(false);
 
int b[51234],c[51234][33];
main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t;
	cin>>t;
//	t=1;
	while(t--){
		int n,i,cnt,ans,j,fl=0;
		cin>>n;
		rep(i,n){
			cin>>b[i];
			rep(j,31){
				c[i][j]=0;
				if(b[i]&(1<<j)){
					c[i][j]=1;
				}
			}
		}
		ans=1;
		f(i,1,n){
			cnt=0;
			rep(j,31){
				if(c[i][j]==1&&c[i-1][j]==1){
					cnt++;
				}
				if(c[i-1][j]==1&&c[i][j]==0){
					fl=1;
				}
			}
			ans*=(1<<cnt);
			ans%=mod;
		}
		if(fl){
			cout<<0<<endl;
		}
		else{
			cout<<ans<<endl;
		}
	}
	return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

const int mxN=5e4, M=1e9+7;
int n, b[mxN];

void solve() {
	//input
	cin >> n;
	for(int i=0; i<n; ++i)
		cin >> b[i];

	//check that b[i] is subset of b[i+1]
	for(int i=0; i+1<n; ++i) {
		if((b[i]&b[i+1])!=b[i]) {
			cout << "0\n";
			return;
		}
	}

	//find x
	int x=0;
	for(int i=0; i<n-1; ++i)
		x+=__builtin_popcount(b[i]);
	//2^x
	int ans=1;
	for(int i=0; i<x; ++i)
		ans=ans*2%M;
	cout << ans << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	while(t--)
		solve();
}

Please give me suggestions if anything is unclear so that I can improve. Thanks :slight_smile:

7 Likes

Well I have no idea what’s wrong with the last paragraph. It would be helpful for you to be more specific.

HI
Am having a lot of trouble finding why my code isnt passing,
https://www.codechef.com/viewsolution/30718428

Please help me . It would hardly take a min.
Thanks in advance.

can you please check my solution, it’s giving WA

https://www.codechef.com/viewsolution/30754705

i’m trying to make O(1) space solution

The problem is-
cout<<0<<endl;
return 0;
you should not return 0 here as there may be other queries.

can anyone help me?
i m getting WA.
https://www.codechef.com/viewsolution/30799634

Heyy Coder’s.
I am getting WA each time. I don’t know what is the issue.
Please have a look on my code.

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

#define ll long long

unsigned int countSetBits(unsigned int n)
{
unsigned int count = 0;
while (n) {
count += n & 1;
n >>= 1;
}
return count;
}

int main() {
// your code goes here
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
ll int b[n];
for(int i=0;i<n;i++)
cin>>b[i];
ll int cnt=0,flag=0;
for(int i=1;i<n;i++)
{
if((b[i-1]&b[i])!=b[i-1])
{
flag=1;
break;
}
cnt+=countSetBits(b[i-1]);
}
if(flag==1)
cout<<“0\n”;
else
cout<<fmod(pow(2,cnt),(pow(10,9)+7))<<"\n";
}
return 0;
}

There is some issue with the test cases of this problem. Even the codes given in the editorial are not passing.

Can someone help me why is my code not passing?Hardly it will take a minute.Please help.

#include <bits/stdc++.h>
using namespace std;
const int inf = 10e9+7;
void solve(){
int n;
cin>>n;
int b[n];
for(int i=0;i<n;i++){
cin>>b[i];
}
int p = 1;
for(int i=0;i<n-1;i++){
if((b[i]&b[i+1])!=b[i]){
cout<<0;
return;
}
}
for(int i=0;i<n-1;i++){
int k = __builtin_popcount(b[i]);
for(int j =0;j<k;j++){
p=p*2%inf;
}
}
cout<<p;

}

int main() {
int t;
cin>>t;
while(t–){
solve();
cout<<endl;
}
return 0;
}

https://www.codechef.com/submit/MYSARA
can someone check why is my code not getting ac.

I have modified your code slightly.

  1. I have used fast exponentiation instead of the built in pow() function. The fast exponentiation works in O(log n) time and also takes care of overflows. You can google for more details.

  2. I have removed the fmod() and printed the answer directly.

    #include
    #include <bits/stdc++.h>
    #define mod 1000000007
    using namespace std;

    #define ll long long

    unsigned int countSetBits(unsigned int n)
    {
    unsigned int count = 0;
    while (n) {
    count += n & 1;
    n >>= 1;
    }
    return count;
    }

    //Fast Exponentation

    ll power(ll a,int p){

    if(p==0) return 1;
    if(p==1) return a;
    
    ll ans = power(a,p/2);
    
    ans*=ans;
    ans%=mod;
    
    if(p%2!=0)
        ans*=a;
    
    return ans%mod;
    

    }

    int main() {
    // your code goes here
    int t;
    cin>>t;
    while(t–)
    {
    int n;
    cin>>n;
    ll int b[n];
    for(int i=0;i<n;i++)
    cin>>b[i];
    ll int cnt=0,flag=0;
    for(int i=1;i<n;i++)
    {
    if((b[i-1]&b[i])!=b[i-1])
    {
    flag=1;
    break;
    }
    cnt+=countSetBits(b[i-1]);
    }
    if(flag==1)
    cout<<0<<endl;
    else
    cout<<power(2,cnt)<<"\n";
    }
    return 0;
    }

Hope this helps!

#include<bits/stdc++.h>
#include<vector>
#include<algorithm>
#include<set>
#include<queue>
#include<map>
#include<stack>
#include<sstream>
#include<string>
#define si(x) scanf("%d",&x);
#define ff first
#define ss second
#define vi vector<int>
#define vll vector<ll>
#define ll long long int
const ll MOD = 1e9 + 7; 
#define ld long double
#define llu unsigned long long int
#define pb(x) push_back(x)
#define all(x) x.begin(),x.end()
#define tezz ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define f(i,n) for(int i=0;i<n;i++)
#define f1(i,j,n) for(int i=j;i<n;i++)
const ll INF = 2e18;
#define pll pair<ll,ll>
#define MAX 100000
using namespace std;//fuck copying and ratings 
vi binary(ll n){
	vi v(32);
	while(n){
		int val=n%2;
		v.pb(val);
		n/=2;
	}
	reverse(all(v));
	return v;
}
int main(){   
    tezz;
	int t=1;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		int flag=1;
		vector<vector<int>> v;
		int arr[n];f(i,n)cin>>arr[i];
		f(i,n){
			v.pb(binary(arr[i]));	
		}
		int cnt=0,sum=1;
		f1(i,1,n){
			cnt=0;
			f(j,31){
				if(v[i-1][j]==1 && v[i][j]==0){
					flag=-1;
				}
				if((v[i-1][j]==1) && v[i][j]==1){
					cnt+=1;
				}
			}
			sum*=(1<<cnt);
			sum%=MOD;
		}
		if(flag==-1)
			cout<<0<<endl;
		else 
			cout<<sum<<endl;
	}
    return 0;
}

I pretty much used similar approach as tester, but unable to figure out where I am getting wrong, if anyone can please let me know, thanks in advanced.