Header Ads Widget

Double inversions Solution

Rajnish Tripathi 10:10

  Problem

Consider a certain permutation of integers from 1 to � as ​​​​�={�1,�2,...,��} and reverse of array � as �, that is, �={��,��−1,...,�1}. You are given the inversions at each position of array � and � as {��1,��2,…..,���} and {��1,��2,…..,���} respectively.

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

Note: The inversion of array ��� for position � is defined as the count of positions � satisfying the following condition ����>���� and 1≤�<�.

Input format

  • The first line contains � denoting the number of test cases.
  • For each test case:
    • The first line contains � denoting the number of elements.
    • The second line contains the elements {��1,��2,…..,���}.
    • The third line contains the elements {��1,��2,…..,���}.

Output format

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

Constraints 

1≤�≤101≤�≤1050≤���,���<� ∀ �∈[1,�]

Sample Input
2
4
0 0 2 3
0 0 0 1
3
0 2 1
2 1 0
Sample Output
3 4 2 1
-1
Time Limit: 3
Memory Limit: 256
Source Limit:
Explanation

For first test case

Consider permutation �={3,4,2,1}.

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

  •  For i = 1, no positions satisfy   ����>���� and 1≤�<�.
  •  For i = 2, no position satisfy   ����>���� and 1≤�<�.
  •  For i = 3, j = 1, 2 satisfy   ����>���� and 1≤�<�.
  •  For i = 4, j = 1, 2, 3 no positions satisfy   ����>���� and 1≤�<�.

Now, �={1,2,4,3}.

It can be seen that inversion for this array will be ��={​​0,0,0,1} as:

  •  For i = 1, no positions satisfy   ����>���� and 1≤�<�.
  •  For i = 2, no positions satisfy   ����>���� and 1≤�<�.
  •  For i = 3,  no positions satisfy   ����>���� and 1≤�<�.
  •  For i = 4, j = 3 satisfy   ����>���� and 1≤�<�.

Thus, �={3,4,2,1} is a valid permutation.


Bitwise AND sumBitwise AND sum Solution(C++):-


#include <iostream>
#include <limits>
#include <vector>
using namespace std;
#define MAX_N 100000
void execTestcase(
int n,
vector<int>& arr,
vector<int>& iA,
vector<bool>& occupations
);
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
vector<int> arr, iA;
vector<bool> occupations;
arr.reserve(MAX_N);
iA.reserve(MAX_N);
occupations.reserve(MAX_N);
for (int i = 0; i < t; i++) {
int n;
cin >> n;
arr.resize(n);
iA.resize(n);
occupations.resize(n);
execTestcase(n, arr, iA, occupations);
}
return 0;
}
void execTestcase(
int n,
vector<int>& arr,
vector<int>& iA,
vector<bool>& occupations
) {
// scan IA and init occupasions
for (int i = 0; i < n; i++) {
int v;
cin >> v;
iA[i] = v;
occupations[i] = false;
}
// scan IR, calculate A and eventually fail if not a solution
bool isSolution = true;
for (int i = n - 1; i >= 0; i--) {
int iR;
cin >> iR;
arr[i] = n - iA[i] - iR;
isSolution = isSolution &&
(arr[i] > 0) &&
!occupations[(arr[i] + n) % n];
occupations[(arr[i] + n) % n] = true;
i *= isSolution;
}
cin.ignore(numeric_limits<streamsize>::max(), '\n');
// print solution
if (isSolution) {
for (auto a : arr) {
cout << a << " ";
}
cout << endl;
} else {
cout << "-1" << endl;
}
}



Tags:

Post a Comment

0 Comments