Author |
Topic: minimum number of flips required (Read 1759 times) |
|
ic10503
Junior Member
Gender: 
Posts: 57
|
 |
minimum number of flips required
« on: Oct 17th, 2010, 9:10pm » |
 Quote  Modify
|
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.
|
| « Last Edit: Oct 17th, 2010, 9:11pm by ic10503 » |
 IP Logged |
|
|
|
ic10503
Junior Member
Gender:
Posts: 57
|
|
Re: minimum number of flips required
« Reply #1 on: Oct 19th, 2010, 5:41am » |
Quote Modify
|
Any replies? Is the problem not clear?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: minimum number of flips required
« Reply #2 on: Oct 19th, 2010, 6:40am » |
Quote Modify
|
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]
|
| « Last Edit: Oct 20th, 2010, 1:41am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ic10503
Junior Member
Gender:
Posts: 57
|
|
Re: minimum number of flips required
« Reply #3 on: Oct 19th, 2010, 10:40am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: minimum number of flips required
« Reply #4 on: Oct 19th, 2010, 12:03pm » |
Quote Modify
|
on Oct 19th, 2010, 10:40am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
newb
Newbie
Posts: 38
|
|
Re: minimum number of flips required
« Reply #5 on: Oct 24th, 2010, 2:58am » |
Quote Modify
|
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. 
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: minimum number of flips required
« Reply #6 on: Oct 24th, 2010, 11:55am » |
Quote Modify
|
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.
|
| « Last Edit: Oct 24th, 2010, 11:58am by birbal » |
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: minimum number of flips required
« Reply #7 on: Oct 25th, 2010, 8:11am » |
Quote Modify
|
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(...).
|
| « Last Edit: Oct 25th, 2010, 8:13am by Grimbal » |
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: minimum number of flips required
« Reply #8 on: Oct 25th, 2010, 11:17pm » |
Quote Modify
|
on Oct 25th, 2010, 8:11am, Grimbal wrote: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(...). |
|
Oops! i missed these cases. Thanks for correction.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print