SIMPLE_XOR - Editorial

editorial
, , ,
1

PROBLEM LINK:

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

Setter: Devendra Singh
Tester: Harris Leung
Editorialist: Trung Dang

DIFFICULTY:

1362

PREREQUISITES:

None

PROBLEM:

You are given two integers L and R (L+3 \le R). Output any four distinct integers between L and R (inclusive) such that their bitwise XOR is zero.

If more than one such quadruple exists, you may output any of them. If no such quadruple exists, print −1 instead.

EXPLANATION:

We have the following observation:

  • If A is even, then A \oplus (A + 1) = 1.
  • Therefore, if A even, then A \oplus (A + 1) \oplus (A + 2) \oplus (A + 3) = 1 \oplus 1 = 0.

With this observation, we have the following greedy algorithm:

  • Try whether L \oplus (L + 1) \oplus (L + 2) \oplus (L + 3) = 0 or not. If yes, output these four numbers.
  • If not, there are two cases:
    • If R = L + 3, then there can’t be any other four distinct numbers between L and R. We output -1.
    • Else, we know that L must be odd. Then, we know that (L + 1) \oplus (L + 2) \oplus (L + 3) \oplus (L + 4) = 0, so we output these four numbers.

TIME COMPLEXITY:

Time complexity is O(1) per test case.

SOLUTION:

Setter'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 l, r;
    cin >> l >> r;
    if ((r - l) > 3 || l % 2 == 0)
    {
        if (l % 2 == 0)
            cout << l << ' ' << l + 1 << ' ' << l + 2 << ' ' << l + 3 << '\n';
        else
            cout << l + 1 << ' ' << l + 2 << ' ' << l + 3 << ' ' << l + 4 << '\n';
    }
    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();
}
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=2e6+1;
int main(){
	ios::sync_with_stdio(false);
	int t;cin >> t;
	while(t--){
		ll l,r;
		cin >> l >> r;
		if(l%2==0) cout << l << ' ' << l+1 << ' ' << l+2 << ' ' << l+3 << '\n';
		else if(r==l+3) cout << "-1\n";
		else{
			l++;
			cout << l << ' ' << l+1 << ' ' << l+2 << ' ' << l+3 << '\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 l, r; cin >> l >> r;
        if ((l ^ (l + 1) ^ (l + 2) ^ (l + 3)) == 0) {
            cout << l << " " << l + 1 << " " << l + 2 << " " << l + 3 << '\n';
        } else if (l + 4 <= r) {
            cout << l + 1 << " " << l + 2 << " " << l + 3 << " " << l + 4 << '\n';
        } else {
            cout << "-1\n";
        }
    }
}
6 Likes