here is my approach :
Starting from the root node ,
if root node need to have a 1 ...
if root is an and gate :
flips = minflips for left child to have value 1 + minflips for the
right child to have value 1
else
flips = minimum of ( minflips for left child to have value 1 , minflips
for right child to have value 1)
For a leaf node , return 0 if the leaf has the value needed else return
INFINITY.Also if at any internal node if it is not possible return INFINITY.
On Tue, Dec 28, 2010 at 10:06 AM, Anand <[email protected]> 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 <[email protected]> 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 [email protected].
>> To unsubscribe from this group, send email to
>> [email protected]<algogeeks%[email protected]>
>> .
>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
