# BITEQU - Editorial

Author: gudegude
Testers: tabr, yash_daga
Editorialist: iceknight1093

TBD

None

# PROBLEM:

Given an integer N, find four distinct positive integers a, b, c, d such that (((a \ \& \ b)\mid c)\oplus d) = N.

# EXPLANATION:

There are several ways to solve this problem. Here are a few:

Author's solution (fix c)

Let’s fix c = 2^{32} - 1, i.e, the first 32 bits of c are set.

This will make (a\ \& \ b)\mid c) always equal 2^{32}-1, no matter what a and b are.

So, choose d = c\oplus N, and then arbitrary a and b that don’t equal c or d, and we’re done.

There are only a couple of edge cases here: when we get d = 0 or d = c.

• If d = 0, that means N = 2^{32}-1. Find any solution for this case by hand and print it separately.
• If d = c, that means N = 0. Again, find a solution to this case by hand.

There are other ways to do this too; for example, you can fix c = 1 and similarly solve all but a handful of cases.

Tester's solution (brute force lower bits)

Let’s solve the problem for N \lt 8 by brute force, while ensuring that a, b, c, d are all also \lt 8.
Simply brute-forcing all 8^4 possibilities here will tell you that this is possible.

To solve for N \geq 8,

• Set the first three bits of a, b, c, d to the solution for N\mod 8.
• Give all higher bits that are set in N to d.
Editorialist's solution (Random)

Choose a, b, c randomly between 1 and 10^{18}, and then choose d = N\oplus ((a\ \& \ b)\mid c).

# TIME COMPLEXITY

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

# CODE:

Setter's code (C++)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
ll m = 4294967295;
while (t--){
ll n;
cin >> n;
if (n == 0) cout << 17 << " " << 1 << " " << 2 << " " << 3 << endl;
else if (n == m) cout << 2 << " " << 4 << " " << m - 1 << " " << 1 << endl;
else {
ll d = bitset<32>(n).flip().to_ulong();
if (d <= 2) cout << d + 1 << " " << d + 2 << " " << m << " " << d << endl;
else cout << d - 2 << " " << d - 1 << " " << m << " "<< d << endl;
}
}
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;
cin>>t;
assert(t>=1 && t<=10000);
vector <int> res[8];
res[0] = {7, 4, 2, 6};
res[1] = {7, 5, 3, 6};
res[2] = {7, 6, 3, 5};
res[3] = {7, 6, 5, 4};
res[4] = {7, 6, 5, 3};
res[5] = {7, 6, 5, 2};
res[6] = {7, 6, 5, 1};
res[7] = {7, 6, 4, 1};
while(t--)
{
int n;
cin>>n;
assert(n>=0 && (n<(1ll << 32)));
}
}

Editorialist's code (C++)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

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

int t; cin >> t;
const ll mx = 1e17;
while (t--) {
ll n; cin >> n;
ll a, b, c, d;
while (true) {
a = uniform_int_distribution<ll>(1, mx)(rng);
while (true) {
b = uniform_int_distribution<ll>(1, mx)(rng);
if (a == b) continue;
else break;
}
while (true) {
c = uniform_int_distribution<ll>(1, mx)(rng);
if (a == c) continue;
else if (b == c) continue;
else break;
}
d = (a & b) | c;
d ^= n;
if (a == d or b == d or c == d or d == 0) continue;
cout << a << ' ' << b << ' ' << c << ' ' << d << '\n';
break;
}
}
}


Can anyone explain where is my testcase failing 90405760

Given expression : ((a&b) | c) ^ d = n

1. Evaluate (a&b) this expression to zero. It can be done by (a = 1 << 35) and b = (1 << 36). Since n value is at max 10^9 or 2^32.
2. Now the expression is dependent only on ( c ^ d = n )
3. Evaluate c = n << 1
4. Evaluate d = c^n;

my logic:- a,b,c,d all are diffrent so fix a=1 and b=2
now a&b=0 , (0|c)=c (where | is bitwise or operator)
now equation is c xor d = n now we need to find c,d which is greater than 2 becouse we already fix a=1,b=2

now i’m stuck at this point how to find c and d?

I got the edge case.
if(n == 0) cout << “3 1 6 7”;

My worst contest ever. I wasted 2 hours due to the n==0 case.
The writer of the problem should highlight the constrain if they are creating some problem in which there are mirror edge cases.

#WA CASE1

2 Likes

I too spent a lot of time thinking there actually exists a -1 case .

Got it in the end though

2 Likes

The statement quite clearly mentions the constraint 0 \leq N \lt 2^{32}. There are only two constraints in this problem!

Also, the tester’s solution and editorialist’s solution I’ve explained (and whose code is linked) have no edge cases at all.

1 Like
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int solve() {
ll n, a = 0b0111111111111111111111111111111111111111
, b = 0b1011111111111111111111111111111111111111
, c = 0b1111111111111111111111111111111111111111
, d;
cin >> n;
if(!n){
cout << 0b001 << " " << 0b101 << " " << 0b110 << " " << 0b111;
return 0;
}
d = c^n;

if((((a&b)|c)^d) == n)
cout << a << " " << b << " " << c << " " << d << "\n";
return 0;
}

int main() {
int TET;
cin >> TET;
for (int i = 1; i <= TET; i++) {
if (solve()) {
break;
}
return 0;
}


Can anybody please tell me, why my code fails for test case
when n=1;
when clearly I print the statement only when the condition in the answer is satisfied?
NOTE: a = 549755813887, b = 824633720831, c = 1099511627775,
where ((a&b)|c) = c
and d = c^n?
???
What is the problem?

Can anyone tell me where my code is failing 90481120.

Logic: (2&1)|0 results in 0 and 0^n= n

The corner cases are n=0, 1, 2 and I have had special coverage for those

If n = 0 → print 3 1 6 7.
If n = 1 → print 1 4 3 2

Given expression: ((a&b) | c) ^d =n

Try to make a&b == 0
i.e, 0 | c = c.

If n is odd → n-1 ^ 1 = n.
If n is even → n+1 ^ 1 = n.

If n < 8
Take a = 15, b=16
// To make distinct values when n=4
else
Take a = 2, b = 4

If n is odd:
then c = n-1
else if n is even :
Then c = n +1

Take d = 1

Print( a,b,c,d)

CodeChef | Competitive Programming | Participate & Learn ( my solution)

I think something is wrong.
Check this submission,
CodeChef | Competitive Programming | Participate & Learn
and this one
CodeChef | Competitive Programming | Participate & Learn

→ First one is all wrong answers and other one is full AC, so whats the difference?
On, line 29, if i use 1L<<62, this gives wrong and 1L<<34, this gives AC,
but accoridng to the constraints, both should give AC, can anyone correct me on this?

2^62 is greater 10^18 chage it to 2^59(less than 2^18) and it passes again and change to 2^60(greater than 10^18) it fails again
2^59
2^60

I have tried with a similar approach, but I am getting WA for Test #0:

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

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
long long c = pow(2,32)-1;
while(t--) {
long long n;
cin >> n;
if(n == 0) cout << 4 << ' ' << 6 << ' ' << 5 << ' ' << 1 << '\n';
else if(n == c) cout << 2 << ' ' << 4 << ' ' << n-1 << ' ' << 1 << '\n';
else {
long long d = n^c;
if(d <= 2) cout << 3 << ' ' << 4 << ' ' << c << ' ' << d << '\n';
else cout << 1 << ' ' << 2 << ' ' << c << ' ' << d << ' ' << '\n';
}
}
return 0;
}


Can you help me in identifying the test case?