SPOJ Problemset (Classical): 9386. Re-Arrange II #[MAIN112]

Problem description (quoted here for convenience):

For a sequence of N integers, A1, A2, ..... AN

We can calculate the stability factor P, as

P = sum of all (abs(Ai-Ai-1)*C[i]) where 2 <= i <= N

C[i] is the cost of putting a number at position i

Your task is find the minimum P for the given N numbers considering all the different permutations of them.

I just need a nudge in the right direction, concerning the general approach to solving this problem. (Little bits of pseudocode are welcome, but I am confident to pretty much code up a solution once the overall algorithm is generally clear)

I've thought about this for quite a while, but am still stuck at arriving at any solution which satisfies the constraints of this problem (N <= 15) A brute-force approach only seems to perform well up to N=10 really.

First off, for the largest possible test case N=15, I don't believe that you're able to enumerate and consider all the 15! permutations in order to find your answer in sufficiently good time, as the complexity class will not permit this.

So we need to make several simplifying assumptions to reduce this search space. This is where I'm stuck. Or maybe it just comes down to a smarter way to begin traversing this permutation space?

I've tried to use dynamic programming to solve this problem, because permutations share many common bits which can be precomputed (memoised) and stored and reused when necessary, eg. A[] = 123456 & A[] = 123465 both will give the same partial sum for 1234-, but this yielded no success because you still have to go through the 15! permutations and will开发者_JAVA百科 TLE way before that, so it's no good.

Another idea is to work with all the possible permutations of the differences between successive A's and all elements of C[], and first find the pair which will produce the minimum abs(A[i]-A[j])*C[k] value out of all these, assign those & mark them as used, then carry on with one of the i or j to form the next pair, iterate through again and repeat. This should complete in polynomial time (n^3 approx. i'm guessing), but the assumption fails for some examples.

I don't think this problem should be so difficult to involve transforming this into some sort of graph problem - where A[i], A[j] form nodes, and C[k] is the cost of the edge linking these nodes, or maybe some boolean SAT problem...that all seems to be going down the wrong track altogether.

If you were to google this, you'd probably find almost nothing related to this problem, apart from the SPOJ site hosting this problem.

Many thanks in advance.

You can use an O(n*2^n) space, O(n^2*n^2) time dynamic programming algorithm on subsets to solve it.

The key insight is that as you are building up optimal solutions from left to right, only the previously placed number and the used subset matter, but not the order that things were placed in the used subset.

The computation has basically the same structure as this solution to the Travelling Salesman Problem.

You were on the right track with your DP idea. The insight is just that the optimal path after all of these partial paths is the same

1235

1325

2135

2315

3125

3215

So you don't actually need to explore all possible permutations, just those that having the best partial path.

Here is some TLE Python code that implements the algorithm described, but fails because of the constant factor slowdown in Python. I converted to C++ and got an AC.

global A
global C

A = []
C = []

def Solve(used, last, cache):
  if (used, last) in cache:
      return cache[(used, last)]
  cur_pos = len(used)
  if cur_pos == len(A):
    return 0

  mn = 1e10
  for idx in range(len(A)):
      if not idx in used:
          next_used = used.union([idx])
          subcost = Solve(next_used, A[idx], cache)
          additional = C[cur_pos] * abs(last - A[idx])
          mn = min(mn, subcost + additional)
  cache[(used, last)] = mn
  return mn

T = int(raw_input())
for i in range(T):
  N = int(raw_input())
  A = map(int, raw_input().split())
  C = map(int, raw_input().split())
  cache = {}
  print min(Solve(frozenset([idx]), A[idx], cache) for idx in range(len(A)))