Why for n>=100, Answer is zero bro ?
I used Set and simple bruteforce n tada…! it worked.!
import java.io.*;
import java.util.*;;
class Orthodox {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
while(t--!=0) {
int n = Integer.parseInt(br.readLine());
String[] line = br.readLine().split(" ");
long[] arr = new long[n];
for (int i = 0; i < n; i++) {
arr[i]=Long.parseLong(line[i]);
}
boolean isPossible = true;
HashSet<Long> hs = new HashSet<>();
for(int i=0;i<n;i++) {
long num=0;
for(int j=i;j<n;j++) {
num=num | arr[j];
}
if(!hs.add(num)) {
isPossible = false;
break;
}
}
if(isPossible) System.out.println("YES");
else System.out.println("NO");
}
}
}Very Nice Editiorial…
please post all the editiorials in such fashion.
1 Like
This question was a waste of time. 2 hours and no solution. 
broo… exactly i did the same approach you did. but my solution failed…
can you once check it plzzz…I cant figure out my mistake 
submission:link
U r not able to solve that doesn’t means it’s waste of time .
1 Like
Many peoples copied from net , and due to this relative increment in rating is less .
Hey, I managed to get an AC during the contest in the first go. But my approach doesn’t match with the one given in Editorial. What I did is I maintained a cumulative “or” variable as follows
https://www.codechef.com/viewsolution/35808556
Is this approach also correct?
Let’s assume 0 <= A[i] <= 7, for the sake of simplicity and let all A[i] be pairwise distinct. Because when they’re not answer is NO directly.
Upto 7, you need only 3 bits to represent a number
For a pair i, j
A[i] | A[j] = max(A[i], A[j]) whenever a bit set in A[i] is set in A[j] also or vice versa.
Eg. 010 and 011; (010 | 011) = 011 = max(010, 011);
You will be able to write only up to 3 numbers such that for all pairs i, j.
A[i] | A[j] is not equal to max(A[i], A[j]).
Trying to write more than 3 numbers will fail, because each bit position would have been set atleast once by some number.
For eg. 001, 010, 100.
If you try to add one more you will end up with two numbers, such that A[i]|A[j] = max(A[i], A[j]); (You also can’t add 000)
In such a case, the answer is NO, as explained in the editorial.
For 7 you can’t write more than 3 numbers.
10^18 requires 60 bits, so you can’t write more than 60 numbers.
2 Likes
broo… exactly i did the same approach you did. but my solution failed…
can you once check it plzzz…I cant figure out my mistake
submission:link
yeah ,I tried standard brute force knowing it would fetch me TLE but that n>62 was nowhere near my head xp
To everyone who uses sorting of the array in this problem: I don’t think this is a good idea. The order of the numbers in this problem is seemingly important, sorting is destroying this order. This is because the condition involves subarrays, not subsequences. If it was talking about subsequences, then obviously the order doesn’t matter. I don’t believe any fruitful outcome could be produced by sorting (but I might be wrong, though!)
1 Like
The case you mentioned is right
I think that you need to compare the p|ar[i] with both p and ar[i] to ensure that match with either is considered
You can refer to my explanation I have commented below. It may help
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.