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