EXISTENCEOFX - Editorial

PROBLEM LINK:

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

Author: Utkarsh Gupta
Testers: Nishank Suresh, Tejas Pandey
Editorialist: Nishank Suresh

DIFFICULTY:

2235

PREREQUISITES:

None

PROBLEM:

Given integers A, B, C, does there exist an X such that A\oplus X + B\oplus X = C\oplus X?

EXPLANATION:

First, let’s try to solve the problem for a single bit, i.e, A, B, C can all be either zero or one. We will later generalize this.

Solving for one bit

There are only 8 cases possible here, depending on the values of A, B, C. Trying them out a bit, you might notice that it is in fact almost always possible to find an X that is either 0 or 1 such that A\oplus X + B\oplus X = C\oplus X.

There are only two cases where it is impossible:

  • A = B = 0 and C = 1; and
  • A = B = 1 and C = 0

In both cases, choosing X = 0 or X = 1 won’t quite satisfy the equation: you’ll end up with either
However, note that choosing X = 1 for the first equation and X = 0 for the second does somewhat satisfy them, as long as you allow for a ‘carry bit’.

That is, you’ll end up with the ‘equation’ 1+1 = 0, but this can still be satisfied if you manage to get an extra of the next higher bit, since it’ll then come out to 1+1 = 2.

Solving the general case

Let’s try to generalize the above approach.
We saw that trying to satisfy one bit can sometimes depend on how we’re able to satisfy the next higher bit.

So, let’s iterate across bits in order from lower to higher, i.e, from 0 to 27. Suppose we’re at the i-th bit, and the respective values at this bit are A_i, B_i, C_i.
We also may or may not have a carry from the previous bit.

There are two cases now:

  • Suppose we don’t have a carry. Then, this is the same as the one-bit case, i.e,
    • If A_i = B_i \neq C_i, then we can satisfy this bit but the next one will have a carry.
    • In every other case, we can satisfy this bit and the next one won’t have a carry.
  • Suppose we did have a carry. You can once again do some case analysis and see that we have a very similar-looking result:
    • If A_i = B_i \neq C_i, then we can satisfy this bit but the next one won’t have a carry.
    • In every other case, the next bit will have a carry.

This way, we can surely satisfy at least the bits 0 to 27. Now, let’s look at where we stand after this process:

  • If there is no carry now, we’re done! A\oplus X + B\oplus X = C\oplus X has been achieved without any excess remaining, so the answer is “Yes”.
  • If there is a carry, it’s not hard to see that the answer is “No”.

So, repeat the process detailed above, and finally check whether there is a carry or not. This is 27 steps per test case.

TIME COMPLEXITY:

\mathcal{O}(\log \max(A, B, C)) per testcase.

CODE:

Preparer's code (C++)
#include <bits/stdc++.h>   
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;   
using namespace std;  
#define ll long long  
const ll INF_MUL=1e13;
const ll INF_ADD=1e18;    
#define pb push_back                 
#define mp make_pair          
#define nline "\n"                           
#define f first                                          
#define s second                                             
#define pll pair<ll,ll> 
#define all(x) x.begin(),x.end()     
#define vl vector<ll>           
#define vvl vector<vector<ll>>    
#define vvvl vector<vector<vector<ll>>>          
#ifndef ONLINE_JUDGE    
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);  
#endif       
void _print(ll x){cerr<<x;}  
void _print(char x){cerr<<x;}   
void _print(string x){cerr<<x;}    
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());   
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";} 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=998244353;       
const ll MAX=5000500;
ll getv(ll x,ll bit){
    return min(1LL,x&(1LL<<bit)); 
}
void solve(){       
    ll a,b,c,x,check; cin>>a>>b>>c;   
    vector<ll> l(31,0),r(31,0);
    for(ll i=0;i<30;i++){
        ll checka=getv(a,i),checkb=getv(b,i),checkc=getv(c,i); 
        if(checka!=checkb){
            l[i]++;
            if(l[i]%2){  
                ;
            }
            else{
                l[i+1]++;
                l[i]=0;
            }  
            r[i]=l[i]; 
        }
        else if(l[i]==checkc){
            r[i]=checkc;
            if(checka){
                l[i+1]++; 
            }
        }
        else{
            r[i]=checkc^1; 
            if(checka){
                ;
            }
            else{
                l[i+1]++;
            }  
        }   
    }  
    if(l==r){
        cout<<"YES\n";
    }
    else{
        cout<<"NO\n";
    }
    return;                                
}                                                 
int main()                                                                                           
{      
    ios_base::sync_with_stdio(false);                         
    cin.tie(NULL);  
    #ifndef ONLINE_JUDGE                   
    freopen("input.txt", "r", stdin);                                              
    freopen("output.txt", "w", stdout);  
    freopen("error.txt", "w", stderr);                        
    #endif                          
    ll test_cases=1;               
    cin>>test_cases;
    while(test_cases--){
        solve();
    } 
    cout<<fixed<<setprecision(10);
    cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
}  
Editorialist's code (Python)
for _ in range(int(input())):
    a, b, c = map(int, input().split())
    carry = 0
    for bit in range(28):
        x, y, z = (a >> bit) & 1, (b >> bit) & 1, (c >> bit) & 1
        if x == y and y != z: carry ^= 1
    print('No' if carry else 'Yes')
1 Like

getting the for Editorialist’s code (Python)

Short and easy to understand
https://www.codechef.com/viewsolution/81420664
just check wheather we get a carry at last or not .

You’re right, I pasted the wrong code there.
It’s fixed now.

hey even after global rank 76 my rating decreased , please someone look into this

Hey please help me debug this: CodeChef | Competitive Programming | Participate & Learn . I not not getting what I have missed. Not a single testcase comes out correct.

Exactly one condition was wrong, and that was the very last one.
When A_i + B_i = 0, C_i = 0, and carry = 1 you should go to doit(1, a, b, c, i+1) and not doit(0, a, b, c, i+1)

In general if you end up having to write many cases like this there’s a good chance you’ll make a mistake in one of them and then it becomes very hard to debug.
When you have many conditions like this, it’s useful to think about whether they can be simplified or not.

In this problem, you can see that all the conditions simplify down to essentially a single one: the carry flips its value if A_i = B_i \neq C_i, and that’s obviously much simpler to implement (and debug, if you do happen to make a mistake somewhere).

2 Likes

My easiest C++ solution

void solve() {
    int a,b,c; cin>>a>>b>>c;
    int carry=0;
    for(int i=0;i<32;i++){
        int aa= a&(1<<i);
        int bb= b&(1<<i);
        int cc= c&(1<<i);

        if(aa>0 && bb>0 && cc==0) carry^=1;
        else if(aa==0 && bb==0 && cc>0) carry^=1;
    }

    if(!carry) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    
}

Hello
I have been wrongly plagiarised for this problem. I have no idea how other codes are similar to mine as I wrote my code myself. I devoted an hour for writing my code and looked up different strategies on Stack Overflow to solve the problem. Please someone look into this. I have no idea how this is happening :((