PROBLEM LINK:
Author: Nitish Gupta
Tester: Raja Vardhan Reddy
Editorialist: Akash Bhalotia
DIFFICULTY:
Easy
PREREQUISITES:
PROBLEM:
Given two arrays A and B, find if it is possible to reorder B into some sequence C, such that (A_1 \oplus C_1) = (A_2 \oplus C_2) = (A_3 \oplus C_3) = \ldots = (A_N \oplus C_N) .
HINTS:
Not the full solution. Just some hints to help you if you are stuck at some point. As soon as you encounter a hint that you had not thought of, go back to solving the problem.
Hint 1:
Let x be any number.
(x \oplus x) =0
(x \oplus x \oplus x) = (0 \oplus x) = x
All (A_1 \oplus C_1) = (A_2 \oplus C_2) = (A_3 \oplus C_3) = \ldots = (A_N \oplus C_N) .
N is odd.
Hint 2:
If (A_i \oplus C_i) =x,
and we have A_i and x, how can we obtain the corresponding C_i from this?
Hint 3:
If we have a sequence C, which satisfies:
(A_1 \oplus C_1) = (A_2 \oplus C_2) = (A_3 \oplus C_3) = \ldots = (A_N \oplus C_N) ,
How will you check if C is a permutation of B?
QUICK EXPLANATION:
show
Xor all elements in arrays A and B together to obtain the value of (A_i \oplus C_i). Xor this value with every A_i to obtain the corresponding value in the solution permutation, C_i. Check if C is indeed a permutation of B. If it is, output it, else, output -1.
EXPLANATION:
show
In the solution permutation C, all
(A_1 \oplus C_1) = (A_2 \oplus C_2) = (A_3 \oplus C_3) = \ldots = (A_N \oplus C_N) \ldots (1)
Is there a way for us to obtain this value: (A_i \oplus C_i) ?
Let’s look at the some properties of xor which will be useful for us to solve the problem.
- (x \oplus x) =0
- (x\oplus0) = (0 \oplus x) = x
So,
(x \oplus x \oplus x) = (0 \oplus x) = x
(x \oplus x \oplus x \oplus x) = (x \oplus x) = 0
(x \oplus x \oplus x \oplus x \oplus x) = (0 \oplus x) = x,
.
.
.
and so on.
In particular, on XORing even number of equal numbers with one another, we obtain 0, while for an odd number of equal numbers, we get that number itself.
Observe the problem constraints. N is odd.
(A_1 \oplus C_1) = (A_2 \oplus C_2) = (A_3 \oplus C_3) = \ldots = (A_N \oplus C_N)
Let (A_i \oplus C_i) = x.
Each (A_i \oplus C_i) is equal. And the number of terms is odd.
\implies (A_1 \oplus C_1) \oplus (A_2 \oplus C_2) \oplus (A_3 \oplus C_3) \oplus \ldots \oplus (A_N \oplus C_N) = x
\implies (A_1 \oplus A_2 \oplus A_3 \oplus A_4 \ldots \oplus A_N) \oplus (C_1 \oplus C_2 \oplus C_3 \oplus C_4 \ldots \oplus C_N) = x
Xor is commutative and associative, and so, the order in which we perform the xor operations doesn’t affect the result.
Since C is simply a permutation, or an arrangement of B
\implies (A_1 \oplus A_2 \oplus A_3 \oplus A_4 \ldots \oplus A_N) \oplus (B_1 \oplus B_2 \oplus B_3 \oplus B_4 \ldots \oplus B_N) = x
Thus, if it’s indeed possible to reorder B to some C which satisfies (1), we can obtain the value of (A_i \oplus C_i) by XORing all A_i and all B_i together.
Xor has this awesome property, where, if
(P \oplus Q = R), then
(Q \oplus R = P), and (R \oplus P = Q)
Thus, as (A_i \oplus C_i) =x,
We can obtain the corresponding C_i 's by XORing the A_i 's with x, i.e.,
C_i = A_i \oplus x
Now, we just need to check if it’s indeed possible to reorder the original array B in some way to obtain this solution array C, i.e., if this C we’ve obtained is a permutation of B.
There are a couple of ways to do this. One way, which we’ve used in our implementation, is to sort the arrays C and B and compare their corresponding elements. If every corresponding element is same, then this solution C is indeed a permutation of B, and we’ve solved the problem. Else, there is no valid way to reorder the sequence B to satisfy (1), and we’ll output -1.
Thus, to solve the problem,
- Xor all A and B, to obtain the value of (A_i \oplus C_i). Let’s call this x.
- Xor this x with every A_i, to obtain the solution permutation C.
- Now we need to check if this permutation can be obtained from B. If it can, output it. Else output -1.
The setter’s solution below involves a similar approach, but a different way to find x, which indirectly uses the same method, explained above:
show
For each bit position from 0 to 20 (as A_i \leq 10^6 and 2^{20} is greater than 10^6) , we count the number of elements in A which have that bit set. We do the same for B.
Each of these 21 bits will either be set or unset in x.
If a bit k is set in p numbers in A and in q numbers in B, (p=q) then we will pair the numbers in A whose k^{th} bit is set with those in B whose k^{th} bit is also set. Thus, the k^{th} bit will be unset in x.
On the other hand, if (p\not=q) and (p+q=N), we’ll pair the numbers in A which have the k^{th} bit set with those in B which don’t have it set, and vice versa. Thus, the k^{th} bit will be set in x.
If there exists a bit k for which neither (p=q), nor (p+q=N), then we won’t be able to arrange B in a way such that this bit remains in the same state (set/unset) for all x's. Thus, in such a case, a valid solution doesn’t exist.
SOLUTIONS:
Setter
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
#define U 998244353
#define N 1000005
#define int long long
#define sz(c) (int)c.size()
#define fr first
#define ll long long
#define sc second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define rep(i,a,n) for(int i=a ; i<n ; i++)
#define r0 return 0;
#define endl '\n'
#define INF (int)1e15
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
std::cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
signed main()
{
ios_base::sync_with_stdio(0);
int TESTS=1;
cin>>TESTS;
while(TESTS--)
{
int n;
cin >> n;
vector<int> a(n),b(n);
rep(i,0,n) cin >> a[i];
rep(i,0,n) cin >> b[i];
int cnta[21]={};
int cntb[21]={};
rep(i,0,n){
rep(j,0,21){
if(a[i]&(1<<j)) cnta[j]++;
}
}
rep(i,0,n){
rep(j,0,21){
if(b[i]&(1<<j)) cntb[j]++;
}
}
int k = 0;
bool f = 1;
rep(j,0,21){
if(cnta[j]==cntb[j]) continue;
else if(cnta[j]+cntb[j]==n) k += (1<<j);
else f = 0;
}
vector<int> bn(n);
rep(i,0,n) bn[i] = a[i]^k;
vector<int> bns = bn;
sort(all(bns));
sort(all(b));
if(bns!=b){
cout << -1 << endl;
continue;
}
for(auto j:bn) cout << j << " ";
cout<<endl;
}
}
Tester
//raja1999
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
//std::ios::sync_with_stdio(false);
vector<pii>vec;
int a[100005],b[100005],ans[100005];
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n,i,val,fl=0;
cin>>n;
vec.clear();
for(i=0;i<n;i++){
cin>>a[i];
}
for(i=0;i<n;i++){
cin>>b[i];
}
val=0;
for(i=0;i<n;i++){
val=(val^a[i]);
val=(val^b[i]);
}
for(i=0;i<n;i++){
vec.push_back(make_pair((a[i]^val),i));
}
sort(vec.begin(),vec.end());
sort(b,b+n);
for(i=0;i<n;i++){
if(b[i]!=vec[i].first){
fl=1;
break;
}
}
if(fl){
cout<<-1<<endl;
}
else{
for(i=0;i<n;i++){
ans[vec[i].second]=vec[i].first;
}
for(i=0;i<n;i++){
cout<<ans[i]<<" ";
}
cout<<endl;
}
}
return 0;
}
Editorialist
CodeChef: Practical coding for everyone
//created by Whiplash99
import java.io.*;
import java.util.*;
class A
{
public static void main(String[] args) throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int i,N;
int T=Integer.parseInt(br.readLine().trim());
StringBuilder sb=new StringBuilder();
while(T-->0)
{
N=Integer.parseInt(br.readLine().trim());
int A[]=new int[N];
int B[]=new int[N];
String s[]=br.readLine().trim().split(" ");
for(i=0;i<N;i++)
A[i]=Integer.parseInt(s[i]);
s=br.readLine().trim().split(" ");
for(i=0;i<N;i++)
B[i]=Integer.parseInt(s[i]);
int X=0;
for(i=0;i<N;i++) //obtaining the value of X
X^=A[i]^B[i];
int C[]=new int[N];
for(i=0;i<N;i++) //obtaining the value of C[i]
C[i]=A[i]^X;
Arrays.sort(C);
Arrays.sort(B);
for(i=0;i<N;i++) //is C indeed a permutation of B?
{
if (B[i] != C[i])
break;
}
if(i<N) // no valid solution exists
sb.append(-1).append("\n");
else
{
for (i = 0; i < N; i++) // Output C[i]
sb.append(A[i]^X).append(" ");
sb.append("\n");
}
}
System.out.println(sb);
}
}
Feel free to share your approach if it differs. You can ask your doubts below. Please let me know if something’s unclear. I would LOVE to hear suggestions 