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.
