EQBYXOR - Editorial

PROBLEM LINK:

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

Setter: Jeevan Jyot Singh
Tester: Harris Leung
Editorialist: Trung Dang

DIFFICULTY:

1507

PREREQUISITES:

XOR

PROBLEM:

JJ has three integers A, B, and N. He can apply the following operation on A:

  • Select an integer X such that 1 \le X \lt N and set A := A \oplus X. (Here, \oplus denotes the bitwise XOR operation.)

JJ wants to make A equal to B.
Determine the minimum number of operations required to do so. Print -1 if it is not possible.

EXPLANATION:

Let X = A \oplus B, and for the sake of editorialist’s sanity we decrease N by 1. We now want to achieve X from XOR-ing as few elements no greater than N as possible.

There are 4 cases:

  • X = 0. Answer is 0.
  • X \le N. Answer is 1.
  • \lfloor \log_2(X) \rfloor = \lfloor \log_2(N) \rfloor . Answer is 2. This semantically means the largest bit of X is equal to the largest bit of N, which means we can construct X by 2^{\lfloor \log_2(X) \rfloor} with some other value less than 2^{\lfloor \log_2(X) \rfloor}.
  • Otherwise. Answer is -1. This happens in the case where the largest bit of X is larger to the largest bit of N, which means we cannot create this largest bit by any means.

TIME COMPLEXITY:

Time complexity is O(1).

SOLUTION:

Setter's Solution
#ifdef WTSH
    #include <wtsh.h>
#else
    #include <bits/stdc++.h>
    using namespace std;
    #define dbg(...)
#endif

#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;

const long long INF = 1e18;

const int N = 1e6 + 5; 
    
// -------------------- Input Checker Start --------------------

long long readInt(long long l, long long r, char endd)
{
    long long x = 0;
    int cnt = 0, fi = -1;
    bool is_neg = false;
    while(true)
    {
        char g = getchar();
        if(g == '-')
        {
            assert(fi == -1);
            is_neg = true;
            continue;
        }
        if('0' <= g && g <= '9')
        {
            x *= 10;
            x += g - '0';
            if(cnt == 0)
                fi = g - '0';
            cnt++;
            assert(fi != 0 || cnt == 1);
            assert(fi != 0 || is_neg == false);
            assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
        }
        else if(g == endd)
        {
            if(is_neg)
                x = -x;
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(false);
            }
            return x;
        }
        else
        {
            assert(false);
        }
    }
}

string readString(int l, int r, char endd)
{
    string ret = "";
    int cnt = 0;
    while(true)
    {
        char g = getchar();
        assert(g != -1);
        if(g == endd)
            break;
        cnt++;
        ret += g;
    }
    assert(l <= cnt && cnt <= r);
    return ret;
}

long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
void readEOF() { assert(getchar() == EOF); }

vector<int> readVectorInt(int n, long long l, long long r)
{
    vector<int> a(n);
    for(int i = 0; i < n - 1; i++)
        a[i] = readIntSp(l, r);
    a[n - 1] = readIntLn(l, r);
    return a;
}

// -------------------- Input Checker End --------------------

void solve()
{
    int a = readIntSp(0, (1 << 30) - 1);
    int b = readIntSp(0, (1 << 30) - 1);
    int n = readIntLn(1, (1 << 30));
    int z = a ^ b;
    if(z == 0)
        cout << 0 << endl;
    else if(z < n)
        cout << 1 << endl;
    else
    {
        int msb = -1;
        for(int i = 30; i >= 0; i--)
        {
            if(z >> i & 1)
            {
                msb = i;
                break;
            }
        }
        if((1 << msb) < n)
            cout << 2 << endl;
        else
            cout << -1 << endl;
    }
}

int32_t main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0);
    int T = readIntLn(1, 1000);
    for(int tc = 1; tc <= T; tc++)
    {
        // cout << "Case #" << tc << ": ";
        solve();
    }
    readEOF();
    return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
const int N=2e5+5;
int n;
ll a[N];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int t;cin >> t;
	while(t--){
		ll a,b,n;cin >> a >> b >> n;
		ll z=1;
		while(z<n) z*=2;
		if((a^b)==0) cout << "0\n";
		else if((a^b)<n) cout << "1\n";
		else if((a^b)<z) cout << "2\n";
		else cout << "-1\n";
	}
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) {
        int a, b, n; cin >> a >> b >> n; --n;
        int x = a ^ b;
        if (x == 0) {
            cout << "0\n";
        } else if (x <= n) {
            cout << "1\n";
        } else if (n != 0 && __lg(x) == __lg(n)) {
            cout << "2\n";
        } else {
            cout << "-1\n";
        }
    }
}
3 Likes

What’s wrong with my code???

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define e cout<<"\n";
#define f(i,n) for(int i=0;i<n;i++)
int main(){
    int T;cin>>T;
    while(T--){
        ll a,b,n,x,m;
        cin>>a>>b>>n;
        
        if(a==b){
            cout<<0;e
        }
        else {
            
            m = n;
            a = a^b;
            int i=0,j=0;
            while(a){
                i++;
                a=a>>1;
            }
            while(n){
                j++;
                n=n>>1;
            }
            if(i<j){
                cout<<1;e
            }
            else if(i==j && (m&(m-1)!=0)){
                cout<<"2\n";
            }
            else{
                cout<<"-1\n";
            }
        }
        
    } 
return 0;
}

did not understand how the answer can be 2?

2 Likes

Suppose,
a = 7 → 111
b = 1 ->001
n = 5, n-1 = 4, → 100
We have to change 2 bits in a to b, we can’t choose 110 to XOR as it’s greater than n,
But we can choose 100 and 10, so two operations

4 Likes

