ORXOR-Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setters: Tejas Pandey,Utkarsh Gupta
Tester: Manan Grover, Abhinav Sharma
Editorialist: Devendra Singh

DIFFICULTY:

2543

PREREQUISITES:

Bitwise operations

PROBLEM:

Chef has an array A of length N such that A_i = i.

In one operation, Chef can pick any two elements of the array, delete them from A, and append either their bitwise XOR or their bitwise OR to A.

Note that after each operation, the length of the array decreases by 1.

Let F be the final number obtained after N-1 operations are made. You are given an integer X, determine if you can get F=X via some sequence of operations.

In case it is possible to get F = X, print the operations too (see the section Output format for more details), otherwise print -1.

EXPLANATION:

Let us handle the case when N=2 separately, when N is 2 only possible value of X is 3 as both XOR and OR of 1 and 2 result in 3. So if N is 2 and x!=3, answer is -1 otherwise both XOR or OR of 1 and 2 are acceptable answers.
If some bit in X is set to 1 which is not set to 1 in any number till N then there is no possible way to attain such X , Hence answer in this case is -1 too.
If N is a power of two then the most significant bit in N is set to 1 in only one number and is 0 in all other numbers less than N hence whether you take XOR with this number or OR with this number, this bit has to be set to 1 in X . If it is unset in X then the answer is -1

Otherwise it is always possible to construct the answer:
Consider the construction take OR of all the elements in the array which are not a power of 2.
This way at least all the bits upto most significant bit of N( excluding it) will be set in the the number obtained.

Proof

If N is a power of 2.Then since we take OR with (2^{msb})-1. It sets all the bits upto msb of N in the number obtained.
Otherwise we take OR of N with 2^{msb}-1 and this sets all the bits upto msb of N in the number obtained.

Now iterate on the bits from i=0 to the most significant bit of N. If it is set in X we take OR with 2^i present in the array otherwise we take XOR with 2^i present in the array.
(Since if N is a power of 2 then X will have most significant bit of N set, therefore we will take OR with N in the end.)
Thus we can get the final value same as X by this method.

TIME COMPLEXITY:

O(N) or O(Nlog(N)) depending upon implementation for each test case.

SOLUTION:

Setter's solution
#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n, x;
        cin >> n >> x;
        int bk = 0;
        for(int i = 20; i > 0; i--) {
            if(n&(1LL<<i)) {
                bk = (1LL<<(i + 1));
                break;
            }
        }
        if((n == 2 && x != 3) || ((n&(n - 1)) == 0 && (x&n) == 0) || x >= bk) {
            cout << "-1\n";
            continue;
        }
        if(n == 2) {
            cout << "1 1 2\n";
            continue;
        }
        set<int> s1, s2;
        for(int i = 1; i <= n; i++) s1.insert(i);
        for(int i = 0; i < 20; i++) {
            if((1LL<<i) > n) break;
            if((x&(1LL<<i)) == 0) {
                s1.erase((1LL<<i));
                s2.insert((1LL<<i));
            }
        }
        int n1 = 0, n2 = 0;
        if(s1.size()) {
            n1 = (*(s1.begin()));
            s1.erase(s1.begin());
            while(s1.size()) {
                int now = (*(s1.begin()));
                cout << "1 " << n1 << " " << now << "\n";
                n1 |= now;
                s1.erase(s1.begin());
            }
        }
        if(s2.size()) {
            n2 = (*(s2.begin()));
            s2.erase(s2.begin());
            while(s2.size()) {
                int now = (*(s2.begin()));
                cout << "1 " << n2 << " " << now << "\n";
                n2 |= now;
                s2.erase(s2.begin());
            }
        }
        if(n1 > 0 && n2 > 0) cout << "2 " << n1 << " " << n2 << "\n";
    }
}

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, x, msbx, msbn;
    cin >> n >> x;
    map<int, bool> ispow2;
    if (n == 2 && x != 3)
    {
        cout << -1 << '\n';
        return;
    }
    else if(n==2 && x==3)
    {
        cout<<1<<' '<<1<<' '<<2<<'\n';
        return ;
    }
    for (int i = 0; i < 20; i++)
    {
        ispow2[1 << i] = true;
        if ((1 << i) & n)
            msbn = i;
        if ((1 << i) & x)
            msbx = i;
    }
    if (msbx > msbn)
    {
        cout << -1 << '\n';
        return;
    }
    if (!ispow2[n] || (x & n))
    {
        int val = 0;
        for (int i = 1; i <= n; i++)
        {
            if (!ispow2[i])
            {
                if (i > 3)
                    cout << 1 << ' ' << i << ' ' << val << '\n';
                val |= i;
            }
        }
        for (auto y : ispow2)
        {
            if (y.F > n || !y.S)
                continue;
            if (x & (y.F))
            {
                cout << 1 << ' ' << y.F << ' ' << val << '\n';
                val |= y.F;
            }
            else
            {
                cout << 2 << ' ' << y.F << ' ' << val << '\n';
                val ^= y.F;
            }
        }
    }
    else
    {
        cout << -1 << '\n';
    }

    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int test = 1;
    cin >> test;
    while (test--)
        sol();
}

5 Likes

i am getting WA for 2 test cases, maybe my code is missing some case please help!!!
APPROACH
according to me min possible number we can get is the bitwise xor of all and max possible is bitwise or of all number
so if x isn’t fall under this max min range then ans = -1
otherwise we can find the ans by take xor of max with x this will give us the number we need to xor so first take ans will be bitwise or of all (except the number we need to xor) than xor the rest of the number
for example
n = 4,x = 6
max = 1 | 2 | 3 | 4 = 7
min = 1 xor 2 xor 3 xor 4 = 4
so according to the approach
number we need to xor = 7 xor 6 = 1
therefore number we need to or = 2 3 4

Thanks

#include<bits/stdc++.h>

#define nline "\n"
#define ll long long
#define pb push_back
#define umap unordered_map
#define mod  1000000007

using namespace std;

void vprint(vector<int> v){
	for(auto &x:v) cout<<x<<" ";
	cout<<nline;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int t;cin>>t;
    while(t--){

//start


    int n;cin>>n;
    int x;cin>>x;
    int mi = 0,mx = 0;
    vector<int> v(n,0);
    for (int i = 0; i < n; ++i)
    {
    	mx = mx | (i+1);
    	mi = mi ^ (i+1);
    	v[i] = i+1;
    }
    if(x<mi or x>mx){
    	cout<<-1<<nline;
    	continue;
    }
    int val = mx^x;
    int vv = 1;
    while(val){
    	if(val%2) v[vv-1] = v[vv-1]*(-1);
    	val/=2;
    	vv*=2;
    }
    sort(v.begin(), v.end(),greater<int>());
    // vprint(v);
    int temp = 0;
    for (int i = 0; i < n-1; ++i)
    {
    	if(v[i+1] > 0) cout<<"1 ";
    	else cout<<"2 ";
    	if(v[i] > 0){
    		temp = temp | v[i];
    	}else{
    		temp = temp ^ abs(v[i]);
    	}
    	cout<<temp<<" "<<abs(v[i+1])<<nline;
    }

//end
    }

    return 0;
}


Did you got wrong answer in 2nd tc??