PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Akshit Monga
Tester & Editorialist: Taranpreet Singh
DIFFICULTY
Simple
PREREQUISITES
Bit Manipulation
PROBLEM
Given a sequence A with N non-negative integers, you are allowed to perform the following operation at most 3*N times.
- Pick three pairwise distinct indices i, j and k and assign A_k = A_i \oplus A_j. This operation can only be performed if N \geq 3
Your aim is to make the sequence good, which happens when both of the following conditions are satisfied.
- A_i \oplus A_{i+1} \geq 0 for all valid i (1 \leq i \leq N-1)
- A_{i-1} \oplus A_i \oplus A_{i+1} = A_i for all valid i (2 \leq i \leq N-1)
Print a sequence of at most 3*N operations to make sequence good or determine if it is impossible to do so.
QUICK EXPLANATION
- For N = 1, the sequence is already good. For N = 2, sequence is good if and only if A_1 \neq A_1
- For N = 3, answer is possible only when there’s atleast 1 non-zero element, and either A_2 = 0 or A_1 = A_3
- For N \geq 4, it is always possible except in case of all zeros. Pick two positions p and q with same parity such that A_p \neq A_q, and make all elements of opposite equal to A_p \oplus A_q. Now, using any two elements of parity opposite and make the elements of parity same as p and q zeros.
EXPLANATION
Let’s see what a good sequence looks like.
- A_i \oplus A_{i+1} > 0 happens when A_i \neq A_{i+1}. Hence, good sequence don’t have any two adjacent elements equal.
- A_{i-1} \oplus A_i \oplus A_{i+1} = A_i \implies A_{i-1} \oplus A_{i+1} = 0 which means A_{i-1} = A_{i+1}.
From above two elements, a good sequence shall be of form a b a b a b ... where a \neq b
Let’s consider this problem based on different values of N
N = 1
In this case, the sequence is already good.
N = 2
We cannot perform any operation, so we just need to check if it is already valid or not.
N = 3
This is tricky case. We need A_1 = A_3 and A_1 \neq A_2.
Let’s say first operation 1 2 3 is applied, resulting in sequence [A_1, A_2, A_1 \oplus A_2]. We can see that applying any other operations on this sequence doesn’t change the sequence at all. Similar situation happens when choosing different first operation.
Hence, one solution can try all possible first operation (there are just 3 of them to be checked). If the original sequence is good, or becomes good after one operation, print that operaton. Otherwise we can see that it is impossible.
We can make further observations as well.
It is possible to make sequence good, if A_1 = A_3, or A_2 = 0
Proof: Consider following cases
All elements same
There are two cases.
- If all elements are zero, then it is impossible to make the sequence good, since we cannot obtain non-zero
- If all elements are non-zero, we can apply operation to make middle element zero, resulting in good sequence
All elements distinct
In this case, we need to make A_1 = A_3, so we need A_1 \oplus A_2 = A_1, requiring A_2 = 0
Exactly two elements equal
If A_1 = A_3, sequence is good
Otherwise we need to make A_1 = A_3 equal, which need A_2 = 0.
N \geq 4
It is always possible to make the sequence good, unless the sequence is filled with zeros, since we cannot make any non-zero XOR.
If the sequence is already good, we don’t need to do anything.
if the sequence is filled with same value, we can make values at odd indices zero by applying \lceil N/2 \rceil operations 2 4 p where p is odd.
We can find two positions p and q of same parity modulo 2 such that A_p \neq A_q. WLOG assume p and q are even. Using these two elements, we can make all odd positioned elements equal to A_p \oplus A_q. Now, picking any two odd indexed elements, we can make all even positioned elements equal to zero.
This uses N operations only.
TIME COMPLEXITY
The time complexity is O(N) per test case.
SOLUTIONS
Setter's Solution
//Author- Akshit Monga
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
void print(int a,int b,int c){
cout<<a<<" "<<b<<" "<<c<<'\n';
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
assert(1<=t and t<=1e3);
int sig_n=0;
while(t--){
int n; cin>>n;
assert(1<=n and n<=1e4);
int arr[n];
for(int i=0;i<n;i++){cin>>arr[i]; assert(0<=arr[i] and arr[i]<(1<<30));}
sig_n+=n;
assert(1<=sig_n and sig_n<=2*(1e4));
if(n==1){
cout<<0<<'\n';
continue;
}
if(n==2){
if(arr[0]==arr[1]) cout<<-1<<'\n';
else cout<<0<<'\n';
continue;
}
if(n==3){
// all elements equal
if(arr[0]==arr[1] and arr[1]==arr[2]){
// all equal to 0
if(arr[0]==0) cout<<-1<<'\n';
// all equal to some non 0 value
else{
cout<<1<<'\n';
print(1,3,2);
}
continue;
}
// if first and last equal
if(arr[0]==arr[2]){
cout<<0<<'\n';
continue;
}
// if middle is 0
if(arr[1]==0){
cout<<1<<'\n';
if(arr[0]) print(1,2,3);
else print(3,2,1);
continue;
}
// else -1
cout<<-1<<'\n';
continue;
}
// now n>=4
set<int> vals;
for(auto i:arr) vals.insert(i);
// all elements equal
if((int)vals.size()==1){
// all equal to 0
if(arr[0]==0) cout<<-1<<'\n';
// all equal to some non 0 value
else{
vector<array<int,3>> ops;
int i=1,j=3;
for(int k=2;k<=n;k+=2) ops.push_back({i,j,k});
cout<<(int) ops.size()<<'\n';
for(auto triplet:ops) print(triplet[0],triplet[1],triplet[2]);
}
continue;
}
map<int,int> evens;
map<int,int> odds;
for(int i=0;i<n;i++){
if(i%2) evens[arr[i]]=i+1;
else odds[arr[i]]=i+1;
}
vector<array<int,3>> ops;
if((int)evens.size()>=2){
auto ptr=evens.begin();
int i=ptr->second;
ptr++;
int j=ptr->second;
for(int k=1;k<=n;k+=2) ops.push_back({i,j,k});
i=1;j=3;
for(int k=2;k<=n;k+=2) ops.push_back({i,j,k});
}
else if((int) odds.size()>=2){
auto ptr=odds.begin();
int i=ptr->second;
ptr++;
int j=ptr->second;
for(int k=2;k<=n;k+=2) ops.push_back({i,j,k});
i=2;j=4;
for(int k=1;k<=n;k+=2) ops.push_back({i,j,k});
}
// if both the conditions are not run array is already good.
cout<<(int) ops.size()<<'\n';
for(auto triplet:ops) print(triplet[0],triplet[1],triplet[2]);
}
return 0;
}
Tester's Solution
#include <iostream>
#include <assert.h>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <map>
using namespace std;
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;
}
assert(l<=x && x<=r);
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,' ');
}
struct OP{
int i, j, k;
OP(int i, int j, int k):i(i), j(j), k(k){}
};
bool valid(vector<int> A, vector<OP> op){
int N = (int)A.size();
if(N <= 2)return true;
for(auto x:op){
assert(x.i != x.j && x.j != x.k && x.i != x.k);
A[x.k] = A[x.i]^A[x.j];
}
bool val = true;
for(int i = 1; i< N-1; i++)val &= (A[i-1]^A[i]^A[i+1]) == A[i];
for(int i = 0; i< N-1; i++)val &= (A[i]^A[i+1]) > 0;
return val;
}
int main(){
int T = readIntLn(1, 1000);
int sumN = 0;
int MX = (1<<30)-1;
while(T-->0){
int N = readIntLn(1, 10000);
sumN += N;
assert(sumN <= 20000);
vector<int> A;
for(int i = 0; i< N; i++){
int x;
if(i+1 < N)x = readIntSp(0, MX);
else x = readIntLn(0, MX);
A.push_back(x);
}
vector<OP> op;
bool impossible = false;
if(N == 1){}
else if(N == 2){
if(A[0] == A[1])
impossible = true;
}else if(N == 3){
if(A[1] == 0){
if(max(A[0], A[2]) == 0)impossible = true;//all zeros
else{
//Middle element zero, making other two equal
if(A[0] > 0)op.push_back(OP(0,1,2));
else op.push_back(OP(2,1,0));
}
}else if(A[0] == A[2]){
//Either all equal > 0, or already good
if(A[0] != 0)op.push_back(OP(0,2,1));//making middle element 0
}else impossible = true;
}else{
bool allzero = true;
for(int x:A)allzero &= x == 0;
if(allzero)impossible = true;
else{
bool even = true, odd = true;
for(int i = 0; i< N; i+= 2)even &= A[i] == A[0];
for(int i = 1; i< N; i+= 2)odd &= A[i] == A[1];
if(even && odd){
if(A[0] == A[1]){
if(A[0] == 0)impossible = true;
else{
for(int i = 1; i< N; i += 2)op.push_back(OP(0, 2, i));
}
}
}else if(!even){
int p = -1;
for(int i = 2; i< N; i+= 2)if(A[i] != A[0])p = i;
assert(p != -1);
for(int i = 1; i< N; i+= 2)op.push_back(OP(0, p, i));
for(int i = 0; i< N; i+= 2)op.push_back(OP(1, 3, i));
}else if(!odd){
int p = -1;
for(int i = 3; i< N; i += 2)if(A[i] != A[1])p = i;
assert(p != -1);
for(int i = 0; i< N; i+= 2)op.push_back(OP(1, p, i));
for(int i = 1; i< N; i+= 2)op.push_back(OP(0, 2, i));
}else assert(false);
}
}
if(impossible)cout<<-1<<endl;
else{
assert(valid(A, op));
cout<<op.size()<<endl;
for(auto x:op)cout<<(1+x.i)<<" "<<(1+x.j)<<" "<<(1+x.k)<<endl;
}
}
assert(getchar()==-1);
cerr<<"SUCCESS\n";
}
Feel free to share your approach. Suggestions are welcomed as always. 