My code will not print -1 .
1010 , 1001 both have 4th bit as most significant set bit so i==j is satisfied
and n!=power of 2, therefore the ans is 2.

Let’s say n is 21, if a ^ b is 20 then the output should be 1.
Your code output will be 2.

Suppose a = 7, b = 18, a ^ b = 21 and N = 17.

Since N is lesser than a ^ b you can’t choose x = 21 and get b in one operation.

In first operation, choose x = 16 (nearest power of 2 to (a ^ b), and it should be lesser than N, that’s why we are checking that log step) and xor it with a, a will become 21.
In 2nd operation choose x = 7 and xor it with a, a will become 18.

Dry run this case, you will get the intuition.

1 Like

bhava discord id dena tuzi . I have some doubts regarding my solution

test()
{
    ll a,b,n;cin>>a>>b>>n;
    ll xr=a^b;
    ll rxr=rightSetBit(xr),rn=rightSetBit(n-1);
    if(a==b)
        cout<<0<<endl;
    if(b==0)
        cout<<1<<endl;
    else if(n-1>=xr)
        cout<<1<<endl;
    else if(rxr==rn)
        cout<<2<<endl;
    else
        cout<<-1<<endl;
    
}

Can some one tell me which test case am i missing i was able to get partial marks for this.

can anyone explain me why the minimum operation can’t be greater than 2 . also how are we checking that minimum operation is 2 . ??

1 Like

IMPORTANT OBSERVATION :

Decimal → 2^n > (2^n)-1
Binary → 1+(n zeros) > (n ones)

Example :
Decimal = 8
Binary = 1000
Here, 1000 > 0111

But, 1000 == 1000, and 1000 < 1001, of course in binary,
That says that if most significant bit of (a^b) differ, and is equal to most significant bit in n, then in 1 operation we can change the most significant bit only, and in another operation we can change all bits less than most significant one… so total 2 operations at max

I actually just hard coded,

#include <bits/stdc++.h>
#define int long long int

void solve(){
    int a, b, n;
    std::cin >> a >> b >> n;
    int num = 1, val = 0;
    std::vector <int> dp(32);
    for(int i=0; i<32; i++){
        if((a&1) != (b&1)){
            dp[i] = 1;
            val = num;
        }
        a >>= 1;
        b >>= 1;
        num <<= 1;
    }
    if(val >= n){
        std::cout << "-1\n";
        return;
    }
    int cnt = 0, sum = 0;
    for(int i=31; i>=0; i--){
        if(dp[i]){
            if(sum + (1<<i) >= n){
                cnt += 1;
                sum = 0;
            }
            sum += (1<<i);
        }
    }
    std::cout << (sum == 0 ? cnt : cnt+1) << "\n";
}
     
signed main() {

    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // ONLINE_JUDGE

    int t = 1;
    std::cin >> t;
    while(t--){
        solve();
    }
}
1 Like

Discord nahiye bhava, ithech v4 ki

Let a = 7, b = 1, n = 5.

let’s find x such that a ^ x = b
So, by using xor property we get x = a ^ b

Now, let say x > = n . So, we can’t use x directly.

let x = d1 ^ d2
So, if d1 < n && d2 < n then, we can replace x by ( d1 ^ d2 )
a ^ ( d1 ^ d2 ) = b

So, all we have to find is, if there exist a pair ( d1 , d2 ) such that d1 < n && d2 < n

So, to find that we simply have to see if n-1 and x have same base of not ,because
the largest set bit of any of the d1 or d2 is equal to the largest set bit of x if
d1 ^ d2 =x.
Ex : let x =6 —> 110 if we want a (d1, d2) for x then think of it how we can generate it?
we must have the leftmost bits of d1 d2 be 0 and 1 such that 0 ^ 1= 1.
here d1 =4–>100 d2 = 2–>010 .
So, we have to do

  1. a = a ^ d1
  2. a ^ d2 So, two operations… ans = 2

If the base of x is greater than n-1 , then we know that one of the d1 or d2 have the largest set bit equal to the largest set bit of x .
means one of d1 or d2 will be greater than n-1. So, we have no solution.

sorry for bad english.

2 Likes

are voice channel madhe sangitle aste tar clear zale aste . but still taku ka ithe code jo 30 points sathi accept zala hota. Mala mazi mistake mahitiye but ti resolve kashi karu te kalat nahiye

1 Like

Your logic is correct. i think the problem is here , rn=rightSetBit(n-1) let say x=1 and n=1. now answer should be -1, as x>n-1. but when you call for rightsetbit (depends on your implementation) it may be returning 0. and the rightmost set bit of x=1 is also zero, return 2 which is wrong.

Even though my code is running , there is a heavy flaw in constraints
In statement it is written 1 ≤ X < N , see the testcase
1
3 2 1
a=3 b=2 n=1
according to equality x=1 is not possible ,
also later in editorial it is written X≤N. Answer is 1.
but judge is taking -1.
This is self contradicting.

I feel like that’s a typo because everything else checks out

Hey, in the editorial I have decreased N by 1 at the start.

1 Like

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
int t;
cin>>t;
while(t–){
int a,b,n;
cin>>a>>b>>n;
a=a^b;
if(a==0)
cout<<0;
else {
n–; //X is till n-1
int m=n;
int z=a;
int i=0,j=0;
while(a){
i++;
a=a>>1;
}
while(n){
j++;
n=n>>1;
}
if(i>j)
cout<<-1;
else if(z<=m)
cout<<1;
else
cout<<2;
}
cout<<"\n";
}
return 0;
}
i==j does not always implies that ans could be 2.Eg-a=101 , n=110 . When a<=n then ans will be 1 otherwise it will be 2 .Eg a=110 ,b=101.

Can Someone explain tester’s solution.