SPOJ MAIN112 – Re-Arrange II Solution

SPOJ Solution

MAIN112 – Re-Arrange II

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.


First line contains an integer T(1<=T<=10) which denotes the total number of test cases. Each test case consists of three lines.

The first line contains the integer N(1<=N<=15). The second line contains a space separated list of N integers(<150) which denote the given set of numbers.

The third line contains a space separated list of N integers. The ith integer on this line denotes the value for Ci


For each test case, print the minimum possible value of P considering all permutations of the given numbers.

MAIN112 Soultion


Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.