Indian Computing Olympiad

Training Material

Dynamic programming on trees→Mobiles (APIO 2007)

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.

  1. Any two toys are at the same level (i.e., are joined to the roof by the same number of rods), or differ by only one level;
  2. For any two toys that differ by one level, the toy to the left is further down than the toy to the right.

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.

Solution

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.

  • The left subtree of the root is a complete binary tree of depth k and the right subtree is a "mobile tree" of depth k-1.
  • The left subtree of the root is a "mobile tree" of depth k the right subtree is a complete binary tree of depth k-1.

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)),}

Problems related to