Double inversions

★★★★★

2.6

31 votes

Arrays, Data Structures, 1-D, Math

Details

Submissions

Discussion

Editorial

Problem

Consider a certain permutation of integers from $1$ to $n$ as $A = \{a_1, a_2,..., a_n\}$ and reverse of array $A$ as $R$ , that is, $R = \{a_n, a_{n -1},...,a_1\}$ . You are given the inversions at each position of array $A$ and $R$ as $\{IA_1, IA_2,….., IA_n\}$ and $\{IR_1, IR_2,….., IR_n\}$ respectively.

Find the original array $A$ . If, there are multiple solutions, print any of them. If there is no solution, then print -1.

Note: The inversion of array $arr$ for position $i$ is defined as the count of positions $j$ satisfying the following condition $arr_j > arr_i$ and $1 \leq j < i$ .

Input format

The first line contains $T$ denoting the number of test cases.
For each test case:
- The first line contains $n$ denoting the number of elements.
- The second line contains the elements $\{IA_1, IA_2,….., IA_n\}$ .
- The third line contains the elements $\{IR_1, IR_2,….., IR_n\}$ .

Output format

For each test case, print the array $A$ in the space-separated format or -1 if no solution exists. Each test case should be answered in a new line.

Constraints

$1 \leq T \leq 10 \\ 1 \leq n \leq 10^5 \\ 0 \leq IA_i, IR_i <n \space \forall \space i \in [1, n]$

Time Limit: 3

Memory Limit: 256

Source Limit:

Explanation

For first test case

Consider permutation $A = \{3, 4, 2, 1\}$ .

It can be seen that inversion for this array will be $IA = \{0 ,0,2, 3\}$ as:

For i = 1, no positions satisfy $arr_j > arr_i$ and $1 \leq j < i$ .
For i = 2, no position satisfy $arr_j > arr_i$ and $1 \leq j < i$ .
For i = 3, j = 1, 2 satisfy $arr_j > arr_i$ and $1 \leq j < i$ .
For i = 4, j = 1, 2, 3 no positions satisfy $arr_j > arr_i$ and $1 \leq j < i$ .

Now, $R = \{1, 2, 4, 3\}$ .

It can be seen that inversion for this array will be $IR = \{0, 0, 0,1\}$ as:

For i = 1, no positions satisfy $arr_j > arr_i$ and $1 \leq j < i$ .
For i = 2, no positions satisfy $arr_j > arr_i$ and $1 \leq j < i$ .
For i = 3, no positions satisfy $arr_j > arr_i$ and $1 \leq j < i$ .
For i = 4, j = 3 satisfy $arr_j > arr_i$ and $1 \leq j < i$ .

Thus, $A = \{3, 4, 2, 1\}$ is a valid permutation.

For second test case

There is no valid permutation that satisfies the condition.