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.
