Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I recently came across this question: "You are given a boolean expression consisting of a string of the symbols 'true', 'false', 'and', 'or', and 'xor'. Count the number of ways to parenthesize the expression such that it will evaluate to true. For example, there are two ways to parenthesize 'true and false xor true' such that it evaluates to true."

I knew it is a dynamic programming problem so i tried to come up with a solution on my own which is as follows. Suppose we have a expression as A.B.C.....D where '.' represents any of the operations and, or, xor and the capital letters represent true or false. Lets say the number of ways for this expression of size K to produce a true is N. when a new boolean value E is added to this expression there are 2 ways to parenthesize this new expression 1. ((A.B.C.....D).E) ie. with all possible parenthesizations of A.B.C.....D we add E at the end. 2. (A.B.C.(D.E)) ie. evaluate D.E first and then find the number of ways this expression of size K can produce true.

suppose T[K] is the number of ways the expression with size K produces true then T[k]=val1+val2+val3 where val1,val2,val3 are calculated as follows.

1)when E is grouped with D.

i)It does not change the value of D

ii)it inverses the value of D

in the first case val1=T[K]=N.( As this reduces to the initial A.B.C....D expression ). In the second case re-evaluate dp[K] with value of D reversed and that is val1.

2)when E is grouped with the whole expression.

//val2 contains the number of 'true' E will produce with expressions which gave 'true' among all parenthesized instances of A.B.C.......D i) if true.E = true then val2 = N

ii) if true.E = false then val2 = 0

//val3 contains the number of 'true' E will produce with expressions which gave 'false' among all parenthesized instances of A.B.C.......D

iii) if false.E=true then val3=( 2^(K-2) - N ) = M ie. number of ways the expression with size K produces a false [ 2^(K-2) is the number of ways to parenthesize an expression of size K ].

iv) if false.E=false then val3 = 0

This is the basic idea i had in mind but when i checked for its solution http://people.csail.mit.edu/bdean/6.046/dp/dp_9.swf the approach there was completely different. Can someone tell me what am I doing wrong and how can i get better at solving DP so that I can come up with solutions like the one given above myself.

Thanks in advance.

share|improve this question
    
The question's wrong. true and (false xor true) = (true and false) xor true (easily seen by reducing both to false xor true). –  Peter Taylor Jun 20 '12 at 8:54
    
Thanks for pointing that out.I edited the question. –  newbie Jun 20 '12 at 9:57
    
Great question! I have to get better to DP too. Some say "ah.. DP is just about a simple recursion". It's not! –  Florents Tselai Jun 21 '12 at 10:32
    
@Florents Tselai just saw your comment. Why do you think it's not? –  John Donn Jan 24 at 10:47
add comment

2 Answers

up vote 7 down vote accepted

The answer, as with many things, is:

Practice, practice, practice.

By the way, I believe that in your solution you got into a dead-end by making a trivial mistake really early on: "There are 2 ways to parenthesize this new expression" -- aren't there more than 2? How about (A.B.(C.D.E)), for example?

share|improve this answer
    
"How do I get better at doing X?" - "Do X!" ... sounds reasonable ;-) –  Joachim Sauer Jun 20 '12 at 11:36
add comment

I agree with occulus that practice is most required, also would like to add that you need to pay attention in recognizing the patterns in problems that can be solved using DP (this is explained pretty well in CLRS)

You can find spoj problems that involve dynamic programming here :)

share|improve this answer
    
please comment before downvote so I can improve :) –  nischayn22 Jun 20 '12 at 11:38
    
that link doesn't work! –  deebee Jun 21 '12 at 0:04
    
@deebee updated it, thanks for telling :) –  nischayn22 Jun 21 '12 at 3:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.