Permutations of numbers

★★★★★

3.5

15 votes

Sorting, Algorithms, Advanced Sorting

Details

Submissions

Discussion

Editorial

Problem

There are $N$ numbers from $1$ to $N$ and your task is to create a permutation such that the cost of the permutation is minimum. For each number, there is a left and right cost. To put number $p$ $(1 \leq p \leq N)$ at the $i^{th}$ index, it costs $L_p *(i - 1) + R_p*(N-i-1)$ where $L[]$ and $R[]$ cost is given.

You do not need to find that permutation but you need to find the total minimum possible cost of the permutation.

Input format

The first line contains $T$ denoting the number of test cases.
The first line of each test case contains the number $N$ .
The next line of each test case contains $N$ integers to indicate the left cost.
The next line of each test case contains $N$ integers to indicate the right cost.

Output format

For each test case, print a single line containing one integer that denotes the minimum cost of the permutation.

Constraints

$1 \leq T \leq 20$

$2 \leq N \leq 10^5$

$1 \leq L_i,R_i \leq 10^7$ for each $1 \leq i \leq N$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

For the test case $1$ , The possible permutaion will be $3, 1, 2$ . The cost will be $(0 * 6 + 2 * 2) + (1 * 1 + 1 * 4) + (2 * 2 + 0 * 7) = 13$ and this is the minimum possible value.

For the test case $2$ , The possible permutaion will be $1, 4, 3, 2$ . The cost will be $(0 * 4 + 3 * 3) + (1 * 2 + 2 * 2) + (2 * 3 + 1 * 5) + (3 * 5 + 0 * 8) = 41$ and this is the minimum possible value.