ORPERM-Editorial

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:

Bitwise OR operation

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();
}
3 Likes

Follow up for participants

How do you find the

  1. Smallest X?
  2. Largest X?
  3. Number of valid X?
  4. K^{th} smallest X?

Can you prove your solution for any of the above?

1 Like