REBIT - Editorial

editorial
, , , , ,
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.

54

you’re welcome man

55

I watched a video and based on that I prepare my solution but I don’t know which test cases I have not taken into consideration. Can anyone help me?
https://www.codechef.com/viewsolution/32029848

56

I have found the test case but I am not able to figure out why it is giving WA. I have followed the same approach by using infix.
1
((((#|#)&#)|#)^((#^#)|#))
This is the test case for which I am getting WA.

57

This link doesn’t have solution of this question.

58

Exercise Sol :

Theorem : Valid Expression in above given form will be of length 4p + 1 \forall p\geq 0 , p \in I.

Proof : This is proof by induction.

Base case : for p = 0
4p + 1 = 1
Valid string of length 1 : #
Let’s take one more base case (even though it isn’t required for the proof)
p = 1,
4 p + 1 = 5
Valid string of len 5 : (#o#)
where o is any of valid operator.

Induction Hypothesis :
Assuming for p = k
The valid string will be of length 4k + 1 holds
and the string would be of the any of the valid form. One such form is given below.
(((\cdots o(\#o\#)\cdots o(\#o\#)\cdots)))

for p = k + 1

p = k + 1
4(k + 1) = 4 k + 4 + 1 = 4m + 1

We can easily see that for appending an valid expression onto an already valid expression we need 4 thing,
one new operand \# one operator o and two brackets '(' and ')'
For more clarification I am assigning a postfix notation to brackets
(_{x} and )_x
and I am renaming the valid expression of 4k + 1 length as exp_k
So the new expression would be written as :
(_x \# o \,exp_k)_x
or (_x \, exp_k \, o \#)

It can be put inside the valid expression somewhere in middle as well.

Now we have included the new exp we have increase the length of old expression by 4.
so new length will be

4 k + 1 + 4 = 4(k + 1) + 1

Hence proved.