here we are just calculating for n=64 and anything above that gives NO by default, so we are considering only 300x64x64 which is well within the constraints and its not 300 * (10^5) * (10^5)=3 * (10^12). 
But Many Solutions Passed with just Bruteforcing and with no such condition like n=64.Blind Bruteforcing is getting AC
1 Like
The naive approach is to find all the sub-arrays and calculate the cumulative OR value for all of them seperately. It will have around O(N^3) complexity. But the method of maintaining a cumulative value and calculating the OR while adding each value to a sub-array is a better approach. It isnât completely brute-force.
I agree that the solution was kind of available on the internet, but who said you couldnât take help from third-party code. The time penalty is on you.
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.
3 Likes
/* 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!
1 Like
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.
2 Likes
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.
1 Like
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.
3 Likes
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