PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: abraxos
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
easy-med
PREREQUISITES:
Familiarity with bitwise operations
PROBLEM:
You’re given three integers x_1, x_2, x_3.
In one move you can choose any two of them (say x_i and x_j) and an integer y, and replace x_i and x_j by x_i\oplus y and x_j\oplus y respectively.
Find the minimum number of moves needed to make x_1 + x_2 = x_3 and also a sequence of moves that achieves this; or claim it’s impossible.
EXPLANATION:
For convenience, let (i, j, y) denote the operation of XOR-ing x_i and x_j by y.
Note that if we have two operations (i, j, y_1) and (i, j, y_2), they can be combined into a single operation (i, j, y_1\oplus y_2).
This immediately tells us that we need no more than three operations: one per pair of elements.
So, we can describe the entire set of operations made by the triple (y_{12}, y_{13}, y_{23}), where y_{ij} corresponds to the operation (i, j, y_{ij}).
It turns out that we can attain an even stricter upper bound on the number of operations: we need no more than 2!
This is because the set of operations (y_{12}, y_{13}, y_{23}) can be replaced by (y_{12}\oplus y_{23}, y_{13}\oplus y_{23}, 0).
This can be verified by looking at how all three elements change upon applying these operations.
Now that we have an upper bound of 2, we only need to check whether using \leq 2 operations is feasible (and also construct a solution when it is).
This can be done by looking at each case separately.
Case 1: 0 operations
This is trivial to check: x_1 + x_2 = x_3 should hold already.
Case 2: 1 operation
Analysis
Suppose we’re operating on x_1 and x_2.
For each bit b,
- If it’s set in neither x_1 nor x_2, flipping it in both will increase x_1 + x_2 by 2^{b+1}.
- If it’s set in both x_1 and x_2, flipping it in both will decrease x_1 + x_2 by 2^{b+1}.
- If it’s set in one of them and not the other, flipping the bit in both doesn’t change the sum.
So, we have some (distinct) bits, each of which allows us to either increase or decrease x_1+x_2 by 2^{b+1}.
Our aim is to use these to make x_1 + x_2 = x_3.Dealing with both addition and subtraction is a bit annoying, so we transform the problem slightly.
For each bit b which allows us to subtract 2^{b+1}, let’s just perform the subtraction immediately.
This then instead gives us the option to add 2^{b+1} back instead - so we only have additions possible now, and we want to obtain x_3 - (x_1 + x_2) using these additions.This is now an easy problem: the powers of 2 with us are distinct, and there’s only one way to write a number as a sum of distinct powers of 2 (which is just its binary representation).
So, quite simply, if x_3 - (x_1 + x_2) has a binary representation whose bits are all present among the values of 2^{b+1} present with us, it’s possible to achieve what we want; otherwise it isn’t.
Operating on x_1 and x_3, or x_2 and x_3, will result in a similar situation: you’ll end up needing to make a certain sum using sums and differences of distinct powers of 2, which can be solved in the exact same way.
The details are left as an exercise to the reader.
Note that we only found the final values of the elements being operated on; but if this is known finding the actual operation is trivial.
Case 3: 2 operations
Analysis
We’ll focus on finding the final values of x_1, x_2, x_3: reconstructing the actual operations is easy after that.
Let’s consider a fixed bit b.
Let (b_1, b_2, b_3) be the value of this bit in variables x_1, x_2, x_3 respectively (each b_i is either 0 or 1).Note that a single operation flips either none of the b_i, or two of them.
This means the parity of b_1 + b_2 + b_3 doesn’t change.
So,
- If b_1+b_2+b_3 is even, after the operations either all three must be 0, or some two of them must be 1.
- If the sum is odd instead, either exactly one of them must be 1, or all three must be 1.
Now, note that if we end up with a solution where b_3 = 1 and some other b_i is also 1, we can simply unset both of them, which maintains the equality x_1+x_2=x_3 - so for simplicity we’ll never go into this case.
Also, in terms of the sum x_1+x_2, the triples (1,0,0) and (0,1,0) are equivalent.
This means the only triples we need to care about are (0,0,0),(1,1,0),(1,0,0),(0,0,1).We’ll call a bit even if it must end up as either (0,0,0) or (1,1,0), and odd otherwise.
Let’s iterate over bits in descending order.
If we encounter an even bit, (1,1,0) is not good: the sum x_1 + x_2 will be larger than x_3 no matter what we do. So, we must set this to (0,0,0).Now, let’s look at the first time we encounter an odd bit.
Note that everything above this is (0,0,0) so there’s no contribution there.
This means that (1,0,0) is not a valid choice here: it’ll again result in x_1+x_2 being larger than x_3.
So, we’re forced to choose (0,0,1) here.Let’s look at the next bit.
If it’s even, then note that we can set it to (1,1,0) and the sums so far become equal (after all, 2^{k-1} + 2^{k-1} = 2^k).
If it’s odd however, we need a bit more analysis.
Choosing (0,0,1) this time is bad: it would make x_3 too large and x_1+x_2 can’t catch up using lower bits. So, we’re forced to choose (1,0,0).In fact, the same logic applies to all following bits: if it’s odd, we must choose (1,0,0) otherwise x_3 becomes too large.
Now, the first time we reach an even bit, we can set it to (1,1,0) - this will equalize x_1+x_2 and x_3 with the bits used so far.Then, repeat for remaining bits.
Observe that the process is essentially: for each consecutive range of odd bits, as long as there’s an even bit immediately after it the entire block can be made to have equal sum with both x_1+x_2 and x_3. If this is achieved for every block we’ll be done.
It’s easy to see that this will almost always work, since after an odd block there must be an even bit.
The only exception is if the lowest bit (b = 0) is itself odd, in which case there’s no even bit after the last block.
But if the lowest bit is odd, we know from the parity argument that x_1+x_2+x_3 must be odd; which means x_1+x_2 can never be the same parity as x_3 (and so they cannot be equal either).So, if the lowest bit is odd no solution exists, otherwise a solution is always obtained using the above algorithm and we’re done!
TIME COMPLEXITY:
\mathcal{O}(\log\max(x_1, x_2, x_3)) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define nl "\n"
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef vector<pair<ll,ll>> vpll;
#define pb push_back
#define Sort(a) sort(a.begin(),a.end())
#define all(x) (x).begin(), (x).end()
const ll f = 1e9+7;
void solve(){
int x,y,z;
cin>>x>>y>>z;
if(x+y==z){
cout<<0<<nl;
return;
}
if((x^y^z)&1){
cout<<-1<<nl;
return;
}
vvi poss(3,vi(2,-1));
vvi nposs(3,vi(2,-1));
poss[0][0]=0;
poss[1][0]=0;
poss[2][0]=0;
for(int i=0;i<30;i++){
for(int j=0;j<3;j++){
for(int k=0;k<2;k++)nposs[j][k]=-1;
}
for(int j=0;j<3;j++){
if(poss[j][0]!=-1){
int b1=(x>>i)&1;
int b2=(y>>i)&1;
int b3=(z>>i)&1;
if((b1+b2)%2==b3){
nposs[j][(b1+b2)/2]=poss[j][0];
}
if(j==0 || j==2){
b1^=1;
}
if(j==0 || j==1){
b2^=1;
}
if(j==1 || j==2){
b3^=1;
}
if((b1+b2)%2==b3){
nposs[j][(b1+b2)/2]=poss[j][0]+(1<<i);
}
}
if(poss[j][1]!=-1){
int b1=(x>>i)&1;
int b2=(y>>i)&1;
int b3=(z>>i)&1;
if((b1+b2+1)%2==b3){
nposs[j][(b1+b2+1)/2]=poss[j][1];
}
if(j==0 || j==2){
b1^=1;
}
if(j==0 || j==1){
b2^=1;
}
if(j==1 || j==2){
b3^=1;
}
if((b1+b2+1)%2==b3){
nposs[j][(b1+b2+1)/2]=poss[j][1]+(1<<i);
}
}
}
for(int j=0;j<3;j++){
for(int k=0;k<2;k++)poss[j][k]=nposs[j][k];
}
}
if(poss[0][0]!=-1){
cout<<1<<nl;
cout<<1<<" "<<2<<" "<<poss[0][0]<<nl;
return;
}
if(poss[1][0]!=-1){
cout<<1<<nl;
cout<<2<<" "<<3<<" "<<poss[1][0]<<nl;
return;
}
if(poss[2][0]!=-1){
cout<<1<<nl;
cout<<1<<" "<<3<<" "<<poss[2][0]<<nl;
return;
}
cout<<2<<nl;
int a=y^z;
int b=x^y;
a^=(x^y^z)^((x^y^z)/2);
cout<<1<<" "<<2<<" "<<a<<nl;
cout<<2<<" "<<3<<" "<<b<<nl;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
Tester's code (C++)
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
// #define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
#define di(a) int a;cin>>a;
#define precise(i) cout<<fixed<<setprecision(i)
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define take(a,n) for(int j=0;j<n;j++) cin>>a[j];
#define give(a,n) for(int j=0;j<n;j++) cout<<a[j]<<' ';
#define vpii vector<pair<int,int>>
#define sis string s;
#define sin string s;cin>>s;
#define db double
#define be(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define pob pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bpc(x) __builtin_popcountll(x)
#define btz(x) __builtin_ctz(x)
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int, int>, null_type,less<pair<int, int> >, rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
const long long INF=1e18;
const long long M=1e9+7;
const long long MM=998244353;
int power( int N, int M){
int power = N, sum = 1;
if(N == 0) sum = 0;
while(M > 0){if((M & 1) == 1){sum *= power;}
power = power * power;M = M >> 1;}
return sum;
}
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}
int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && !isspace(buffer[now])) {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
return res;
}
string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
string res = readOne();
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int minv, int maxv) {
assert(minv <= maxv);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
auto readInts(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readInt(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
auto readLongs(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readLong(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
}inp;
vi pw(31);
int check_12(int x,int y,int z){
int give = 1,ans = 0,lx;
for(int i = 0;i < 31;i++){
int acc = pw[(((x&pw[i])?1:0) + ((y&pw[i])?1:0) + ((z&pw[i])?1:0))&1];
if((acc&give) != acc)return 0;
if(give == 3 && (lx^(acc-1)))ans |= pw[i-1];
lx = ((x&pw[i]) ? 1 : 0);
give = ((x&pw[i]) == (y&pw[i])? 3 : acc);
}
return ans;
}
int check_13(int x,int y,int z){
int give = 1,ans = 0,lx;
for(int i = 0;i < 31;i++){
int acc = pw[(((x&pw[i])?1:0) + ((y&pw[i])?1:0) + ((z&pw[i])?1:0))&1];
if((acc&give) != acc)return 0;
if(give == 3 && (lx^(acc-1)))ans |= pw[i-1];
lx = ((x&pw[i]) ? 1 : 0);
give = ((x&pw[i]) != (z&pw[i])? 3 : acc);
}
return ans;
}
void solve()
{
int x,y,z;
x = inp.readInt(0,1000'000'000);inp.readSpace();
y = inp.readInt(0,1000'000'000);inp.readSpace();
z = inp.readInt(0,1000'000'000);inp.readEoln();
if((x+y+z)&1){
cout << "-1\n";return;
}
if(x+y == z){
cout << "0\n";return;
}
int chk = check_12(x,y,z);
if((x^chk) + (y^chk) == z){
cout << 1 << "\n";
cout << 1 << " " << 2 << " " << chk << "\n";
return;
}
chk = check_13(x,y,z);
if((x^chk) + y == (z^chk)){
cout << 1 << "\n";
cout << 1 << " " << 3 << " " << chk << "\n";
return ;
}
chk = check_13(y,x,z);
if(x + (y^chk) == (z^chk)){
cout << 1 << "\n";
cout << 2 << " " << 3 << " " << chk << "\n";
return;
}
int op = 0;
for(int i = 0;i < 30;i++){
if((x&pw[i]) != (y&pw[i]))op |= pw[i];
}
cout << 2 << "\n";
cout << 2 << " " << 3 << " " << op << "\n";
y ^= op;z ^= op;
chk = check_12(x,y,z);
assert((x^chk) + (y^chk) == z);
cout << 1 << " " << 2 << " " << chk << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
pw[0] = 1;
rep(i,1,31)pw[i] = pw[i-1]*2;
int t = inp.readInt(1,200'000);
inp.readEoln();
while(t--)
solve();
inp.readEof();
return 0;
}