TOOXOR - Editorial

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. :slight_smile:

11 Likes

Lovely problem @akshitm16, how did you come up with this?, I can’t ever think of me coming up with such an intriguing problem.

10 Likes

Is the difficulty really Simple ??

Because seems to be Medium level to most. The question statement was awesome and pretty clear. But the implementation is complex imo.

Anyways excellent problem @akshitm16.

6 Likes

Thank you so much! :smile:

I tried to build the problem from the solution itself. I already had alternating sequence in my mind. I tried thinking of some kind of conditions for sequences such that alternating sequences would always satisfy those. Initially, I wanted to set conditions such that sequences other than alternating sequences would also satisfy them but then I came with this problem where the solution could only be alternating sequences and I think that part was pretty easy to think of in my problem.

After that, I tried to think of some kind of sensible operations to perform to convert a given sequence to a “good” sequence.

The problem has couple of cases to handle for N=3 which made the problem a bit tougher than expected but they can also be easily handled as told in the editorial.

3 Likes

I want to ask the admin why this problem is not included in Div 1??.

1 Like

Yes, I can understand from participants’ point of view that the problem can be tough to implement especially when you’ve to handle cases. There are chances that people might miss to print out some output like number of operations somewhere etc. I think the overall logic is not very tough but maybe handling casework and implementation makes it bit tougher. The number of AC submissions also suggest that it proved out to be tougher than expected. So, you can place it in Easy category maybe.

4 Likes

Nice problem
mostly the edge cases were difficult to get.

5 Likes

Somewhat readable solution

The edge cases for N=3 can be easily handled. Notice you need only 1 operation atmost to fix the array, else it will never fix. So try out all different permutations of first operation and check whether that fixes the array. (also check if it was already fixed before).

2 Likes

Hey admin,
I’ve implemented a soln in C++ covering all cases suggested by the editorialist, rather in my own way.
But I see my solution isn’t getting accepted as correct(in practice mode, of course). I have cross-verified all cases mentioned in editorial, gave sample inputs to my code and checked it - it was giving all cases right answers (atleast to my understanding).
I’m really curious where my soln fails (of course there are very tricky edge cases).
Is there any way I can know where my soln is failing (atleast in which test case)?? I’m asking solely for knowledge purposes as I got deeply attached to this problem solving for hours :slight_smile:

Share the link of solution here.

https://www.codechef.com/viewsolution/48030782

Consider case-

1
4
0 1 1 1
2 Likes
#include <bits/stdc++.h>

using namespace std;

struct tri
{
    int a; int b; int c;
};

int main()
{
   ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);

   int tt;  cin>>tt;

   while(tt--)
   {
       int n;  cin>>n;

       int ar[n+1]; pair<int,int>br[n];

       for(int i=1;i<=n;i++)
          {cin>>ar[i]; br[i-1]={ar[i],i};}

           if(n==1) {cout<<0<<endl; continue;}
       if(n==2)
        { if(ar[1]==ar[2])  {cout<<-1<<endl; continue;}
       else {cout<<0<<endl; continue;}

        }

        bool bb=0;
        for(int i=1;i<=n;i++)
            {
                if(ar[i]!=0) bb=1;
            }
        if(bb==0) {cout<<-1<<endl; continue;}
        int x,y;
        sort(br,br+n);
        bool ff=1;
        for(int i=1;i<n;i++)
        {
            if(br[i].first==br[i-1].first)
            {
                ff=0;
                x=br[i].second;
                y=br[i-1].second;
                break;
            }
        }
          vector<tri>ans;
           if(ar[1]==0)
       {ar[1]=br[n-1].first^br[n-2].first;
        ans.push_back({br[n-1].second,br[n-2].second,1});
       }

        if(ff==1)
            {    if(n==3)
                {cout<<-1<<endl; continue;}
                else{
                    ar[2]=ar[1]^ar[n];
                    ans.push_back({1,n,2});
                    x=2;
                    ar[3]=ar[1]^ar[n];
                    ans.push_back({1,n,3});
                    y=3;
                }
        }









        for(int i=2;i<=n;i+=2)
        {
            if(i==x || i==y)
            {
                continue;
            }
            else{
                ar[i]=0;

                ans.push_back({x,y,i});
            }
        }
        int pos;
        for(int i=2;i<=n;i+=2 )
        {
            if(ar[i]==0)
            {
               pos=i; break;
            }
        }

       for(int i=3;i<=n;i+=2)
       {
           ar[i]=ar[1];
           ans.push_back({1,pos,i});
       }


       int pos1;

       for(int i=3;i<=n;i+=2)
       {
           if(ar[i]==ar[1]&&i!=x&& i!=y)
           {
               pos1=i; break;
           }
       }

       if(x%2==0)
       {
           ar[x]=0;
           ans.push_back({1,pos1,x});

       }

        if(y%2==0)
       {
           ar[y]=0;
           ans.push_back({1,pos1,y});

       }

       cout<<ans.size()<<endl;

       for(int i=0;i<ans.size();i++)
        cout<<ans[i].a<<" "<<ans[i].b<<" "<<ans[i].c<<endl;
   }
    return 0;
}

please anybody tell why this code isn’t working

Looks like some undefined behavior on

1
3
1 1 1

Ya, my code fails on this test case! Thanks for highlighting it.
I corrected my code and it gave AC finally :slight_smile:
Thanks a lot! Feeling a lot relieved!

1 Like

@akshitm16 can you please check this code?
https://www.codechef.com/viewsolution/48057380

Consider case-

1
4
0 0 0 1

My Output :
4
1 4 2
1 4 4
2 4 1
2 4 3

Final sequence according to this:
0 1 0 1

choose 3 pairwise distinct valid indices a, b and c.