XORRY1 - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: munch_01
Tester: raysh_07
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You’re given an integer X.
Find any pair (A, B) such that:

  • 0 \leq A \leq B \leq X
  • A\oplus B = X
  • (B-A) is as small as possible across all pairs satisfying the first two conditions.

EXPLANATION:

Given that we’re dealing with bitwise XOR, it’s useful to look at the binary representation of X.
So, let

X = 2^{x_1} + 2^{x_2} + \ldots + 2^{x_k}

where x_1 \lt x_2 \lt\ldots\lt x_k are the set bits in the binary representation of X.

Now, for A\oplus B = X to hold:

  • Each x_i should be set in exactly one of A and B, not both.
  • Each bit that’s not one of the x_i should be set in either both A and B, or neither of them.

Further, the condition 0 \leq A \leq B \leq X means that:

  • Any bit higher than x_k isn’t allowed to be set in either A or B (otherwise they’d exceed X).
  • Bit x_k must be set in B, to ensure A \leq B.

Now that x_k is decided, we need to fix the other k-1 of them.
Let’s just give them all to A, making it as large as possible - after all, our aim is to minimize B-A.

That is, we have B = 2^{x_k} and A = 2^{x_1} + 2^{x_2} + \ldots + 2^{x_{k-1}}.
This is a valid solution, because:

  • As noted earlier, any bit which isn’t one of the x_i should be set in both A and B, or neither of them.
    As of now, they’re all unset in both: and setting them won’t change the difference since both A and B increase by the same value.
  • Moving one of the x_i from A to B is clearly only going to make the difference larger, given that A decreases while B increases.

TIME COMPLEXITY:

\mathcal{O}(\log X) per testcase.

CODE:

Tester's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

struct input_checker {
    string buffer;
    int pos;

    const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    const string number = "0123456789";
    const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    const string lower = "abcdefghijklmnopqrstuvwxyz";

    input_checker() {
        pos = 0;
        while (true) {
            int c = cin.get();
            if (c == -1) {
                break;
            }
            buffer.push_back((char) c);
        }
    }

    int nextDelimiter() {
        int now = pos;
        while (now < (int) buffer.size() && !isspace(buffer[now])) {
            now++;
        }
        return now;
    }

    string readOne() {
        assert(pos < (int) buffer.size());
        int nxt = nextDelimiter();
        string res;
        while (pos < nxt) {
            res += buffer[pos];
            pos++;
        }
        return res;
    }

    string readString(int minl, int maxl, const string &pattern = "") {
        assert(minl <= maxl);
        string res = readOne();
        assert(minl <= (int) res.size());
        assert((int) res.size() <= maxl);
        for (int i = 0; i < (int) res.size(); i++) {
            assert(pattern.empty() || pattern.find(res[i]) != string::npos);
        }
        return res;
    }

    int readInt(int minv, int maxv) {
        assert(minv <= maxv);
        int res = stoi(readOne());
        assert(minv <= res);
        assert(res <= maxv);
        return res;
    }

    long long readLong(long long minv, long long maxv) {
        assert(minv <= maxv);
        long long res = stoll(readOne());
        assert(minv <= res);
        assert(res <= maxv);
        return res;
    }

    auto readInts(int n, int minv, int maxv) {
        assert(n >= 0);
        vector<int> v(n);
        for (int i = 0; i < n; ++i) {
            v[i] = readInt(minv, maxv);
            if (i+1 < n) readSpace();
        }
        return v;
    }

    auto readLongs(int n, long long minv, long long maxv) {
        assert(n >= 0);
        vector<long long> v(n);
        for (int i = 0; i < n; ++i) {
            v[i] = readLong(minv, maxv);
            if (i+1 < n) readSpace();
        }
        return v;
    }

    void readSpace() {
        assert((int) buffer.size() > pos);
        assert(buffer[pos] == ' ');
        pos++;
    }

    void readEoln() {
        assert((int) buffer.size() > pos);
        assert(buffer[pos] == '\n');
        pos++;
    }

    void readEof() {
        assert((int) buffer.size() == pos);
    }
};

input_checker inp;

const int T = 1e5;
const int N = 1e9;

void Solve() 
{
    int n = inp.readInt(1, N); inp.readEoln();

    int a = 0, b = 0;
    int cnt = 0;
    for (int i = 31; i >= 0; i--) if (n >> i & 1){
        cnt++;
        if (cnt == 1) a += 1 << i;
        else b += 1 << i;
    }
    swap(a, b);

    cout << a << " " << b << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    t = inp.readInt(1, T);
    inp.readEoln();

    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }

    inp.readEof();

    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}
Editorialist's code (Python) 
for _ in range(int(input())):
    x = int(input())
    a, b = 0, 0
    for i in range(30):
        if x & 2**i:
            a += b
            b = 2**i
    print(a, b)
2 Likes
2

include <bits/stdc++.h>
using namespace std;

int main()
{
int T;
cin>>T;
while(T–)
{
int X;
cin>>X;

    vector<vector<int>>subset;
    
    for(int i=0;i<X;i++)
    {
        
        for(int j=i+1;j<X;j++)
        {
            vector<int>ans;
            ans.push_back(i);
            ans.push_back(j);
            subset.push_back(ans);
        }
    }
    vector<vector<int>>XOR;
    for(int i=0;i<subset.size();i++)
    {
        if(subset[i][0]^subset[i][1]==X)
        XOR.push_back(subset[i]);
    }
    
    int diff = XOR.empty() ? 0 : XOR[0][1] - XOR[0][0];
    vector<vector<int>>finalans;
    for(int i=1;i<XOR.size();i++)
    {
        int currentdiff=XOR[i][1]-XOR[i][0];
        if(diff>currentdiff)
        {
            diff=currentdiff;
            finalans.clear();
            finalans.push_back(XOR[i]);
        }
        else if(diff==currentdiff) 
        {
            finalans.push_back(XOR[i]);
        }
        
    }
    
    for(int i=0;i<finalans.size();i++) 
    {
        for(int j=0;j<finalans[i].size();j++) 
        {
            cout<<finalans[i][j]<<" ";
        }
        cout<<endl;
    }
    
}

}

whats wrong in my above code?

3

What’s wrong if i greedily i.e alternatively assign 1s to A and B keeping position of 0s same??

4

It doesn’t minimize the difference of B-A.
For example if X = 7 = (111)_2, alternating the ones gets you B = (101)_2 = 5 and A = (010)_2 = 2, but it’s better to have 4 and 3.

1 Like
5

We can try using this code too :
Python Code :

import math

t = int(input())

while t > 0:
x = int(input())

nearest_power_of_2 = 2 ** int(math.log2(x))

a = x - nearest_power_of_2
b = nearest_power_of_2

print(a, b)

t -= 1
6

what is wrong with this code
include
include
include

using namespace std;

int main() {
int t;
cin >> t;

while (t--) {
    int x;
    cin >> x;

    vector<pair<int, int>> pairs;
    pair<int, int> min_pair = {0, x};
    int min_diff = INT_MAX;

    int low = 0;
    int high = x;

    while (low < high) {
        pairs.push_back({low, high});
        low++;
        high--;
    }

    for (auto& it : pairs) {
        int current_diff = it.second - it.first;
        if ((it.first ^ it.second) == x && current_diff < min_diff) {
            min_diff = current_diff;
            min_pair = {it.first, it.second};
        }
    }

    cout << min_pair.first << " " << min_pair.second << endl;
}

return 0;

}