PROBLEM LINK:
Setter: Divyansh Gupta
Testers: Lavish Gupta, Tejas Pandey
Editorialist: Ajit Sharma Kasturi
DIFFICULTY:
SIMPLE
PREREQUISITES:
PROBLEM:
We are given an array of N elements. From this array, we create array B of \frac{N \cdot (N-1)}{2} elements where for every 1 \leq i \lt j \leq N, we add A_i \land A_j to B. Then, the following operations are performed until we are left with a single element:
-
Let the current maximum and minimum element of array B be X and Y respectively.
-
Remove X, Y and add X \lor Y to the array B.
We need to output the final element of B.
EXPLANATION:
-
The statement seems very complicated, but the important thing to notice is the bitwise operation \lor. The property of bitwise or is that if we are performing X \lor Y, bit i will be set if atleast one of bit i in X or Y is set.
-
This leads us to the most crucial observation of the problem, for every bit i, if bit i is set in atleast one of B_1, B_2, \dots B_\frac{N \cdot (N-1)}{2}, then bit i will be set in the final remaining element of B when all the operations are performed. We don’t need to worry about how the operations are performed.
-
For bit i to be set in atleast one element of B, we need to have atleast 2 elements in A say j and k where A_j and A_k both have bit i set. This sets the bit i in A_j \land A_k.
-
Now we have the following solution, iterate over every valid bit i, count the number of elements in array A which have bit i set. If this count is greater than 1, the final answer will have bit i set else it will be unset.
TIME COMPLEXITY:
O(N\log 10^9) for each test case.
SOLUTION:
Editorialist's solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int tests;
cin >> tests;
while (tests--)
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
vector<int> cnt(31);
for (int bit = 30; bit >= 0; bit--)
{
for (int i = 0; i < n; i++)
{
if ((1 << bit) & a[i])
cnt[bit]++;
}
}
int ans = 0;
for (int bit = 30; bit >= 0; bit--)
{
if (cnt[bit] > 1)
{
ans += (1 << bit);
}
}
cout << ans << endl;
}
return 0;
}
Setter's solution
#include<bits/stdc++.h>
#include<string>
using namespace std;
#define ll long long int
#define ld long double
#define pb push_back
#define all(v) v.begin(),v.end()
#define sz(x) ((int)(x).size())
#define deb(x) cout<< #x << '=' << x <<endl
#define MOD 1000000007
const int N = 1e5 + 5;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--){
ll n;
cin>>n;
ll a[n];
for(int i = 0; i < n; i++){
cin>>a[i];
}
vector<ll> cnt(32);
for(int i = 0; i < n; i++){
for(ll j = 0; j < 31; j++){
if((1LL << j) & a[i]){
cnt[j]++;
}
}
}
ll ans = 0;
for(ll i = 0; i < 32; i++){
if(cnt[i] > 1){
ans += (1LL << i);
}
}
cout<<ans<<"\n";
}
return 0;
}
Tester's solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
/*
------------------------Input Checker----------------------------------
*/
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;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
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,' ');
}
/*
------------------------Main code starts here----------------------------------
*/
const int MAX_T = 10000;
const int MAX_N = 100000;
const int MAX_Q = 100000;
const int MAX_val = 1000000000;
const int MAX_SUM_N = 200000;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int sum_n = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll p = 1000000007;
ll sum_nk = 0 ;
void solve()
{
int n = readIntLn(2 , MAX_N) ;
sum_n += n ;
max_n = max(max_n , n) ;
int arr[n] ;
for(int i = 0 ; i < n-1 ; i++)
arr[i] = readIntSp(0 , 1000000000) ;
arr[n-1] = readIntLn(0 , 1000000000) ;
vector<int> cnt(30) ;
for(int i = 0 ; i < n ; i++)
{
for(int j = 0 ; j < 30 ; j++)
if(arr[i] & (1 << j))
cnt[j]++ ;
}
int ans = 0 , curr = 1 ;
for(int i = 0 ; i < 30 ; i++)
{
if(cnt[i] > 1)
ans += curr ;
curr *= 2 ;
}
cout << ans << '\n' ;
return ;
}
signed main()
{
//fast;
#ifndef ONLINE_JUDGE
freopen("inputf.txt" , "r" , stdin) ;
freopen("outputf.txt" , "w" , stdout) ;
freopen("error.txt" , "w" , stderr) ;
#endif
int t = 1;
t = readIntLn(1,MAX_T);
for(int i=1;i<=t;i++)
{
solve() ;
}
assert(getchar() == -1);
assert(sum_n <= MAX_SUM_N);
cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
cerr<<"Sum of lengths : " << sum_n << '\n';
cerr<<"Maximum length : " << max_n << '\n';
// cerr << "Sum of product : " << sum_nk << '\n' ;
// cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';
}
Please comment below if you have any questions, alternate solutions, or suggestions. 