BITPLAY - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: notsoloud
Tester: mridulahi
Editorialist: iceknight1093

DIFFICULTY:

1537

PREREQUISITES:

Basic combinatorics

PROBLEM:

You’re given a binary string S of length N.
Find the number of operation strings o such that S_{2i-1} \ o_i \ S_{2i} = S_{2i+1} for every i.
Each o_i must belong to \{\oplus, \mid, \& \}, i.e, be one of bitwise XOR/OR/AND.

EXPLANATION:

We know the string S already, which also includes the results of the operations.
So, elements of the operation string o are completely independent of each other: we can choose o_1, then o_2, then o_3, and so on separately; and multiply the choices for each of them.

This reduction simplifies the problem greatly, since we can deal with a single operation at a time.
That is, we’re given three bits b_1, b_2, b_3, and we want to count the number of bitwise operations op such that b_1 \ op \ b_2 = b_3.

With a bit of casework, this is not too hard:

  • If b_3 = 1, then:
    • If b_1 = b_2 = 0, then there’s no way to achieve this; the answer is 0.
    • If b_1 = 1 and b_2 = 0 (or vice versa), there are two choices: XOR and OR.
    • If b_1 = b_2 = 1, there are again two choices: OR and AND.
  • If b_3 = 0, then:
    • If b_1 = b_2 = 0, then any of the three operations will work.
    • If b_1 = 1 and b_2 = 0 (or vice versa), there’s only one choice: AND
    • If b_1 = b_2 = 1, there’s again only one choice: XOR

So, depending on the values of b_1, b_2, b_3, the answer gets multiplied by one of \{0, 1, 2, 3\}.
Perform all these multiplications, and print the final result modulo 10^9 + 7.
This takes \mathcal{O}(N) time.

TIME COMPLEXITY

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
mod = 10**9 + 7
for _ in range(int(input())):
    n = int(input())
    s = input()
    ans = 1
    for i in range(0, n-1, 2):
        result = s[i+2]
        a, b = s[i], s[i+1]
        if result == '1':
            if a == '0' and b == '0': ans = 0
            else: ans = ans * 2 % mod
        else:
            if a == '0' and b == '0': ans = ans * 3 % mod
    print(ans)
1 Like
2

Sorry I am a newbie. Please help.
while(t–){
long long int n;
cin>>n;
string s;
cin>>s;
long long int ans = 1;
for(long long int i = 2; i < n;i+= 2){
int num = s[i] -‘0’;
int prev = s[i-1] -‘0’;
int prevv = s[i-2] - ‘0’;
int acp = 0;
if(num == (prev ^ prevv)){
acp++;

        }
        if(num == (prev | prevv)){
            acp++;
           
        }if(num == (prev & prevv)){
            acp++;
        }
        ans = ans* acp;
        
    }
   
   cout<<ans%1000000007<<"\n";
        
    
}

why this was not accepted.
I am checking on every i+2 iteration and multiplying the ans with (0,1,2,3) instead of generalizing I am first checking every case then multiplying.

BY this approach 2 testcases passed, the third one was wrong.

3

It doesn’t look like you’re taking modulo correctly.
You need to do something like ans = (ans* acp) % mod; at each step, not just at the end - otherwise intermediate values will get extremely large and overflow.

1 Like
4

This is my code, can someone tell me why is this wrong?
`
include <stdio.h>
include <stdlib.h>

define MOD 1000000007;

void initIO();
void solve();
int possibilities(int, int, int);

int main() {
initIO();
int t;
scanf(“%d”, &t);

while (t--) {
    solve();
}

return 0;

}

void initIO() {
#ifndef ONLINE_JUDGE
freopen(“./input.txt”, “r”, stdin);
freopen(“./output.txt”, “w”, stdout);
#endif
}

void solve() {
int n;
scanf(“%d”, &n);

char* bin = (char*) calloc(n, sizeof(char));
scanf("%s", bin);

int product = 1;
for (int i = 2; i < n; i += 2) {
    int p = possibilities(bin[i - 2] - '0', bin[i - 1] - '0', bin[i] - '0');
    if (p == 0) {
        product = 0;
        break;
    }
    product = (product * p) % MOD;
}

printf("%d\n", product);

}

int possibilities(int arg1, int arg2, int out) {
return ((arg1 & arg2) == out) + ((arg1 | arg2) == out) + ((arg1 ^ arg2) == out);
}
`

5

u are getting wrong answer due to overflow in long long int as ans can be greater than LONG_MAX also, so use mod operation after each time you do ans*acp.

1 Like
6

I think it should be like this:
ans = (ans * acp) % 1000000007;

The reason is that if you keep multiplying a non-zero positive number by the variable ans, it will cross the limits of the data type.

Please note that the maximum value of the variable ans = 3 ^ 5000 (which, in my opinion, cannot be stored by any data type)

1 Like
7

Thanks :+1:

8

Please help me why this program is not getting accepted when tot_count%mod is directly printed using cout while when tot_count%=mod is calculated first and thereafter it is printed then it is being accepted.

include
using namespace std;
define mod 1000000007
int main() {
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
string s;
cin>>s;
long long count=0,tot_count=1;
for(int i=2;i<n;i+=2)
{
count=0;
if((((s[i-1]-‘0’) & (s[i-2]-‘0’)) == (s[i]-‘0’)) || (((s[i-1]-‘0’) | (s[i-2]-‘0’)) == (s[i]-‘0’)) || (((s[i-1]-‘0’)^(s[i-2]-‘0’))== (s[i]-‘0’)))
{
if(((s[i-1]-‘0’) & (s[i-2]-‘0’)) == (s[i]-‘0’))
{
count++;
}
if(((s[i-1]-‘0’) | (s[i-2]-‘0’)) == (s[i]-‘0’))
{
count++;
}
if(((s[i-1]-‘0’)^(s[i-2]-‘0’))== (s[i]-‘0’))
{
count++;
}
}
tot_count*=count;
// tot_count=tot_count%mod;
}
cout<<(tot_count%mod)<<endl;
}
return 0;
}