ORANDCON Editorial

PROBLEM LINK:

https://www.codechef.com/START24C/problems/ORANDCON

Setter: Utkarsh Gupta
Tester: Aryan Chaudhary
Editorialist: Rishabh Gupta

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You are given a positive integer X which is at most 10^8.

Find three distinct non-negative integers A,B,CA,B,C that do not exceed 10^9 and satisfy the following equation:

( A | B ) \& ( B | C ) \& ( C | A) = X

Here, | denotes the bitwise OR operator and & denotes the bitwise AND operator.

It can be shown that a solution always exists for inputs satisfying the given constraints. If there are multiple solutions, you may print any of them.

EXPLANATION:

Every set bit of X must be present in (A|B), (B|C) and (A|C) which also boils down to the fact that every set bit of X must be present in at least 2 of A,B and C.
So, we can make a construction as A = X = B, C= 0. To make A!=B we can add a larger power of 2 to A(say 2^{27}), making sure it does not get larger than 10^9.

TIME COMPLEXITY:

O(1) for each test case.

SOLUTION:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
#define LL long long
LL seed = chrono::steady_clock::now().time_since_epoch().count();
mt19937_64 rng(seed);
#define rand(l, r) uniform_int_distribution<LL>(l, r)(rng)
clock_t start = clock();

#define getchar getchar_unlocked

namespace IO {
long long readInt(char endd) {
    long long ret = 0;
    char c = getchar();
    while (c != endd) {
        ret = (ret * 10) + c - '0';
        c = getchar();
    }
    return ret;
}
long long readInt(long long L, long long R, char endd) {
    long long ret = readInt(endd);
    assert(ret >= L && ret <= R);
    return ret;
}
long long readIntSp(long long L, long long R) {
    return readInt(L, R, ' ');
}
long long readIntLn(long long L, long long R) {
    return readInt(L, R, '\n');
}
string readString(int l, int r) {
    string ret = "";
    char c = getchar();
    while (c == '0' || c == '?' || c == '1') {
        ret += c;
        c = getchar();
    }
    assert((int)ret.size() >= l && (int)ret.size() <= r);
    return ret;
}
}
using namespace IO;

const int TMAX = 100;

void solve() {
    int x = readIntLn(1, (int)1e8);
    int pos = 0, ret[3] = {0};
    for (int j=26;j>=0;--j) {
        for (int k=0;k<3;++k) {
            ret[k] |= (((pos == k) ^ ((x >> j) & 1)) << j);
        }
        pos = (pos == 2 ? 0 : pos + 1);
    }
    cout << ret[0] << " " << ret[1] << " " << ret[2] << '\n';
    assert(((ret[0] | ret[1]) & (ret[1] | ret[2]) & (ret[2] | ret[0])) == x);
}

int main() {
    int T = readIntLn(1, TMAX);
    while (T--) {
        solve();
    } 
    // assert(getchar() == EOF);
    cerr << fixed << setprecision(10);
    cerr << (clock() - start) / ((long double)CLOCKS_PER_SEC) << " secs\n";
    return 0;
}
Editorialist''s Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define dd double
#define endl "\n"
#define pb push_back
#define all(v) v.begin(),v.end()
#define mp make_pair
#define fi first
#define se second
#define vll vector<ll>
#define pll pair<ll,ll>
#define fo(i,n) for(int i=0;i<n;i++)
#define fo1(i,n) for(int i=1;i<=n;i++)
ll mod=1000000007;
ll n,k,t,m,q,flag=0;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// using namespace __gnu_pbds; 
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(a) -- no. of elements strictly less than a
// s.find_by_order(i) -- itertor to ith element (0 indexed)
ll min(ll a,ll b){if(a>b)return b;else return a;}
ll max(ll a,ll b){if(a>b)return a;else return b;}
ll gcd(ll a , ll b){ if(b > a) return gcd(b , a) ; if(b == 0) return a ; return gcd(b , a%b) ;}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #ifdef NOOBxCODER
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #else 
    #define NOOBxCODER 0
    #endif
    cin>>t;
    //t=1;
    while(t--){
        int a;
        cin>>a;
        cout<<a<<" "<<a + (1<<27)<<" "<< 0<<endl;






        
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
    return 0;
}

4 Likes

Why my code is not passing all test cases?
#include<bits/stdc++.h>
using namespace std;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while(t–){
int x;
cin>>x;
if(x&1)
cout<<x<<" β€œ<<x-1<<” β€œ<<x-2;
else
cout<<x<<” β€œ<<x+1<<” "<<x+2;
cout<<endl;
}

return 0;

}

2 Likes

check for x=1

3 Likes

think about x = 1

1 Like

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

#define For(a, c) for (int(a) = 0; (a) < (c); (a)++)

#define FORL(a, b, c) for (long long int(a) = (b); (a) <= (c); (a)++)

#define FORR(a, b, c) for (int(a) = (b); (a) >= (c); (a)–)

#define mp make_pair

#define pb push_back

#define Pob pop_back

#define F first

#define S second

typedef vector vll;

typedef vector vi;

typedef vector<vector> vii;

typedef pair<int, int> pi;

bool isPowerOfTwo(int n)

{

if(n==0)

return false;

return (ceil(log2(n)) == floor(log2(n)));

}

int main(){

ios::sync_with_stdio(0);

cin.tie(NULL);

cout.tie(NULL);

int t;

cin >> t;

while(t–){

ll x;

cin >> x;

if(isPowerOfTwo(x)){

    cout<<x<<" "<<x+1<<" "<<x+2<<"\n";

}

else if(x % 10 == 0 || x%2 == 0) {

  for(ll i=2; i<x; i*=2){

      ll ele = ((i|x-1) & (x-1|x) & (x|i));

      if(ele == x) cout<<i<<" "<<x-1<<" "<<x<<"\n";

  }

}

else{

    cout<<"1"<<" "<<x-1<<" "<<x<<"\n";

}

}

return 0;

}

