Btw...another observation in case 1.2: I wrote: Now, let v=min(x[1],x[2],x[3],.....x[k]), and 'h' be the index of the minimum element(x[h] is minimum) Then, dp[i][j]=v+sigma(f!=h)[min(x[f],y[f])]
Here, just setting dp[i][j]=v will do (athough the complexity is same in both the cases) because for all (f!=h), atleast one of x[f], y[f] will be 0. (by not performing any swaps, and just evaluating the value at the node) hence dp[i][j]=min(x[1],x[2],x[3],.....x[k]) On Dec 28, 10:32 am, suhash <suhash.venkat...@gmail.com> wrote: > This problem can be solved using dp in O(n), where 'n' is the number > of nodes in the tree. > Definitions: > Let gate[i] be a boolean denoting whether the gate at node 'i' is > 'AND' or 'OR'. (0-'AND' 1-'OR') > Let dp[i][j] store the minimum no. of swaps required to get a value of > 'j' (0 or 1), for the subtree rooted at 'i'. > Let ok[i] be a boolean which denotes whether a flip operation can be > performed at the i'th node or not. > Let i1,i2,i3.....ik be the children of node 'i' > > Now we have 2 cases: > case 1: ok[i] = 0 (means no flipping possible at node 'i') > In this, we have many cases: > case 1.1: gate[i]=0 (there is an AND gate at node 'i'), > and j=1 > this means all children should have a value > 1. > hence dp[i][j]=dp[i1][j]+dp[i2][j] > +.....dp[ik][j] > case 1.2: gate[i]=0 (there is an AND gate at node 'i'), > and j=0 > i will discuss this case in the end. > case 1.3: gate[i]=1 (there is an OR gate at node 'i'), and > j=1 > this one too, for the end > case 1.4: gate[i]=1 (there is an OR gate at node 'i'), and > j=0 > this means all children should have a value > 0. > hence dp[i][j]=dp[i1][j]+dp[i2][j] > +.....dp[ik][j] > > case 2: ok[i] = 1 (means flipping is possible at node 'i') > We have 2 cases in this: > case 2.1: we choose not to flip gate at node 'i'. This > reduces to the 4 cases above(case 1.1, 1.2, 1.3, 1.4) > case 2.2: we choose to flip gate 'i'. Again it is similar > to cases discussed above, except replacing 'AND' by 'OR' and vice > versa > and dp[i][j]=1 + dp[i1][j]+dp[i2][j] > +.....dp[ik][j] > > Note: 1)Boundary cases for leaf nodes. > 2)Top down is easier. > 3)If it is impossible to get a value 'j' for subtree rooted > at 'i', then dp[i][j]=INF(some large value) > 4)Answer is dp[root][required_value(o or 1)]. If this > quantity is INF, then it is impossible to achieve this. > > Now, lets discuss case 1.2: > We have an 'AND' gate and we want a result of 0. > So, atleast one of the children of node 'i' should be 0. > Now create 2 arrays x,y each of size 'k' > x[1]=dp[i1][0], y[1]=dp[i1][1] > x[2]=dp[i2][0], y[2]=dp[i2][1] > . > . > . > x[k]=dp[ik][0], y[k]=dp[ik][1] > > Now, let v=min(x[1],x[2],x[3],.....x[k]), and 'h' be the index of the > minimum element(x[h] is minimum) > Then, dp[i][j]=v+sigma(f!=h)[min(x[f],y[f])] > > The other cases are similar to this! > I can write a code and send if you have doubts. > > On Dec 28, 9:36 am, Anand <anandut2...@gmail.com> wrote: > > > @Terence. > > > Could please elaborate your answer. Bottom up level order traversal helps to > > get the final root value but how to use it to find minimum flips needed to > > Obtain the desired root value. > > > On Fri, Dec 24, 2010 at 1:56 AM, Terence <technic....@gmail.com> wrote: > > > Using the same level order traversal (bottom up), calculating the minimum > > > flips to turn each internal node to given value (0/1). > > > > On 2010-12-24 17:19, bittu wrote: > > > >> Boolean tree problem: > > > >> Each leaf node has a boolean value associated with it, 1 or 0. In > > >> addition, each interior node has either an "AND" or an "OR" gate > > >> associated with it. The value of an "AND" gate node is given by the > > >> logical AND of its two children's values. The value of an "OR" gate > > >> likewise is given by the logical OR of its two children's values. The > > >> value of all of the leaf nodes will be given as input so that the > > >> value of all nodes can be calculated up the tree. > > >> It's easy to find the actual value at the root using level order > > >> traversal and a stack(internal if used recursion). > > > >> Given V as the desired result i.e we want the value calculated at the > > >> root to be V(0 or 1) what is the minimum number of gates flip i.e. AND > > >> to OR or OR to AND be required at internal nodes to achieve that? > > > >> Also for each internal node you have boolean associated which tells > > >> whether the node can be flipped or not. You are not supposed to flip a > > >> non flippable internal node. > > > >> Regards > > >> Shashank Mani Narayan > > >> BIT Mesra > > > > -- > > > You received this message because you are subscribed to the Google Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to algoge...@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > > > . > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
