PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Sai Suman Chitturi
Tester: Satyam, Utkarsh Gupta
Editorialist: Devendra Singh
DIFFICULTY:
To be calculated
PREREQUISITES:
PROBLEM:
Chef has a sequence A of N integers. He picked a non-negative integer X and obtained another sequence B of N integers, defined as B_i = A_i \mid X for each 1 \leq i \leq N. Unfortunately, he forgot X, and the sequence B got jumbled.
Chef wonders what the value of X is. He gives you the sequence A and the jumbled sequence B. Your task is to find whether there is a non-negative integer X such that there exists a permutation C of B satisfying the condition C_i = A_i \mid X for each 1 \leq i \leq N.
If there are multiple such X, find any of them.
Note: Here | represents the bitwise OR operation.
EXPLANATION:
Let us look at each bit one at a time. If the i^{th} bit is set to 1 in a elements of the array A and set to 1 in b elements of the array B. Then these two conditions are necessary for an answer to exist:
- b\geq a
Why?
( 0 | 1 = 1)
Suppose the i^{th} bit is set to 1 in the binary representation of X, then it will be set to 1 in all numbers in array B or else it will be set to 1 in exactly same number of elements of array B as that of array A in which it was set to 1.
\implies b\geq a
- (a < b) \implies b = N
Why?
( 0 | 0 = 0)
Suppose the i^{th} bit is set to 0 in the binary representation of X, then it will be set to 1 in exactly same number of elements in array B as that of array A in which it was set to 1. Therefore a<b means i^{th} bit is set to 1 in X which implies that it has to be set to 1 in all values of array B as (0 | 1 = 1 ) as well as (1 | 1 = 1).
\implies\: (a < b)\rightarrow b = N
But these are necessary conditions not sufficient.
Example
Let A=[1,2] and B=[0,3] necessary conditions are true but an answer does not exist.
Maintain the count of each bit in array A and array B.Initialize X=0. Calculate the value of X by iterating on the bits and verifying the necessary conditions. If count of i^{th} bit in B = N add 2^i to X.(This value X is same as taking bitwise\: \& of all values of array B)
Lastly check whether the calculated X is correct by generating Array B' where B'_i = A_i|X.Now if array B is same as B' then X is an answer otherwise output -1.
TIME COMPLEXITY:
O(Nlog(N)) or O(Nlog(N)+Nlog(max(A_i))) for each test case.
SOLUTION:
Setter's solution
/**
*
* Author : Sai Suman Chitturi
* Handle : suman_18733097
*
**/
#include <bits/stdc++.h>
using namespace std;
void solve() {
int N = 0;
cin >> N;
vector<int> a(N), b(N);
for(int i = 0; i < N; i++) {
cin >> a[i];
}
for(int i = 0; i < N; i++) {
cin >> b[i];
}
int X = b[0];
for(int i = 0; i < N; i++) {
X &= b[i];
}
for(int i = 0; i < N; i++) {
a[i] |= X;
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
for(int i = 0; i < N; i++) {
if(a[i] != b[i]) {
cout << -1 << '\n';
return;
}
}
cout << X << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int t = 1;
cin >> t;
for(int test = 0; test < t; test++) {
solve();
}
return 0;
}
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
int n;
cin >> n;
vll a(n), b(n);
int bita[30], bitb[30];
memset(bita, 0, sizeof(bita));
memset(bitb, 0, sizeof(bitb));
for (int i = 0; i < n; i++)
{
cin >> a[i];
for (int j = 0; j < 30; j++)
if (a[i] & (1 << j))
bita[j]++;
}
for (int i = 0; i < n; i++)
{
cin >> b[i];
for (int j = 0; j < 30; j++)
if (b[i] & (1 << j))
bitb[j]++;
}
int x = 0;
for (int i = 0; i < 30; i++)
{
if (bitb[i] < bita[i] || (bita[i] < bitb[i] && bitb[i] != n))
{
x = -1;
break;
}
if (bitb[i] == bita[i])
continue;
x += (1 << i);
}
sort(all(b));
for (int i = 0; i < n; i++)
a[i] |= x;
sort(all(a));
if (a == b)
cout << x << '\n';
else
cout << -1 << '\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
cin >> test;
while (test--)
sol();
}