PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: krrishmath
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You are given two integers N and M.
A sequence A is called a beautiful sequence if it consists of at least two distinct integers between 0 and M such that A_i \land A_j = N for each 1 \leq i \lt j \leq |A|.
Find any beautiful sequence with maximum length.
EXPLANATION:
The bitwise AND operation will be denoted by \land.
First, observe that if we have x\land y = z then:
- Both x and y must be supermasks of z, i.e. every bit that’s set in z must be set in both x and y.
- Any bit that’s not set in z must be unset in at least one of x and y — if it’s set in both of them then it’ll be set in their bitwise AND, which contradicts the AND being equal to z.
Now, we want A_i \land A_j = N for each pair (i, j). This means:
- Every bit that’s set in N must be present in every element of the array.
- Every bit that’s not set in N can be present in at most one element of the array.
Let the bits that are not set in N be, in ascending order, b_1, b_2, b_3, \ldots
Since our aim is to maximize the number of elements of A, it’s optimal to give each element of A exactly one of the bits b_i - if we give some element two or more of the bits, we could just as well split it into multiple elements (which will both be \leq M if the original value was \leq M so that’s not an issue).
This means the elements we need to consider are
We aren’t allowed to have elements that are \gt M, so stop the instant N + 2^{b_i} \gt M happens.
TIME COMPLEXITY:
\mathcal{O}(\log M) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
ll t;
cin>>t;
while(t--){
ll n,m;
cin>>n>>m;
vector<ll> arr;
arr.push_back(n);
ll c=1;
while(true){
if (c<0) break;
if ((n&c)==c) {
c=c<<1;
continue;
}
if (n+c>m) break;
arr.push_back(n+c);
c=c<<1;
}
if (arr.size()==1){
cout<<"-1\n";
continue;
}
cout<<arr.size()<<endl;
for (auto p: arr) cout<<p<<" ";
cout<<endl;
}
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
int t;
cin>>t;
while(t--){
int n, m;
cin>>n>>m;
if(n > m){
cout<<-1<<"\n";
}else{
int nn = n;
int temp = 1;
vector<int> ans;
ans.push_back(n);
while(n + temp <= m){
if(nn % 2 == 0){
ans.push_back(n + temp);
}
nn /= 2;
temp *= 2;
}
if(ans.size() == 1){
cout<<-1<<"\n";
}else{
cout<<ans.size()<<"\n";
for(int i = 0; i < ans.size(); i++){
cout<<ans[i]<<" ";
}
cout<<"\n";
}
}
}
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, m = map(int, input().split())
ans = [n]
for b in range(100):
if (n | 2**b) > m: break
if ~n & 2**b: ans.append(n | 2**b)
if len(ans) > 1:
print(len(ans))
print(*ans)
else:
print(-1)
