wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> minimum number of flips required
        
(Message started by: ic10503 on Oct 17^th, 2010, 9:10pm)

Title: minimum number of flips required
Post by ic10503 on Oct 17^th, 2010, 9:10pm

Given a complete binary tree (either a node is a leaf node or has two children) every leaf node has value 0 or 1. Every internal node has value as the AND gate or OR gate. you are given with the tree and a value V.
You have to output the minimum number of flips (AND to OR or OR to AND) if the evaluated value is not equal to V, if it is equal return 0, if not possible return -1. you can just change the value of internal nodes i.e can make AND to OR , OR to AND to get the desired output.
Give the minimum number of flips required to get the desired output.
I know DP has to be applied, but I am not able to come up with the recursive relation.

Title: Re: minimum number of flips required
Post by ic10503 on Oct 19^th, 2010, 5:41am

Any replies? Is the problem not clear?

Title: Re: minimum number of flips required
Post by towr on Oct 19^th, 2010, 6:40am

You can get 0 if any of the leaves is 0, and 1 if any of the leaves is 1; so if those condition aren't met return -1.
Then if v=0, find the subtree evaluating to 0 that has the fewest ORs on the path to it; if v=1 find the subtree evaluating to 1 that has the fewest ANDs on the path to it. (And return that fewest number of ORs or ANDs, respectively; if it's 0, then the tree evaluates to v. So that case is already covered.)

[edit]Actually, come to think of it; this just comes down to finding the appropriate root-leaf path with the fewest ORs/ANDs.[/edit]

Title: Re: minimum number of flips required
Post by ic10503 on Oct 19^th, 2010, 10:40am

Quote:

Then if v=0, find the subtree evaluating to 0 that has the fewest ORs on the path to it;

Didnt get this point. Path to what? Can you please explain this?

Quote:

Actually, come to think of it; this just comes down to finding the appropriate root-leaf path with the fewest ORs/ANDs.

How is the original problem equivalent to this?

Title: Re: minimum number of flips required
Post by towr on Oct 19^th, 2010, 12:03pm

on 10/19/10 at 10:40:29, ic10503 wrote:

Didnt get this point. Path to what?

The path to the root of the subtree.

Quote:

How is the original problem equivalent to this?

I was thinking that a subtree has value 1 if there is a path of ORs to a 1, and has value 0 if there's a path of ANDs to a 0. However, I've made a mistake there, because of course an OR of two 0's is also 0, and the AND of two 1's is 1. So let's just forget I mentioned it.

Title: Re: minimum number of flips required
Post by newb on Oct 24^th, 2010, 2:58am

if a node is 'and' and we need 0 at node:

1)don't flip node.
minimum number of flips required to get 0=
min(flip(node->left,0),flip(node->right,0));
{get either child as 0 then we will hv 0 at node }

2)flip node from and to or.
minimum number of flips required to get 0=
1+ flip(node->left,0)+flip(node->right,0);
{we will hv to get both child as 0 + 1 more flip}

now flip(node,0)= min(eq1,eq2);

similarly, form case for (node,1)

find till you reach root node and desired value at root.

I hope this makes sense. :)

Title: Re: minimum number of flips required
Post by birbal on Oct 24^th, 2010, 11:55am

You can try something like this:

for every internal node k, maintain two states
F(0,k) : Minimum flips required to get a 0 at node k.
F(1,k) : Minimum flips required to get a 1 at node k.

for a subtree like this
a
/ \
/ \
b c
To get a 0 at a, we can have following cases:
1. b=0 , c=0 , a=OR
2. b=0 , c=1 , a=AND
3. b=1 , c=0 , a=AND

To get a 1 at a, we can have following cases:
1. b=0 , c=1 , a=OR
2. b=1 , c=0 , a=OR
3. b=1 , c=1 , a=AND

So you can use F(0,b) , F(1,b) , F(0,c) , F(1,c) to calculate F(0,a) and F(1,a). Take the minimum of the above 3 cases at every step. Start from leaf nodes.

Title: Re: minimum number of flips required
Post by Grimbal on Oct 25^th, 2010, 8:11am

Looks good.

But you should add the cases
0. b=0 , c=0 , a=AND
resp.
0. b=1 , c=1 , a=OR

You should also save the state telling whether it is at all possible to get the 0 or 1 you want (or return a large number for F(...).

Title: Re: minimum number of flips required
Post by birbal on Oct 25^th, 2010, 11:17pm

on 10/25/10 at 08:11:09, Grimbal wrote:

Oops! i missed these cases. Thanks for correction.