A mobile is a multi-layered decoration that is hung from the roof. Each mobile consists of a series of horizontal rods connected by vertical wires. Each rod has a wire hanging from both ends, which holds either another horizontal rod or a toy.
A sample mobile is shown below:
| ------- 1 --------------------- | | --- 2---------- --3------------ | | | | O --4------- --5------- --6------- | | | | | | O O O O O O
You need to find a mobile that has the following configuration.
Mobiles can be reconfigured as follows.
The ends of any individual rod can be 'swapped' by unhooking whatever is hanging beneath the left and right ends of the rod, and reattaching them again at opposite ends. This process does not modify the ordering of any rods or toys further down.
The mobile above satisfies condition 1 but not condition 2 because the toy at the leftmost end is at a higher level than the toys to its right. This mobile can be reconfigured to meet condition 2 using two reconfigurations, first swapping the ends of rod 1 and then swapping the ends of rod 2.
| ------- 1 --------------------- | | --3------------ --- 2---------- | | | | --5------- --6------- --4------- O | | | | | | O O O O O O
The task is to identify if a given mobile can be reconfigured to meet requirements 1 and 2 and, if so, compute the minimum number of reconfigurations required to do so.
We can think of the mobile as a binary tree. A binary tree that meets requirements 1 and 2 will have levels 1,2,..,k-1 filled completely and level k filled to some extent from left to right. Let us call such a tree a "mobile tree".
In a mobile tree of depth k, one of the two following cases must hold, depending on how many leaves are there are depth k.
We can then inductively define the following quantities:
C(v): Minimum number of moves to make the tree rooted at v complete:
This is 0 if v has a complete tree below it, and infinity otherwise.
M(v): Minimum number of moves to make the tree rooted at v a mobile tree.
To determine M(v), we have to consider three cases.
Case 1: depth(leftchild(v)) < depth(rightchild(v))
Need to swap left and right. After swapping, get a complete tree on right and mobile tree on left
Case 2: depth(leftchild(v)) &rt; depth(rightchild(v))
No swap needed, get a complete tree on right and mobile tree on left.
Case 3: depth(leftchild(v)) = depth(rightchild(v))
May or may not swap. After swapping (if necessary), left must be complete, right must be mobile tree.
This gives us the following update rule for M(v):
M(v) = | 1 + C(leftchild(v)) + M(rightchild(v)) | if Case 1 |
M(leftchild(v)) + C(rightchild(v)) | if Case 2 | |
min {1 + M(leftchild(v)) + C(rightchild(v)), | if Case 3 | |
C(leftchild(v)) + M(rightchild(v)),} |
©IARCS 2012–2016
PÄ›stujeme web | visit: Skluzavky