# Help required MYSARA MARCH COOKOFF

Obviously after the contest ends

I want to know if my code has a bug or the logic is totally wrong.
Here’s my code: CodeChef: Practical coding for everyone

1 Like

Please help  You haven’t handled the case when the answer will be 0.

when it will be zero?

When `seq[i-1]&seq[i]!=seq[i-1]`. Basically there is a set bit that is in the previous element and not in this element.

2 Likes

please give an example of such case where seq[i-1]&seq[i] !=seq[i-1]

7 8

If i is less than j and in the given sequence if there exists any bi greater than bj than answer will be zero.

1 Like

Here is some examples
2 4 5 13

or

4 5 2

convert into binary and try to build sequence A from it

1 Like

It’s not possible for any sequence A. That’s why the answer is 0. The bits can’t unset themselves when you bitwise or it with another number. The question states that a sequence A may not necessarily exist.

1 Like

okay now I get It thank you I missed this.

There are two mistakes in your code.

First:
In the question they mentioned

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

So, if B is not generated for sequence A your answer should be 0.
i.e. when any bit from previous number is 1 and it’s corresponding bit of current number is 0, you cannot make 1 as 0 with applying OR operation on it. In this case B is not generated from A.

Second:
There is a very good possibility of overflow in line number 18.
i.e. (ans * p) % mod should be ((long long)and * p) % mod

1 Like

A very weird thing happend today while the contest was open. I submit my code for this problem while the contest running but it said error in submission and said Something went wrong

1 Like

Hi.
Could someone point out why the test is TLEing for the commented section, thanks:

``````//https://www.codechef.com/COOK116A/problems/MYSARA
#include <bits/stdc++.h>
const long long MOD = 1e9 + 7;
using namespace std;
long long power = {0};

long long SetBit(long long num) {
long long ans = 0;
while(num) {
ans += (num & 1);
num >>= 1;
}
return ans;
}

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
power = 1;
for(long long i = 1; i < 50; i++) {
power[i] = 2 * power[i - 1];
power[i] %= MOD;
}
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
long long a[n + 1], bit[n + 1], ans = 1, temp = 0, f = 0;
/*for(int i = 1; i <= n; i++) {  The code is TLEing for this part only.
}
a = 0;*/
for(long long i = 1; i <= n; i++) {
cin >> a[i];
if(a[i] == (a[i] | temp)) {
temp |= a[i];
bit[i] = SetBit(a[i]);
}
else {
cout << 0 << endl;
f = 1;
break;
}
}
if(f)
continue;
for(long long i = 1; i < n; i++) {
long long x = power[bit[i]];
ans *= x;
ans %= MOD;
}
cout << ans << endl;
}
return 0;
}
``````

Probably use i as an int, long long comparisions and addition take double time. Also I think you could just do `int bit[n+1]={0}`

1 Like

That is not true, for example

``````1
2
7 8
``````

the array is sorted, but has no possible sequence `A`

It still doesn’t help, could you please suggest another way to it?

Use `__builtin_popcount(x)` to count set bits in x.

1 Like

My AC code gives 8 on this testcase.
Weak Testcases?

2 Likes

Thanks, I got an AC with it. If you could, please figure out the mistake in my code, with the TLE. It will help me in my implementation. Thanks 