# XOR_ORDER - Editorial

Author: youknow_who
Tester: yash_daga
Editorialist: iceknight1093

TBD

# PREREQUISITES:

Bitwise operations

# PROBLEM:

Given distinct integers A, B, C, find any 0 \leq X \lt 2^{30} such that

A\oplus X \lt B\oplus X \lt C\oplus X

or claim that none exist.

# EXPLANATION:

Let’s just look at A and B first.

Looking at their binary representations, let k be the highest bit where they differ.
For example, if A = 28 = 11100_2 and B = 26 = 11010_2, we’d have k =2, because the first time the binary representations differ is at 2^2 = 4.

Let a_k be the value of this bit in A, and b_k be the value of this bit in B.
The direction of inequality between A and B is completely defined by what a_k and b_k are; in particular, we want a_k = 0 and b_k = 1 to hold.

So,

• if a_k = 0 and b_k = 1, then the k-th bit of X must be 0
• if a_k = 1 and b_k = 0, then the k-th bit of X must be 1

This fixes one of the bits of X.

Do the same for the pairs (B, C) and (A, C) as well, giving us three conditions on the bits of X.

If any of these conditions conflict (for example, if (A, B) says that the 10-th bit must be 0 while (B, C) says that it must be 1), no answer is possible; so print -1.

Otherwise, fix these three bits of X, and the others can be left as zeros since there are no constraints on them; so this gives us a valid value of X.

The fact that at most three bits really matter also gives us a rather funny randomized solution: generate a random X between 0 and 2^{30} - 1 and check if it satisfies the condition; and if it doesn’t, continue generating X till you find a valid one.
If no valid X is found after several attempts (say, 100 attempts), the answer is -1.
Do you see why this works with high probability?

# TIME COMPLEXITY

\mathcal{O}(1) per test case.

# CODE:

Setter's code (C++)
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define all(x)      x.begin(), x.end()
#define pb          push_back
#define sz(x)       (int)(x.size())
#define ll          long long
#define fi          first
#define se          second
#define lbd         lower_bound
#define ubd         upper_bound

template <typename T>
using ordered_set = tree<T, null_type,
less<T>, rb_tree_tag,
tree_order_statistics_node_update>;

const int MOD = 1e9 + 7;
const double eps = 1e-10;
const long long INF = 1e18;
const int N = 2e5 + 10;

void solve() {
int a, b, c;
cin >> a >> b >> c;

int ans = 0, ok = 0;
for (int i = 29; i >= 0; --i) {
int x = (1 << i) ^ a;
int y = (1 << i) ^ b;
int z = (1 << i) ^ c;
if (x < y && y < z) {
a = x;
b = y;
c = z;
ans ^= (1 << i);
break;
} else if (x < min(y, z) || max(x, y) < z) {
a = x;
b = y;
c = z;
ans ^= (1 << i);
}
}
if (a < b && b < c) cout << ans;
else cout << -1;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

int tt = 1;
cin >> tt;
while (tt--) {
solve();
cout << '\n';
}
return 0;
}

Tester's code (C++)
//clear adj and visited vector declared globally after each test case
//check for long long overflow
//Mod wale question mein last mein if dalo ie. Ans<0 then ans+=mod;
//Incase of close mle change language to c++17 or c++14
//Check ans for n=1
// #pragma GCC target ("avx2")
// #pragma GCC optimize ("O3")
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
// #define int long long
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);cout.precision(dbl::max_digits10);
#define pb push_back
#define mod 1000000007ll //998244353ll
#define lld long double
#define mii map<int, int>
#define pii pair<int, int>
#define ll long long
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rep(i,x,y) for(int i=x; i<y; i++)
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>
#define setbits(x) __builtin_popcountll(x)
#define print2d(dp,n,m) for(int i=0;i<=n;i++){for(int j=0;j<=m;j++)cout<<dp[i][j]<<" ";cout<<"\n";}
typedef std::numeric_limits< double > dbl;
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
const long long N=200005, INF=2000000000000000000;
const int inf=2e9 + 5;
lld pi=3.1415926535897932;
int lcm(int a, int b)
{
int g=__gcd(a, b);
return a/g*b;
}
int power(int a, int b, int p)
{
if(a==0)
return 0;
int res=1;
a%=p;
while(b>0)
{
if(b&1)
res=(1ll*res*a)%p;
b>>=1;
a=(1ll*a*a)%p;
}
return res;
}

