MYSARA Solution Explained

editorial
2

I think there might be a mistake.
Say, what’s the answer for this test case?

1
2
7 8
1 Like
3

hi @udit5656 firstly thanks for sharing your approach
but i think for solution to exist
one condition is mission from your solution

//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;
}
}

// CodeChef: Practical coding for everyone tmwilliamlin
@everule1

1 Like
5

Just Look at My Solution.It simple and Fast

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

typedef long long ll;
#define endl “\n”

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

ll t = 1;
cin >> t;
while (t--)
{
    ll n;
    cin>>n;
    vector<ll> v(n);
    for(auto &x:v)cin>>x;
    ll ans=1;
    ll mod=1000000007;
    for(int i=1;i<n;i++){
        ll pro=1;
        bool ok=0;
        for(int j=0;j<32;j++){
            if((v[i]&(1<<j)) && (v[i-1]&(1<<j))){
                pro*=2;
            }
            if(!(v[i]&(1<<j)) && (v[i-1]&(1<<j)))ok=1;
        }
        if(ok)ans=0;
        ans=(ans*pro)%mod;
    }
    cout<<ans<<endl;
}
return 0;

}

6

You seriously need to format your code !

8

Can you give an example of a possible sequence A?
Which is equivalent to finding x such that
7|x =8 where | denotes bitwise or.

10

It’s not. The question very clearly states

Note that it is not guaranteed that the given sequence B was generated from some sequence A.

11

Okay I was again wrong. That’s why my answers were wrong in both questions. Here is my solution CodeChef: Practical coding for everyone. You just need to check two conditions then to make a valid sequence.

12

If a[i]&a[i-1]== a[i-1] then a[i-1] is lesser than equal to a[i]. Therefore you don’t need to check both conditions.

1 Like
13

Sorry, Actually when I was writing this post ,codechef website was not opening that’s why I was not able to give link to my formated code link in post.

14

I have mentioned at last that given array should be sorted. If given array is not sorted then answer will be zero.

15

Try

1
2
7 8

The array is sorted, but the answer is nonetheless 0.

16

Here x has only one value i.e. 8

17

Sorry you are right ,here answer will be 0. Thanks for pointing it out.

18

What is the bitwise or of 7 and 8?
7 is 0111 and 8 is 1000

19

Thanks @ketan_mehta . Due to missing of this condition my code was giving wrong answer on array{7,8} which was pointed out by @everule1.

1 Like
20 
Can someone help me finding an error in this?

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

inline int mul(int x, int y){
	return (x * 1ll* y)%mod;
}

inline int bitcount( int a){
	int count =0;
	while(a){
		if(a&1) count++;
		a>>=1;
	}
	return count;
}

inline int binpow(int x, int y){
	int z=1;
	while(y){
		if(y&1) z=mul(z,x);
		x=mul(x,x);
		y>>=1;
	}
	return z;
}
int main(){

	int t; cin>>t;

	for(int i=0; i<t; i++){
		int n; cin>>n;
		int a; int b;
		cin>>a;
		int ansbit=0;
			
		bool check=1;
		for (int i=1; i<n; i++){
			cin>>b;
			if(check){
				if((a&b)!=a) {
					check=0;
					break;
				}
				ansbit+=bitcount(a);
				a=b;
			}

		}

		if(check)
			cout<<binpow(2,ansbit)<<endl;
		else cout<<0<<endl;
	}

}
21

Write cin.ignore(); before the break. If you break early, you haven’t inputted some values which you’ll input in the next test case erraneously.
cin.ignore(); takes the reader to the next line.

Also instead of bitcount(a) you can use __builtin_popcount(a) which is up to 14% faster than your implementation.

22

I think you counting extra bits. You should count bits of ( a & b) . But you are counting bit of a.

23

Thanks a lot @everule1

24

My approach was B[0] =A[0]. We know that B[i] = B[i-1] V A[i]. If B[i-1][j]==0 then A[i][j]=b[i][j] and we have no option. If B[i-1][j]==1 then B[i][j]=1 no whatter the value of A[i][j]. Hence we have two options. using product rule we can say that A[i] can have 2^(number of set b its in B[i-1]). The only case where the array will not be defined will be if B[i-1][j]==1 and B[i][j]==0, since that is not possible using or operation. In that case output 0. else output product of number of possible A[i] for each i from 1 to n. But I am getting wrong answer, below is my code, can someone please tell me the error in my logic/code. Help will be appreciated!

#include<iostream>

#include<vector>

#include<algorithm>

#include<bitset>

using namespace std;

#define ll long long int

ll MOD = 1000000007;

long long int fast_exp(long long int base, long long int exp) {

    long long int res = 1;

    while(exp>0) {

       if(exp&1) {

           res = (res*base)%MOD;

       }

       base = (base*base)%MOD;

       exp = exp>>1;

    }

    return res%MOD;

}

int main(){

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    ll t;

    cin>>t;

    while(t--){

        ll n, temp;

        cin>>n;

        vector<bitset<32>> b(n);

        for(ll i=0; i<n; i++){

            cin>>temp;

            b[i] = temp;

        }

        ll count = 1;

        bool flag = true;

        for(ll i=1; i<n; i++){

            count = (count*fast_exp(2, b[i-1].count()))%MOD;

            if((b[i-1]&(~b[i]))!=0) {

                cout<<0<<'\n';

                flag = false;

                continue;

            }

        }

        if(flag) cout<<count<<"\n";

    }

    return 0;

}