PROBLEM LINK:
Author: Ritesh Gupta
Tester: Sachin Yadav
Editorialist: Ritesh Gupta
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
BITS, PREFIX-SUFFIX, OBSERVATION
PROBLEM:
You are given a circular sequence A_1, A_2, \ldots, A_N (3 \le N \le 2*10^5 \space and \space 0 \le A_i \le 10^9) where the elements are in the clockwise order and an integer K(0 \le K \le 10^9). You can change the value at any index by applying some operations. In one operation, you can select some index and replace the value at that index by bitwise or of the values of two adjacent elements of the current element i.e. if we apply the operation on i_{th} index then the value of A_i is equal to A_{i-1} or A_{i+1}.
Perform the above-mentioned operation over each index (exactly once) of the circular sequence in any order such that bitwise or of the elements of the resultant sequence is K.
QUICK EXPLANATION:
- Let suppose, if the answer is always possible then we need to remove first that elements which have a set bit that is not set in K. After then we can apply the operation on the rest of the indexes in such a way that we choose the index whose adjacent index had already been affected by the operation.
- If there is no element that has a set bit that is not set in K then we start operation from the index whose contribution is not required in clockwise order and cover all the indexes without skipping any.
EXPLANATION:
Let’s define an element good or bad. An i_{th} index element is said to be good if (A_i \space or \space K) == K else it is said to be bad. The answer is defined as the bitwise or of the elements of the resultant sequence.
OBSERVATION:
- The value of N should be greater than and equal to 3 as given in the question.
- If or of all the good elements of the sequence is not equal to k then the answer is -1.
- The first element where the operation applied makes sure that its adjacent element contribution is present in answer. So, if there are two bad elements in the sequence that are adjacent to each other then the answer is -1.
- It does not matter in which way we apply the operation but is sure that at least one element (the first element where the operation applied) should not contribute in answer. So, If the array has only good elements and all of them have some set bit which is not in others then the answer is -1 otherwise the answer is equal to K always possible.
If the answer exists then we perform the operation on bad elements in any order and after that on good elements in some order such that all the elements give their contribution into the answer. To make sure that we apply the operation on good elements from the right adjacent element of any bad element in the clockwise direction.
If all the elements are good then we can use the prefix-suffix technique to solve the problem as we know at least one index should not contribute to the answer. Let P_i and S_i is defined as bitwise-or of a prefix which ends at i^{th} index and bitwise-or of a suffix which starts at i^{th} index respectively. So, answer can be equal to:
- P_{N-1}
- S_1
- P_{i-1} + S_{i+1} for i form 1 to N-1
Now, suppose the contribution of i_{th} index element is not required in the answer, and answer is equal to K then we can apply the operation over the sequence from the i_{th} element in clockwise order.
Bonus Problem
- Try to find the lexicographically smallest solution among all possible ones.
COMPLEXITY:
TIME: O(N)
SPACE: O(N)
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[200010];
int b[200010];
bool vis[200010];
int32_t main()
{
int t;
cin >> t;
while(t--)
{
int n,k;
cin >> n >> k;
bool flag = false;
for(int i=0;i<n;i++)
{
cin >> a[i];
vis[i] = false;
if((a[i] | k) != k)
vis[i] = flag = true;
}
if(!flag)
{
for(int i=0;i<n;i++)
b[i] = a[i];
b[n] = 0;
for(int i=n-1;i>=0;i--)
b[i] = (b[i] | b[i+1]);
int cnt = 0;
flag = false;
for(int i=0;i<n;i++)
{
if((cnt | b[i+1]) == k)
{
cnt = i;
flag = true;
break;
}
cnt = (cnt | a[i]);
}
if(flag)
{
for(int i=cnt;i<n;i++)
cout << i+1 << " ";
for(int i=0;i<cnt;i++)
cout << i+1 << " ";
cout << endl;
}
else
cout << -1 << endl;
continue;
}
vis[n] = vis[0];
flag = false;
for(int i=1;i<=n;i++)
{
if(vis[i] && (vis[i] == vis[i-1]))
{
flag = true;
break;
}
}
if(flag)
{
cout << -1 << endl;
continue;
}
if(vis[0])
a[0] = (a[n-1] | a[1]);
int cnt = a[0];
a[n] = a[0];
for(int i=1;i<n;i++)
{
if(vis[i])
a[i] = (a[i-1] | a[i+1]);
cnt = (cnt | a[i]);
}
if(cnt == k)
{
for(int i=0;i<n;i++)
{
if(vis[i])
cout << i+1 << " ";
}
int prev = 0;
for(int i=0;i<n;i++)
{
if(vis[i])
{
int j = i;
while(j != prev)
{
cout << j << " ";
j--;
}
prev = i+1;
}
}
int j = n;
while(j != prev)
{
cout << j << " ";
j--;
}
cout << endl;
}
else
cout << -1 << endl;
}
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll const max_N=2e5+50;
ll T, N, K, arr[max_N];
bool bad[max_N];
void sol1();
void sol2();
void solve()
{
bool all_good=true;
memset(bad, 0, N+10);
ll or_good=0;
for(int i=1; i<=N; i++)
bad[i]=((arr[i] | K) != K);
for(int i=1; i<=N; i++)
{
int j=i+1;
if(j>N) j=1;
if(bad[i])
{
all_good=false;
if(bad[j])
{
cout<<-1;
return ;
}
}
else or_good|=arr[i];
}
if(or_good != K)
{
cout<<-1;
return ;
}
if(all_good)
sol1();
else
sol2();
}
void sol2()
{
int fst=N;
for(int i=1; i<=N; i++)
if(bad[i]){ cout<<i<<" "; fst=min(i, fst); }
for(int j=fst-1; j>=1; j--)
cout<<j<<" ";
for(int i=fst+1; i<=N; i++)
if(!bad[i]) cout<<i<<" ";
}
void sol1()
{
ll pre_or, suff_or[N+2];
pre_or=suff_or[N+1]=0;
for(int i=N; i>=1; i--)
suff_or[i]=suff_or[i+1] | arr[i];
for(int i=1; i<=N; i++)
{
if((pre_or | suff_or[i+1]) == K)
{
for(int j=i; j<=N; j++)
cout<<j<<" ";
for(int j=1; j<i; j++)
cout<<j<<" ";
return ;
}
pre_or|=arr[i];
}
cout<<-1;
}
int32_t main()
{
ios::sync_with_stdio(false); cin.tie(nullptr);
cin>>T;
while(T--)
{
cin>>N>>K;
for(int i=1; i<=N; i++)
cin>>arr[i];
solve();
cout<<"\n";
}
return 0;
}