Pokémon Selection

Author : shailesh_2004

Required Knowledge : Bit Manipulation, Greedy

Time Complexity : $O(T \cdot log_2N)$

Editorialists : shailesh_2004, nisritha35

Approach-1 by shailesh_2004:

Let us first check for which $n$ it is not possible to do so. Let us check for odd number $9$ whose binary representation is $1001$. We have to chose $a,b,c$ such that their sum is $18$ and xor is $9$. There should be odd number of $1$s in LSB place. This means that the sum will be odd which is wrong. Thus, for odd $n$ it is not possible to find $a,b,c$ which satisfy the given condition.

Now, let us consider power of $2$. Take $16$ as example whose binary representation is $10000$. The number of $1$s in MSB place should be odd which can be $1$ or $3$ ones but $3$ ones is not possible as the sum exceeds $2 \cdot n$. So, there has to be only one $1$ in MSB place which leaves make $a$ as $n$ and $b, c$ both as $\frac{n}{2}$. There is no other possible $a,b,c$ which will satisfy the given constraints. But $b,c$ can't be equal. So it is not possible for powers of $2$ as well.

Consider three elements $n, \frac{n}{2}, \frac{n}{2}$.

This triplet follows the given first condition and second condition but two numbers are equal.

To make them not equal, consider a position at which bit is set in $\frac{n}{2}$ and unset in $n$ then swap these bits.

Here $n$ get's increased, $\frac{n}{2}$ get's decreased and another $\frac{n}{2}$ is constant. Hence these three values are not equal.

Code:

// Author : Shailesh
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vll vector<ll>
#define pb push_back
#define mp make_pair
#define endl "\n"
#define mod 1000000007
#define tot(a) a.begin(),a.end()
#define minii *min_element
#define maxii *max_element

void solve()
{
    ll n;
    cin>>n;
    if(n%2==1 || (n&(n-1))==0)
    {
        cout<<-1<<endl;
        return;
    }
    ll a=n;
    ll b=n/2;
    ll c=n/2;
    for(ll i=0;i<=62;i++)
    {
        if(((1LL<<i)&b)!=0 && ((1LL<<i)&a)==0)
        {
            a|=(1LL<<i);
            b^=(1LL<<i);
            break;
        }
    }
    cout<<a<<" "<<b<<" "<<c<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    ll t;cin>>t;while(t--)
    solve();
    return 0;
}

Approach-2 by nisritha35

Observations

To satisfy the conditions, we can analyze the binary representation of $N$ and examine how $A$, $B$, and $C$ can be constructed bit-by-bit:

XOR Condition: The condition $A$ ^ $B$ ^ $C$ = $N$ requires that: If a bit in $N$ is $1$, then an odd number of bits in $A$, $B$, and $C$ should be $1$ at that position (either $1$ or $3$ of them should be set). If a bit in $N$ is $0$, then an even number of bits in $A$, $B$, and $C$ should be $1$ at that position (either $0$ or $2$ of them should be set).

Sum Condition: The sum ${A + B + C = 2.N}$ implies that the total sum of bits in positions where $N$ has a $1$ must be achieved by either carrying over from the previous bit or by setting the bits in $A$, $B$, and $C$ appropriately.

When calculating ${2⋅N}$, the MSB of ${2⋅N}$ will have a $1$ in a position that’s higher than any bit in $N$. To satisfy the sum condition:

If a bit position in $N$ is $1$, we need a carry from the previous bit position to meet the sum requirement of ${2⋅N}$. If a bit position in $N$ is $0$, we either have zero or two bits set across $𝐴$, $B$, and $𝐶$ at that position.

Start from the most significant bit and proceed bit by bit. Use a carry variable to handle overflow across bit positions. Assign values to $A$, $B$, and $𝐶$ based on the current bit configuration and the constraints. To ensure $A$, $B$, and $C$ are distinct, alternate assignments where possible.

Code:

// Author: D. Nisritha Reddy 

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


void solve(){
     
    int n; cin >> n;
    
    int carry = 0;
    
    vi bits(63, 0);
    
    for(int i = 62; i>=0; i--){
        
        if((n&(1ll << i))) bits[i] = 1;
    
        if(carry==1){
            bits[i] += 2;
        }
        
        if((n&(1ll << i))) carry = 1;
        else carry = 0;
    }

    if(carry){
        cout << -1 <<"\n"; return;
    }
    
    bool first = true;
    int a = 0, b = 0, c = 0;
    
    for(int i = 0; i<63; i++){
        
        if(bits[i]==0)continue;
        else if(bits[i]==1)a += (1ll << i);
        else if(bits[i]==3){
            a += (1ll << i);
            b += (1ll << i);
            c += (1ll << i);
        }
        else{
        if(first){
            a += (1ll << i);
            c += (1ll << i);
            first = false; 
        }
        else{
            b += (1ll << i);
            c += (1ll << i);
        }
        }
    }
    
    if(a==0 || b==0 || c == 0 || a==b || a==c || b==c){
        cout << -1 <<"\n"; 
    }
    else{
        cout << a <<" "<<b<<" "<<c<<"\n";
    }
}


signed main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t = 1; cin>>t;
    
    while(t--){
        solve();
    }
}