REBIT - Editorial

editorial
, , , , ,
32

You need the probabilities in rational form, so that you can find the answer modulo a prime number as required by the problem.

33

Please help me out …why i am getting a wrong answer

https://www.codechef.com/viewsolution/31870565

34

Really nice problem.

My solution differed in three aspects.

1.) Rather than creating the expression tree explicitly, I looped through just to find the root operator for the current expression. This can be done by using a stack and finding the first operator where the stack is empty.

2.) I used a generic function that takes in any boolean operator that operates on two variables, and combine the probabilities based on the operator provided.

3.) Because only the final probability mattered, I computed the inverse of the denominator only at the end.

Here is a link to my solution: REBIT SOLN

I would love to hear feedback/suggestions on how to improve! Thanks

35

Shouldn’t it also be the sum of all 4 numerators? I didn’t calculate the number of #. Searched for days for error and one day I just replaced the denominator and finally received AC. Where was I wrong?

1 Like
36

Please help me out …i dont know where i am getting wrong :pray: :pray:
https://www.codechef.com/viewsolution/31870565

37

Try this

1
((((#|#)&#)|#)^((#^#)|#))

Expected Answer
646324225 833495041 757456897 757456897

One possible problem which I can figure out from your code is your way of calculating probability. Set base case as 1 for each operand rather than 0.25 and calculate probability at end.

38

Try this

1
((((#|#)&#)|#)^((#^#)|#))

Expected Answer
646324225 833495041 757456897 757456897

40

Indeed it is the same thing. Look we are calculating probability and the sum of all possible probabilities should be equal to 1. Hence numerator by
the denominator needs to be equal.

41

Hey can anyone point what mistake is there in my code:

#include<bits/stdc++.h>
#define ll long long int
using namespace std;

ll modInverse(ll a, ll m)
{
ll m0 = m;
ll y = 0, x = 1;

if (m == 1) 
  return 0; 

while (a > 1) 
{
    ll q = a / m; 
    ll t = m; 
    m = a % m, a = t; 
    t = y; 
    y = x - q * y; 
    x = t; 
} 
if (x < 0) 
   x += m0; 
return x;

}

void bitwise(string s){
ll mod = 998244353;
ll n = s.size();
ll count_0 = 1;
ll count_1 = 1;
ll count_a = 1;
ll count_A = 1;

for(int i = 2 ; i < n ; i += 2){
    ll curr_0 = count_0;
    ll curr_1 = count_1;
    ll curr_a = count_a;
    ll curr_A = count_A;
    if(s[i-1] == '&'){
        count_0 = 4*curr_0 + curr_1 + 2*curr_a + 2*curr_A;
        count_1 = curr_1;
        count_a = 2*curr_a + curr_1;
        count_A = 2*curr_A + curr_1;
    }
    else if(s[i-1] == '|'){
        count_0 = curr_0;
        count_1 = 4*curr_1 + curr_0 + 2*curr_a + 2*curr_A;
        count_a = 2*curr_a + curr_0;
        count_A = 2*curr_A + curr_0;
    }
    else{
        count_0 = curr_0 + curr_1 + curr_a + curr_A;
        count_1 = curr_0 + curr_1  + curr_a + curr_A;
        count_a = curr_0 + curr_1 + curr_a + curr_A;
        count_A = curr_0 + curr_1 + curr_a + curr_A;
    }
    
    count_0 = count_0 % mod;
    count_1 = count_1 % mod;
    count_a = count_a % mod;
    count_A = count_A % mod;
}

ll total = (count_0 + count_1)%mod;
total = (total + count_a)%mod;
total = (total + count_A)%mod;
total = total%mod;
total = modInverse(total, mod);

ll ans1 = ((count_0%mod)*total)%mod;
ll ans2 = ((count_1%mod)*total)%mod;
ll ans3 = ((count_a%mod)*total)%mod;
ll ans4 = ((count_A%mod)*total)%mod;

cout << ans1 << " " << ans2 << " " << ans3 << " " << ans4 << endl;

}

int main() {
// your code goes here
int t;
cin >> t;
while(t–){
string l;
cin >> l;
string s;
int n = l.size();
for(int i = 0 ; i < n ; i++){
if(l[i] != ‘(’ && l[i] !=’)’)
s.push_back(l[i]);
}
bitwise(s);
}
return 0;
}

42

This is wrong. I was making similar mistake but then I found out that I was wrong. See my wrong code and correct code.

44

Thanks a lot for pointing out the mistake.
Could you please elaborate a bit about this.If all of them is set to 1 then how we will calculate the probability.Moreover the denominator will be different for different expression

45

Mentioned as “Your output” is correct, I checked acroos correct solutions.

46

Yeah True

47

Denominator will be sum of all the 4 calculated possibilities . Then you can just multiply every possibility with modulo inverse of Denominator to get answer.

48

Ooh yes I reversed the order of correct and wa.

49

Please help me out. I have used almost the same approach as the one described in the editorial. My code has been able to successfully pass the sample test cases as provided above. Here is my code CodeChef: Practical coding for everyone
can someone please provide the test cases where the program fails.

50

I agree with you. This problem is among the most interesting problems that I solved in the past few years. I used a stack-based approach to compute the answer as well. To speed up the computation, I used a constant dp array to store the truth-table for each of the XOR, OR and AND two-input gate, where the domain for eah input is ZERO, ONE, A or NOT A. You can check the 28-line C++14 implementation of this approach in my previous comment.

51

Yeah it worked…Thanks a lot.

Could you please also tell me why the previous method didnt worked out.

52

https://www.codechef.com/viewsolution/31989789
please anybody can help to reduce time complexity as I am getting a TLE

53

Thanks bro, such a wonderful explanation. Thanks for your effort.