int getRand(int l, int r)
{
uniform_int_distribution<int> uid(l, r);
return uid(rng);
}

int32_t main()
{
IOS;
int t;
cin>>t;
while(t--)
{
int a, b, c;
cin>>a>>b>>c;
if(a==b || c==a || b==c)
{
cout<<-1<<"\n";
continue;
}
int f=-1;
rep(i,0,500)
{
int x=getRand(0, (1 << 30) - 1);
if((b^x)>(a^x) && (c^x)>(b^x))
{
f=x;
break;
}
}
cout<<f<<"\n";
}
}

Editorialist's code (Python)
for _ in range(int(input())):
a, b, c = map(int, input().split())
x = 0
for bit in reversed(range(30)):
abit, bbit, cbit = (a >> bit) & 1, (b >> bit) & 1, (c >> bit) & 1

flip = 0
if a > b and abit > bbit: flip = 1
if b > c and bbit > cbit: flip = 1
if a > c and abit > cbit: flip = 1

if flip == 1:
a ^= 1 << bit
b ^= 1 << bit
c ^= 1 << bit
x ^= 1 << bit

print(x if a < b < c else -1)

4 Likes

There is something wrong with this judge literally giving ac on -1,0,1,2,3,4,5,6,7 anything .

4 Likes

You are damn right. I just printed -1 it got accepted . Submission id : CodeChef: Practical coding for everyone

4 Likes

ya you are damn right bro .

a,b,c is greater than 1 in constraint

I used another logic, like if ascending then the answer is 0, if descending then I used x as (A | (B^C)), as we know A > B > C, so A ^ (A | B^C)) what we can say is that lets as B and C are smaller their last position be say y’ and A before that doing xor with A will make it 0, and so we are left with xor of B xor C, for B ^ (A | B^C), will give us roughly equal to A|C, and for C similarly for C ^ X, it will give A|B, as A|B > A|C > B^C, so it convert it into required solution,
I know I don’t have much prove about it, but I used this as approximation, and it worked for me.

[i tired of multiple test cases but after i saw submissions i got surprised how was this codes gave ac ,then realized even with only a print statement of -1 the solution is getting accepted [Solution ](CodeChef: Practical coding for everyone)
There is something wrong with judge @youknow_who @yash_daga

weakest test cases , many got right , while i was struggling thinking actually cases , although authors approach seems true, but atleast i was thinking in my own way, while others with wrong codes got accepted. code force is better where hacks are done

2 Likes

i tried tester’s code but it’s showing wrong answer

1 Like

in tester’s code, why is he iterating 500 times can someone please explain it

Will they rejudge solution or not? I got AC on printing -1. At that time on running code it was showing same answer on sample test cases as well. Didn’t verify that again.

He is generating random x and checking if it gives the answer XD

Same here brother

There was an issue with the judge, which should be fixed now. Tester’s code gets AC.

As @darshan_9405 mentioned, the tester’s code randomly picks an X and checks if it satisfies the condition.
This is provably correct with high probability, and the editorial also mentions this solution in its last paragraph.

If a solution doesn’t exist, it will definitely print -1.
If a solution does exist, a random X will be a solution with probability \geq \frac 18
Since the failure probability is \leq \frac 78, repeating 500 times makes the overall failure probability something like 10^{-29} which is so low that it’s never going to fail in practice.

1 Like

will the contest rankings be updated because there may be many submissions wrongly accepted ?

3 Likes

Just rejudge and adjust the rankings or make this round unrated,or this platform loses its trust, I’m leaving the platform anyways,
It’s not worth the effort to participate in contests and put efforts while people plagiarise and wrong submissions get AC.
There’s no point in putting efforts, codechef has diminished it’s quality a lot, work on it.

3 Likes

What about the people who lost ratings because of that?

1 Like

Please make the contest unrated or atleast give the rankings updated.
@iceknight1093
Why should we suffer for taking time and write correct logical code because of Codechef’s weak and wrong testcases

2 Likes

Exactly