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:

3 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