# DECOXOR - Editorial

Author: Ritesh Gupta
Editorialist: Ritesh Gupta

EASY

# PREREQUISITES:

Observation, Math

# PROBLEM:

You are given a sequence A_1, A_2, \ldots, A_N. You have to tell whether it is possible to find a non-empty subsequence of length L such that xor of the elements of this subsequence is equal to K.

# Constraints:

• 1 \le T \le 10^6
• 2 \le L \le N \le 3 \cdot 10^5
• 1 \le K \le 3
• 1 \le A_i \le 3 for each valid i

# EXPLANATION:

We know that 1^2^3 is equal to 0 which implies that xor of any two-elements is equal to the third element. If we want to find out the subsequence of length L and xor value equal to K = 1 then there are two cases:

• L is even then it is clear that subsequence contains one 2 and one 3 and rest can be filled by pairs of equal elements so the resultant subsequence results in xor equal to K. So, the answer is possible if
• There exist at least one 2 in the given sequence.
• There exist at least one 3 in the given sequence.
• L-2 >= c_1 + c_2 + c_3 where c_i = frequency of i in sequence integer division by 2.
• L is odd then it is clear that subsequence contains one 1 and rest can be filled by pairs of equal elements so the resultant subsequence results in xor equal to K. So, the answer is possible if
1. There exist at least one 1 in the given sequence.
2. L-1 >= c_1 + c_2 + c_3 where c_i = frequency of i in sequence integer division by 2.

Same for K is equal to 2 and 3.

# SOLUTIONS:

Setter's Solution

#include <bits/stdc++.h>

#define int long long
#define endl ā\nā

using namespace std;

int32_t main()
{
int t;
cin >> t;

while(t--)
{
int n,x,y;
cin >> n >> x >> y;

int a[4] = {0};

for(int i=0;i<n;i++)
{
int x;
cin >> x;

a[x]++;
}

swap(a[1],a[y]);

if(x%2)
a[1]--, x--;
else
a[2]--, a[3]--, x -= 2;

bool flag = false;

for(int i:a)
{
if(i < 0)
{
flag = true;
break;
}
}

if(flag)
{
cout << "NO\n";
continue;
}

x /= 2;
int cnt = 0;

for(int i:a)
cnt += i/2;

if(x > cnt)
cout << "NO\n";
else
cout << "YES\n";
}


}

Tester's Solution

#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
using ll=long long;

int main()
{
int n,l,k,t;
cin>>t;

while(t--)
{
cin>>n>>l>>k;

vector<int> f(4);

for(int i=0;i<n;i++)
{
int x;
cin>>x;

f[x]++;
}

int ans=0;

if(k==3)
{
int a=f[1],b=f[2],c=f[3],len=l;

if(c)
{
c--;
len--;

if(len%2==0)
{
if(2*(a/2+b/2+c/2)>=len)
ans=1;
}
else if(a && b && c)
{
a--,b--,c--;
len-=3;

if(2*(a/2+b/2+c/2)>=len)
ans=1;
}
}

a=f[1],b=f[2],c=f[3],len=l;

if(a && b)
{
a--,b--;
len-=2;

if(len%2==0)
{
if(2*(a/2+b/2+c/2)>=len)
ans=1;
}
else if(a && b && c)
{
a--,b--,c--;
len-=3;

if(2*(a/2+b/2+c/2)>=len)
ans=1;
}
}
}
else if(k==2)
{
int a=f[1],b=f[2],c=f[3],len=l;

if(b)
{
b--;
len--;

if(len%2==0)
{
if(2*(a/2+b/2+c/2)>=len)
ans=1;
}
else if(a && b && c)
{
a--,b--,c--;
len-=3;

if(2*(a/2+b/2+c/2)>=len)
ans=1;
}
}

a=f[1],b=f[2],c=f[3],len=l;

if(a && c)
{
a--,c--;
len-=2;

if(len%2==0)
{
if(2*(a/2+b/2+c/2)>=len)
ans=1;
}
else if(a && b && c)
{
a--,b--,c--;
len-=3;

if(2*(a/2+b/2+c/2)>=len)
ans=1;
}
}
}
else
{
int a=f[1],b=f[2],c=f[3],len=l;

if(a)
{
a--;
len--;

if(len%2==0)
{
if(2*(a/2+b/2+c/2)>=len)
ans=1;
}
else if(a && b && c)
{
a--,b--,c--;
len-=3;

if(2*(a/2+b/2+c/2)>=len)
ans=1;
}
}

a=f[1],b=f[2],c=f[3],len=l;

if(b && c)
{
b--,c--;
len-=2;

if(len%2==0)
{
if(2*(a/2+b/2+c/2)>=len)
ans=1;
}
else if(a && b && c)
{
a--,b--,c--;
len-=3;

if(2*(a/2+b/2+c/2)>=len)
ans=1;
}
}
}

if(ans)
cout<<"YES\n";
else
cout<<"NO\n";
}


}

2 Likes

Again a great editorial

1 Like