PROBLEM LINK:
Author: Ritesh Gupta
Tester: Subhadeep Chandra
Editorialist: Ritesh Gupta
DIFFICULTY:
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
- There exist at least one 1 in the given sequence.
- 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";
}
}