Editorial for Problem A

Pokémon Selection

Author : shailesh_2004

Required Knowledge : Bit Manipulation, Greedy

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

Editorialists : shailesh_2004, nisritha35

Approach-1 by shailesh_2004:

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

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

Consider three elements n,n2,n2n, \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 n2\frac{n}{2} and unset in nn then swap these bits.

Here nn get's increased, n2\frac{n}{2} get's decreased and another n2\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 NN and examine how AA, BB, and CC can be constructed bit-by-bit:

XOR Condition: The condition AA ^ BB ^ CC = NN requires that: If a bit in NN is 11, then an odd number of bits in AA, BB, and CC should be 11 at that position (either 11 or 33 of them should be set). If a bit in NN is 00, then an even number of bits in AA, BB, and CC should be 11 at that position (either 00 or 22 of them should be set).

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

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

If a bit position in NN is 11, we need a carry from the previous bit position to meet the sum requirement of 2N{2⋅N}. If a bit position in NN is 00, we either have zero or two bits set across 𝐴𝐴, BB, 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 AA, BB, and 𝐶𝐶 based on the current bit configuration and the constraints. To ensure AA, BB, and CC 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();
    }
}