Yeah he is known for doing that
Can anyone explain this python solution?
I’m really curious to know…
https://www.codechef.com/viewsolution/35815848
Same as gfg 
Wooooaaahh… That’s bit too much of ‘same’
Wow, This solution is really cool. It’s like pigeon hole theory.
So, We can claim that there will be at least 2 numbers whose bits will be common, if numbers are >= 62.
1 Like
Suppose you can have only 10 bits numbers, then first number should have atleast one set bit, then second number should add some distinct bit so Or of first two should have atleast two set bits and so on so Or of first set bit should have atleast 10 set bit (ie every possible bit is set in Or of first ten numbers). Then whatever be the 11th number, it’s set bits are already set in Or of first ten numbers . So for all ORs to be distinct N can not be greater than number of bits possible.
according to u loop will run till 64 times in worst case bt according to tester after 60 it will terminate… hope u understand what i am trying to say
def cal(l):
res = set()
p = {0}
for k in l:
p = {y|k for y in p} | {k}
res |= p
return len(res)
t = int(input())
for i in range(t):
n = int(input())
l = [int(j) for j in input().split()]
le = cal(l)
‘’’
check for duplicate entries which will make the set length less than the total number of possible (l,r) pairs
‘’’
if le == n*(n+1)/2:
print(“YES”)
else:
print(“NO”)
Much better explained in GFG
Can someone give a firm explanation or proof for this approach?
Although it seems intuitive, I am not able to digest why this always works.
It can be proved that , there is two different sub-array with equal OR if and only if at least one of the following conditions are true:
- There is an index i such that OR of sub-arrays (1,i-1) and (1,i) is equal.
- There is an index i such that OR of sub-arrays (i,N) and (i+1,N) is equal.
So all you have to do is check if any of these two conditions are true or not using two linear run over the array.
kindly read the editorial before making a statement
N^3 solution is working because for N > 62 before you get timed out you would have get duplicate and you would have ended the code execution
and
if n < 62 then you go on doing and at end you’re not timed out because N < 62
It’s correct. I proved it during the contest. And then solved it.
Suppose there are four indices a, b, c, d and (a,b)!=(c,d) such that or(a, b) =or(c, d)
where d>=b
If d>b
Case 1 : c>b or(1, c-1) =or(1, d)
Case 2 : otherwise or(1, b) =or(1, d)
If d =b
Or(a, n) =or(c, n)
These are the only possibilities of Or repeating and in all these cases 2*N-1 ORs mentioned in the solution can’t be distinct.
1 Like
MANY STUDENTS COPY CODE FROM DIRECTLY geeks from geeks (python)
AND ALSO THERE ARE WEAKS TEST CASES LIKE
2 4 5 16 32
2 Likes
bro…dont worry …u just focus on ur soln… 
1 Like
BUT DUE TO THIS CHEATING, ME AND MANY PEOPLE NOT ENJOY THIS CODING CULTURE
2 Likes
its not about enjoying bro,…just keep on coding
codechef needs to improve the test cases strictly
its really disappointing
WHY ARE YOU TAUNTING ME
AND DONT TELL ME WHAT TO DO AND WHAT NOT TO DO
2 Likes