Editorial Of Easy one! (CYPAUG01)

Problem : https://www.codechef.com/CYAU2019/problems/CYAUG01
Problem name : Easy One!
Problem Difficulty : Simple
Contest Code : CYAU2019

Editorial of Easy one!

In question it was defined that we have to work on bitwise operator so we need to convert string in binary form.

We will work on bitwise OR so lets first know about OR table.

0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1

So by this table we now know that there are 3 ways of getting 1.

So we are given a string as input and we have to tell how many such strings exist so that their bitwise OR value is same as given string.
Let’s consider case of B first:
Input
B

Explanation:

convert this string to binary:
value of “B”= 1
binary = 000001
Let this binary form as input we need to tell how many input exist for this output.

So for getting 0 as output we have only one option taking that bit as 0 in both input string.

For getting 1 as output we have 3 option

first string bit second string bit Output

 1                            0                        1

 0                            1                         1

 1                           1                          1

So now we know that for each bit value 1 we have 3 options.

So number of input string possible for getting that string as output = (power(3,number of set bits) )% mod

For refrence you can see my code:

#include<bits/stdc++.h>
using namespace std;
#define max1 100005
#define mod 1000000007
int main()
{
ll i,j,k,n,m,z,y,x,ans=0;
string ch;
string ch1=“ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_”;
cin>>ch;
vector value(300,0);
m=ch1.length();
//debug(m);
for(i=0;i<m;i++)
{
value[ch1[i]]=i;
}
n=ch.length();
ans=1;
for(i=0;i<n;i++)
{
x=value[ch[i]];
for(j=0;j<6;j++)
{
if((x&(1<<j)))
{
ans=(ans*3)%mod;
}
}
}
cout<<ans;
}

1 Like