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 C[i](1 <= C[i] < 150)


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


1 8 3 6 5
1 2 3 4 5


One of the possible permutation of given numbers which has p = 24 is 1, 3, 5, 6, 8

hide comments
scolar_fuad: 2019-11-21 19:53:21

AC in my first attempt !
nice bitmask dp ...
good one for beginner

walter_whitee: 2019-06-15 15:16:21

AC in 2nd attempt :D

hodobox: 2017-07-31 16:31:19

@Divyank no, there is no use for cost[0]

ankit kumar: 2015-07-07 15:53:30

@bitwise ans in your case should be abs(6-5)*2+abs(8-6)*3+abs(1-8)*4+abs(3-1)*5>21&&24.

bitwise: 2015-07-02 12:13:34

why can't the minimum possible value be 21 ??????
for :
5 6 8 1 3
8 6 5 3 1

Divyank Duvedi: 2014-12-23 13:31:52

Is there any use of cost[0]?

Added by:amit karmakar
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem used in -