PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Practice
Setter: Mithil Shah
Testers: Nishank Suresh and Abhinav Sharma
Editorialist: Mithil Shah
DIFFICULTY
1519
PREREQUISITES
None
PROBLEM
For 3 distinct prime integers A, B, and C (1 \lt A,B,C \lt 2^{30}), we define positive integers X, Y, and Z as:
X = A\oplus B, Y = B\oplus C, and Z = C\oplus A, where \oplus denotes the bitwise XOR operation.
Given only two integers X and Y and the fact that at least one integer amongst X, Y, and Z is odd, find the values of A, B, and C.
EXPLANATION
First Observation:
If we have X and Y then we can get Z by taking bitwise XOR of the X and Y.
Proof
X=A\oplus B, Y=B\oplus C and X\oplus Y=(A\oplus B)\oplus (B\oplus C)=A\oplus C=Z.
Second Observation:
It is given that at least one integer amongst X, Y, and Z is odd, this implies one of the numbers from A, B, and C must be even as bitwise XOR of even and odd number gives odd.
The only even prime number that exists is 2, hence we have concluded one number out of A, B, and C.
To obtain the remaining two numbers from A, B, and C, we can take bitwise XOR of 2 and two odd numbers out of X, Y, and Z.
Hence, we arrive at the values of all A, B, and C.
TIME COMPLEXITY
The time complexity is O(1) per testcase.
SOLUTIONS
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define vi vector<int>
#define rep(i, n) for (int i = 0; i < n; i++)
#define endl '\n'
#define fastio \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
void tosolve()
{
vi a;
int b[3];
cin >> b[0] >> b[1];
b[2]=b[0]^b[1];
a.pb(2);
if (b[0] % 2 == 0)
{
a.pb(2^b[1]);
a.pb(2^b[2]);
}
else if (b[1] % 2 == 0)
{
a.pb(2^b[0]);
a.pb(2^b[2]);
}
else if (b[2] % 2 == 0)
{
a.pb(2^b[0]);
a.pb(2^b[1]);
}
sort(a.begin(), a.end());
rep(i,3)
{
if(i==2) cout<<a[i]<<endl;
else cout<<a[i]<<" ";
}
return;
}
int32_t main()
{
fastio;
int t;
cin>>t;
while(t--)
{
tosolve();
}
return 0;
}
Tester-1's Solution
for _ in range(int(input())):
x, y = map(int, input().split())
ans = [2]
if x%2 == 1:
ans.append(x^2)
if y%2 == 1:
ans.append(y^2)
else:
ans.append(y^ans[1])
else:
ans.append(y^2)
ans.append(ans[1]^x)
print(*sorted(ans))
Tester-2's Solution
#include <bits/stdc++.h>
using namespace std;
/*
------------------------Input Checker----------------------------------
*/
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=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 readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
/*
------------------------Main code starts here----------------------------------
*/
const int MAX_T = 1e5;
const int MAX_N = 1e5;
const int MAX_SUM_LEN = 1e5;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
#define pb push_back
int sum_n = 0, sum_m = 0;
int max_n = 0, max_m = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll mod = 1000000007;
using ii = pair<ll,ll>;
bool chk_pr(int x){
for(int i=2; i*i<=x; i++) if(x%i==0) return 0;
return 1;
}
vector<int> pr;
void pre(){
rep_a(i,2,40005){
if(chk_pr(i)) pr.pb(i);
}
}
bool fun(int x){
for(auto h:pr){
if(h*h>x) return 1;
if(x%h==0) return 0;
}
return 1;
}
void solve(){
int x = readIntSp(1,(1ll<<30)-1);
int y = readIntLn(1,(1ll<<30)-1);
int z = x^y;
int a[3];
a[0]=a[1]=a[2]=2;
if(x&1) a[0] = x^2;
if(y&1) a[1] = y^2;
if(z&1) a[2] = z^2;
sort(a,a+3);
assert(a[0]!=a[1] && a[1]!=a[2]);
assert(fun(a[0]) && fun(a[1]) && fun(a[2]));
cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<'\n';
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r" , stdin);
freopen("output.txt", "w" , stdout);
#endif
fast;
int t = 1;
pre();
t = readIntLn(1,1e5);
for(int i=1;i<=t;i++)
{
solve();
}
assert(getchar() == -1);
//assert(sum_n<=3e5);
cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
cerr<<"Sum of lengths : " << sum_n <<" "<<sum_m<<'\n';
// cerr<<"Maximum length : " << max_n <<'\n';
// // cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Feel free to share your approach. Suggestions are welcomed. 