REBIT - Editorial

editorial
, , , , ,
7

If anyone wants a video explanation of expression trees : Expression Tree - SPOJ - Complicated Expressions - YouTube

I have used infix to postfix conversion to deal with the expressions.
Here is my python code: CodeChef: Practical coding for everyone

1 Like
8

Correct me if i am wrong…shouldnt the value of fn in main function would always be pow(4,c) , where c is the total number of ‘#’ present in the expression.

9

Yes. It should be pow(4, number of #). Also to the setter, this was my favorite question of the contest
because I think it requires a hell of creative thinking coming up with such a question. (idk this was the first time I was dealing with such problem). my solution.

10

Let E be a valid expression .
E= (E1 op E2 )
then PE can be written in terms of combination P[E1] (0,1,a,A) and P[E2] (0,1,a,A) under different operators
The recursion can be carried out iteratively using a stack… whenever we find ‘#’ we push (1/4,1/4,1/4,1/4) to stack . whenever we find a closing bracket pop two values from the stack and push their result . separate stacks can be maintained for different probabilities . final result will be the value in stack .
base case when E is ‘#’ p[E] (0,1,a,A)={1/4,1/4,1/4,1/4} as all are equally probable.
Link to solution -
https://www.codechef.com/viewsolution/31584883

11

Wow I was wildly off on this one. I tried to use infix evaluation algorithm and hard-coding all probabilities. Couldn’t think of test cases that’d fail, but still didn’t get AC.

1 Like
13

Try this:

2
(((#^#)|(#&#))&((#&#)^#))
((#|#)|#)

Your output
526417921 900759553 783777793 783777793
857866241 233963521 889061377 889061377

Correct output
526417921 900759553 783777793 783777793
982646785 233963521 889061377 889061377

14

I basically considered all possibilities like 0 xor {0,1,a,A}, 0 & {0,1,a,A},0 | {0,1,a,A} similarly for all 1,a,A. And with little observation it can be seen that the possibilities of {1,0,a,A} is getting multiplied with each expression. Code

16

I find something fishy in your expression in line 49 in operation == ‘|’ if you are using v[0] for zero probability then it should be v[0]=v1[0]*V2[0] as 0=0|0 but you wrote something else .Please verify your findval function properly.If you would comment your code it would be easy for me to help

17

I tried the above test case mine is also printing the same value.
Lets take the equation ((#|#)|#)
The probability of 0,1,a,A are 1/64, 49/64, 7/64,7/64 respectively.
in the result 857866241 is 1inv(64)%998244353 so the 49inv(64)%998244353 should be 109182983 but it is 233963521
but in my ans 982646785 is 1inv(64)%998244353 so the 49inv(64)%998244353 is 233963521. What am I missing? could you please help me why I am getting this wrong ans.

18

Can Anyone help me in finding modulo of a fraction…??

19

Thank you :")
brother

20

Thank you Thank you thank you ,
idk how that v2[1] came :sob: . now it passed.
Thanks

21

Sad it happens at times :pensive: Anyways welcome :sweat_smile:. Did you solve ppdiv I need some help

22

Thanks a lot it is really helpful.

23

https://www.codechef.com/viewsolution/31545809
Can i get any test cases where my program gives WA and NZEC ? i tried few test cases later with my AC code but all of them were giving the same answers

24

refer modulo multiplicative inverse link
Since the modulo given is prime we can go for fermat’s little theoram.
say our denominator is 4 raised to the power of number of # we encounter in the expression.
let Y be the number of # we encountered in our expression.
let M be the prime modulo provided in the problem
By applying fermat’s little theoram,

INV = ((4^Y)^M-2)%M // Q^-1 % MOD

we can do a fast modular exponentiation for base 4 and power Y*(M-2) modulo M

25

This is my O(|L|) stack-based C++14 solution that computes the answer without creating the binary tree of the well-formed Boolean expression.

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

1 Like
27

CodeChef: Practical coding for everyone. Time complexity of the algorithm is 16*L . But, why am I not getting an AC for big test cases ?. I got partial score of 30% for the question. I request anyone to tell me why performing recursion sometimes for over n=10^6 takes too much time to get accepted in contests. Thanks in advance !

29 
    Is this approach to find probability Right or Wrong? 

    string l;
    cin >> l;
    l=infixToPostfix(l);
    long double p0=0.25,p1=0.25,pa=0.25,pA=0.25;
    long double P0,P1,Pa,PA;
    for(int j=0;j<l.length();j++)
    {
        switch(l[j])
        {
            case '&' :  P0=p0+((0.25)*p1)+((0.5)*pa)+((0.5)*pA);
                        P1=(0.25)*p1;
                        Pa=(((0.25)*p1)+((0.5)*pa));
                        PA=(((0.25)*p1)+((0.5)*pA));
                break;

            case '|' :  P0=(0.25)*p0;
                        P1=((0.25)*p0)+p1+((0.5)*pa)+((0.5)*pA);
                        Pa=(((0.25)*p0)+((0.5)*pa));
                        PA=(((0.25)*p0)+((0.5)*pA));
                break;

            case '^' :  P0=0.25;
                        P1=0.25;
                        Pa=0.25;
                        PA=0.25;
                break;
        }
        p0=P0,p1=P1,pa=Pa,pA=PA;
    }
30

you’re welcome buddy

1 Like