shuprog1's blog

How to solve this problem using Bitmasks-DP?
By shuprog1, 10 years ago, In English

There are N servers which you have to place in N slots. Slots and servers are numbered from 1 to N. A distance between slots i and j is |i — j|. There are M pairs of servers that should be connected by wire. You are to place all the servers in the slots so the total wire length is minimized.

The problem statement is given here : Problem Statement

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The editorial of this problem uses bitmasks approach but I could not understand it from there.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Consider the optimal arrangement of the servers. Imagine it in an array. Now imagine the links between the servers as horizontal lines between the array elements.
    Consider a case where there are 5 servers, arranged in the order 1, 2, 3, 4, 5. Here, edges are (1, 4), (1, 5), (2, 4), (3, 4), (3, 5). It looks as follows:

    Notice that I deliberately did not extend the lines till their end points (except for the top-most line, sorry for that :P ). Now, if you add the number of lines over each position, it will give you the cost of your arrangement. In this case — 2 + 3 + 5 + 2 + 0 = 12.
    So now if you calculate this value individually and add all of them, you'll get the cost of a particular arrangement.
    Now suppose you have placed 1 and 2 already. Now if you place 3, the relative order of 1 and 2 does not matter, only thing that matters now is how many lines are already coming out of 1 and 2 combined. When you place your next number, some of these "open" lines will be closed and some new lines will be added. After that, you can add this newly obtained number of open lines as the score of the current position and calculate the remaining cost recursively (look at my solution for the implementation). The last thing to notice is that for a given set of placed servers, this "open" value is unique, hence you do not need to memoize it. :)

    Solution

    → Reply