On which tc my code will not run, can somebody tell me.?

Hello can anybody help me figure out how this code was AC for only 1 hidden test case??

#include
#include<bits/stdc++.h>
using namespace std;

int getbit(int n){
int check=1;
while ((n&check)==0)
{
check= check<<1;
}

return check;
}

bool isPowerOfTwo(int n)
{
if(n==0)
return false;

return (ceil(log2(n)) == floor(log2(n)));
}

int main(int argc, char const *argv[])
{
int tc;
cin>>tc;

while (tc--)
{
    int x;
    cin>>x;

    if (isPowerOfTwo(x))
    {
        cout<<x<<" "<<x+1<<" "<<x+2<<endl;
    }
    else
    {
        int j=getbit(x);
        cout<<j<<" "<<x-j<<" "<<x<<endl;
    }
    


}


return 0;

}

can somebody tell where i am getting wrong in this code

#include <bits/stdc++.h>
using namespace std;

void solve()
{
int x;
cin>>x;
int arr[3]={0,0,0};
arr[0]=x;
int temp=0,counter_z=0;
int bits = log2(x)+1;

int maxi = max(bits,3);
if((x&(x-1))==0){
for(int i=0;i<maxi;i++)
{
	temp=pow(2,i);
	if((x&temp))
	{
		for(int j=0;j<3;j++)
		{
			if(j!=counter_z) 
			{
				arr[j] += pow(2,i);
			}
		}
		
	}
	else
	{
		for(int j=0;j<3;j++)
		{
			if(j==counter_z) 
			{
				arr[j] += pow(2,i);
			}
		}
		
	}
	counter_z++;
}

}
else{
for(int i=0;i<bits;i++)
{
temp=pow(2,i);
if((x&temp))
{ if(counter_z==1)
{
arr[2]+=pow(2,i);
}

    		else arr[1]+=pow(2,i);
    		counter_z++;
    		
    	}
    	
    }

}
for(int j=0;j<3;j++) cout<<arr[j]<<" β€œ;
cout<<”\n";
// int a=arr[0],b= arr[1],c= arr[2];
// cout<<((a|b)&(b|c)&(c|a));
// cout<<endl;
}
int main() {
int test;
cin>>test;
while(test–)solve();
// your code goes here
return 0;
}

check for x= 1

correct for 1. For 1, (1,2,3) is my output

#include <bits/stdc++.h>

using namespace std;

int main(){

int t;

cin>>t;

while(t--){

    long long X;

    cin>>X;

    if(X==1){

        cout<<"1"<<"   "<<"2"<<"   "<<"7"<<endl;

    }

    else if(X%2==0){

        cout<<X<<"   "<<X+1<<"   "<<X+2<<endl;

    }

    else{

        cout<<X-2<<"   "<<X-1<<"   "<<X<<endl;

    }

}

}

why is it not accepting the solution… i have taken care of X=1 too… give me some examples…

1 Like

for x = 1 the last one is going to be negative number which we don’t want so for x == 1 print directly 0 1 3 or any other case if there for 1

even i also thought the same thing but got WA

can anyone tell me my mistake??

#include<bits/stdc++.h>

using namespace std;

int main(){

int T;

cin>>T;

while(T–){

long long n;

cin>>n;

if(n==1)

cout<<β€œ1”<<" β€œ<<β€œ2”<<” "<<β€œ7”<<endl;

else if(n%2==0)

cout<<n<<" β€œ<<n+1<<” "<<n+2<<endl;

else

cout<<n-2<<" β€œ<<n-1<<” "<<n<<endl;

}

return 0;

}

This is Correct ans…
#include<bits/stdc++.h>
using namespace std;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while(t–){
int x;
cin>>x;
if(x==1)
cout<<3<<" β€œ<<1<<” β€œ<<0;
else if(x&1)
cout<<x<<” β€œ<<x-1<<” β€œ<<x-2;
else
cout<<x<<” β€œ<<x+1<<” "<<x+2;
cout<<endl;
}

return 0;

}

1 Like

Think for x = 1
Your Output : 1 2 3

But when you calculate : (1|2) & (2|3) & (3|1)
it gives you 3 not 1

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    
   long long x;
    cin>>x;
    if(x%2)
    {
       if(x==1)
        {
            cout<<"1"<<" 2"<<" 4\n";
            return;
        }
       cout<<"1"<<" "<<x-1<<" "<<x<<endl;
    }
    else
    {
        if(x==2)
        {
            cout<<"1 6 2\n";
            return;
        }
        cout<<2<<" "<<x+1<<" "<<x<<endl;
    }
    
}

int main() {
    int test;
    cin>>test;
    while(test--)
	solve();
	return 0;
}

Please anyone give hidden testcase which fails this code.

For X = 1, it will fail. For X = 1, your answer will be 1, 0 and -1 but in the constraint negative numbers are not allowed. So take it as base case and try to find any three numbers that satisfy for X = 1.

I probably got the same issue but i figured it out.

for x = 1 , your output is wrong.

when you calculate : (1|2) & (2|4) & (4|1)
it gives you 0 not 1

heyy please can you tell me for which number I am getting wrong answer

#include <bits/stdc++.h>
using namespace std;

int main()
{
int t;
cin>>t;
while(t–){

    long long int n;
    cin>>n;
    if(n!=1){
        cout<<0<<" ";
        cout<<n<<" ";
        long long int x=ceil(log2(n));
        cout<<pow(2,x)-1<<endl;
    }
    if(n==1){
        cout<<0<<" ";
        cout<<1<<" "<<1<<endl;
    }
}

return 0;

}