| Submit | All submissions | Best solutions | Back to list |
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.
Input
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)
Output
For each test case, print the minimum possible value of P considering all permutations of the given numbers.
Example
Input: 1 5 1 8 3 6 5 1 2 3 4 5 Output 24
One of the possible permutation of given numbers which has p = 24 is 1, 3, 5, 6, 8
| Added by: | amit karmakar |
| Date: | 2011-08-15 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | own problem used in - http://www.spoj.pl/MAIN11/ |
hide comments
|
2023-05-11 04:56:26
Do not permutate the cost array, otherwise you will get 21 instead of 24 in the given test case. |
|
|
2019-11-21 19:53:21
AC in my first attempt ! nice bitmask dp ... good one for beginner |
|
|
2019-06-15 15:16:21
AC in 2nd attempt :D |
|
|
2017-07-31 16:31:19
@Divyank no, there is no use for cost[0] |
|
|
2015-07-07 15:53:30 ankit kumar
@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. |
|
|
2015-07-02 12:13:34 bitwise
why can't the minimum possible value be 21 ?????? for : 5 6 8 1 3 8 6 5 3 1 |
|
|
2014-12-23 13:31:52 Divyank Duvedi
Is there any use of cost[0]? |
RSS