notred's blog

By notred, history, 13 months ago, In English

You are given a permutation of the n numbers 0, 1, 2, ...., n-1. It is required to sort the permutation in increasing order. The only operation allowed on the permutation is to swap the ith element with the jth element, for any 0 <= i < j < n. Each number i has an associated weight w_i, which is a positive integer. You are also given n-1 positive integers d_0, d_1, .., d_{n-2}, where d_i is the "distance" between the ith and (i+1)th element in the sequence. The distance between the ith and jth element, d_{ij} for i < j, is defined to be d_i + d_{i+1} + ... + d_{j-1}.

The cost of swapping the ith element with the jth element is d_{ij} multiplied by the sum of weights of the two numbers that are swapped. Basically, it is the distance by which the objects are moved multiplied by their weights. In such a swap both the ith and jth element are moved by a distance d_{ij}, other elements remain where they were.

You have to find the minimum total cost of swaps required to arrange the permutation in increasing order. Any help would be appreciated..

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