@Terence: I like your explanation. Very short and crisp! :)
On Dec 28, 12:10 pm, Terence <technic....@gmail.com> wrote:
> Let cst[i][j] store the cost to flip node i to given gate j (0-'AND',
> 1-'OR').
> Then: cst[i][j] = 0, if j==gate[i];
> cst[i][j] = 1, if j!=gate[i] and ok[i];
> cst[i][j] = INFINITY, if j!=gate[i] and !ok[i];
>
> 1. To get value 1:
> 1.1 flip current gate to AND, and change all children to 1
> 1.2 flip current gate to OR, and change any child to 1.
> 2. To get value 0:
> 1.1 flip current gate to AND, and change any child to 0
> 1.2 flip current gate to OR, and change all children to 0.
>
> So for internal node i:
> dp[i][0] = min(cst[i][0]+sum{dp[x][1] for each child x of i},
> cst[i][1]+max{dp[x][1] for each child x of i});
> dp[i][1] = min(cst[i][0]+max{dp[x][0] for each child x of i},
> cst[i][1]+sum{dp[x][0] for each child x of i});
> for leaf i:
> dp[i][j] = (value[i]==j ? 0 : INFINITY)
>
> On 2010-12-28 13:32, suhash 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.
