It’s poetic that your handle is pigeon and the question involved pigeon hole principle xD. This question involved both bitwise operations and one very important observation.
If you want to practice regular bitwise operation problems, I’d suggest this. There isn’t much to read. You’ll just have to know how bitwise operations work, and the rest just comes from practice.
/* package codechef; // don’t place package name! */
import java.util.;
import java.lang.;
import java.io.*;
/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
try {
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t–>0)
{
int n=sc.nextInt();
long arr[]=new long[n];
HashSet set=new HashSet();
for(int i=0;i<n;i++) {
arr[i]=sc.nextInt();
set.add(arr[i]);
}
for(int i=0;i<n-1;i++)
{
long or=arr[i];
for(int j=i+1;j<n;j++)
{
or=or|arr[j];
set.add(or);
}
}
if(set.size()==n*(n+1)/2)
System.out.println("YES");
else
System.out.println("NO");
}
} catch(Exception e) {
} finally {
return;
}
}
}
This is my code can anyone please tell me what mistake I am making.It is passing all the sample test cases.Still its giving a wrong ans.
I know basic bitwise operations…
But to improve my problem solving in such bitwise question
Will solving problem on that topic help me or
Should i study something else also
IMO, there is nothing to study. You gain experience by solving a lot of bitwise problem. The link I tagged was from MAY20 challenge, and solving that (without any help) would definitely be of some help to your learning curve!
I can’t seem to understand why the answer is NO if number of elements is greater than 62. Can anyone explain it please?
Hi, setter here.
The complaint about brute forces getting AC is not valid because after at most 60 * (60 + 1) / 2 + 1 iterations we will always find a duplicate subarray OR(pigeonhole principle).
The only correct argument is solutions which just check if every prefix OR is a sub mask of the next element getting AC(or suffix OR). If you check both prefix OR and suffix OR then it is a correct solution.
This is my previous generator: FyXVT6 - Online C++0x Compiler & Debugging Tool - Ideone.com
As you can see, I had a function called ‘prefix defense’ to tackle these kinds of solutions. And guess what, I did another mistake while returning the vectors from that function. I returned a randomized version of the vector which I wasn’t supposed to do. So my whole ‘prefix defense’ function was all for nothing and really helped me to get bad impressions by making the test cases really weak!
The two mistakes I made in this contest are this one along with the palindromic checker(Invitation to CodeChef July Cook-Off 2020 - Codeforces) and I was really aware of them and don’t know how I actually ended up making the mistakes.
Sorry for the issues. I have fixed that stupid ‘prefix defense’ function and added a few new test cases. Hopefully, everything will be fine.
If you have any other complaints please let me know.
Actually we weren’t aware of this resource and that leetcode problem. Sorry!
The submissions won’t be rejudged as it will not be fair.
Help please.
The editorial says if n>62 directly reject otherwise do brute force in O(n^2) but if have 300 test cases (max possible) each having n around 60. Then we’ll have 300*(62^2) operations which is greater than 10^6.
In this case wouldn’t we get TLE?
But we don’t have 1600 test cases here. If we did have those many test cases then the problem would have been a little bit different. 
This code is very easy than written in the editorial!!
Can anyone help me Pass this code
#include<bits/stdc++.h>
using namespace std;
#define tw() int t; cin>>t; while(t--)
#define ll long long
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define all(x) x.begin(),x.end()
#define allcmp(x) x.begin(),x.end(),cmp
const int MOD = 1000000007;
vl bit(65),bit1,bit2;
void decToBinary(ll n)
{
ll i = 0;
while (n > 0) {
bit[i]+=(n % 2);
n = n / 2;
i++;
}
}
ll decrease1(ll n)
{
ll i = 0;
while (n > 0)
{
bit1[i] += (n % 2) ? -1 : 0;
n = n / 2;
if (bit1[i] == 1)
i++;
}
ll sum = 0;
for (ll i = 0; i < 65; i++)
{
if (bit1[i] > 0)
sum += pow(2, i);
}
return sum;
}
ll decrease2(ll n)
{
ll x = n;
ll i = 0;
while (n > 0)
{
bit2[i] += (n % 2) ? -1 : 0;
n = n / 2;
if (bit2[i] == 1)
i++;
}
ll sum = 0;
for (ll i = 0; i < 65; i++)
{
if (bit2[i] > 0)
sum += pow(2, i);
}
return sum;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
tw(){ bool ok=true;
fill(all(bit), 0);
ll n;
cin >> n;
vl v(n);
ll sum = 0;
map<ll, ll> m;
int z = 0;
for (auto &x : v)
{
cin >> x;
m[x]++;
if (m[x] > 1)
ok = false;
}
for (auto x : v)
{
decToBinary(x);
}
ll sum1 = 0;
for (ll i = 0; i < 65; i++)
{
if (bit[i] > 0)
sum1 += pow(2, i);
}
m[sum1]++;
if (m[sum1] > 1)
ok = false;
bit1 = bit;
bit2 = bit;
for (int i = 0; i < n - 1 && ok; i++)
{
ll x;
if (i > 0)
{
x = decrease1(v[i - 1]);
m[x]++;
if (m[x] > 1)
{
ok = false;
break;
}
}
}
for (int i = n - 1; i > 0 && ok; i--)
{
ll x;
if (i < n - 1)
{
x = decrease2(v[i + 1]);
m[x]++;
if (m[x] > 1)
{
ok = false;
break;
}
}
}
if(ok){cout<<"YES\n";}
else{cout<<"NO\n";}
}
return 0;}It’s nice of you to give an explanation of what went wrong with the test cases. It shows us that we are all humans. It is already hard enough think of alternate solutions that should or shouldn’t pass a problem, let alone preventing them from getting accepted.
i faced the same issue man …i was just keep wondering for a optimised approach.
here everyone has written that around operations upto 10^8 are allowed but here n^2 approach performs 10^10 operations…please someone help me with this issue
Could you prove why? In that case, we’re done right? I know how to continue after this is proved. I just need a solid proof that what I said is true
Did you try reading the editorial? Can you scroll up and read setters’s remarks?
thnx bruuh… it worked but cant understand for which case it could go wrong for my previous submission. I think it should cover all the test cases 