Help required MYSARA MARCH COOKOFF

1

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
2

Please help :confused: :slight_smile:

3

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

4

when it will be zero?

5

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
6

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

7

7 8

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
9

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
10

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
11

okay now I get It thank you I missed this.

12

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
13

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
14

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[100] = {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[0] = 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.
            bit[i] = 0; Please help in figuring out.
        }
        a[0] = 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;
}
16

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
17

That is not true, for example

1
2
7 8

the array is sorted, but has no possible sequence A

18

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

19

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

1 Like
20

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

2 Likes
21

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 :slight_smile: