ORTHODOX - Editorial

mvj3011 · July 19, 2020, 7:49pm

My approach is different from the one mentioned.
I first sorted the array in descending order and then traversed from left to right. I maintained a variable X that stored the OR of all the number seen till now. At each step I ORed X with the current index value and checked if the value of X has changed or not.
If it didn’t then I broke the loop and printed “NO”.
I got AC. Can anybody confirm if the approach was actually correct. Thanks.

tanmayaaeron · July 19, 2020, 7:49pm

This logic is correct. I also did it the same way.

ssrivastava990 · July 19, 2020, 7:53pm

Think in terms of binary - what is the largest power of 2 which is less than 10¹⁸ it is 2⁵⁹

Now what it means , how many different values we can take of power of 2 which is 59 -
see-

1 000000000000000000000000000000000000000000000000000000000001
2 000000000000000000000000000000000000000000000000000000000010
4 000000000000000000000000000000000000000000000000000000000100
8 000000000000000000000000000000000000000000000000000000001000
16 000000000000000000000000000000000000000000000000000000010000
32 000000000000000000000000000000000000000000000000000000100000
64 000000000000000000000000000000000000000000000000000001000000
128 000000000000000000000000000000000000000000000000000010000000
256 000000000000000000000000000000000000000000000000000100000000
512 000000000000000000000000000000000000000000000000001000000000
1024 000000000000000000000000000000000000000000000000010000000000
2048 000000000000000000000000000000000000000000000000100000000000
4096 000000000000000000000000000000000000000000000001000000000000
8192 000000000000000000000000000000000000000000000010000000000000
16384 000000000000000000000000000000000000000000000100000000000000
32768 000000000000000000000000000000000000000000001000000000000000
65536 000000000000000000000000000000000000000000010000000000000000
131072 000000000000000000000000000000000000000000100000000000000000
262144 000000000000000000000000000000000000000001000000000000000000
524288 000000000000000000000000000000000000000010000000000000000000
1048576 000000000000000000000000000000000000000100000000000000000000
2097152 000000000000000000000000000000000000001000000000000000000000
4194304 000000000000000000000000000000000000010000000000000000000000
8388608 000000000000000000000000000000000000100000000000000000000000
16777216 000000000000000000000000000000000001000000000000000000000000
33554432 000000000000000000000000000000000010000000000000000000000000
67108864 000000000000000000000000000000000100000000000000000000000000
134217728 000000000000000000000000000000001000000000000000000000000000
268435456 000000000000000000000000000000010000000000000000000000000000
536870912 000000000000000000000000000000100000000000000000000000000000
1073741824 000000000000000000000000000001000000000000000000000000000000
2147483648 000000000000000000000000000010000000000000000000000000000000
4294967296 000000000000000000000000000100000000000000000000000000000000
8589934592 000000000000000000000000001000000000000000000000000000000000
17179869184 000000000000000000000000010000000000000000000000000000000000
34359738368 000000000000000000000000100000000000000000000000000000000000
68719476736 000000000000000000000001000000000000000000000000000000000000
137438953472 000000000000000000000010000000000000000000000000000000000000
274877906944 000000000000000000000100000000000000000000000000000000000000
549755813888 000000000000000000001000000000000000000000000000000000000000
1099511627776 000000000000000000010000000000000000000000000000000000000000
2199023255552 000000000000000000100000000000000000000000000000000000000000
4398046511104 000000000000000001000000000000000000000000000000000000000000
8796093022208 000000000000000010000000000000000000000000000000000000000000
17592186044416 000000000000000100000000000000000000000000000000000000000000
35184372088832 000000000000001000000000000000000000000000000000000000000000
70368744177664 000000000000010000000000000000000000000000000000000000000000
140737488355328 000000000000100000000000000000000000000000000000000000000000
281474976710656 000000000001000000000000000000000000000000000000000000000000
562949953421312 000000000010000000000000000000000000000000000000000000000000
1125899906842624 000000000100000000000000000000000000000000000000000000000000
2251799813685248 000000001000000000000000000000000000000000000000000000000000
4503599627370496 000000010000000000000000000000000000000000000000000000000000
9007199254740992 000000100000000000000000000000000000000000000000000000000000
18014398509481984 000001000000000000000000000000000000000000000000000000000000
36028797018963968 000010000000000000000000000000000000000000000000000000000000
72057594037927936 000100000000000000000000000000000000000000000000000000000000
144115188075855872 001000000000000000000000000000000000000000000000000000000000
288230376151711744 010000000000000000000000000000000000000000000000000000000000
576460752303423488 100000000000000000000000000000000000000000000000000000000000

now if we take these values in array and bitwise OR of all of them answer is unique -

which is

1152921504606846975 111111111111111111111111111111111111111111111111111111111111

Now if we do bitwise OR then the value is already present in set , so no change , means answer will be NO

else for size less than 60 we will do brute force bcz answer may or may not exist .

See this guy solution : HERE

avi_9314 · July 19, 2020, 7:57pm

Include me in this list

mavrik · July 19, 2020, 7:58pm

can someone make me understand why this is in testers solution

Blockquote
if (n >= 100) {
cout << “NO\n”;

why would be the answer NO if the number of element is more than 100 ?

c1ph3r420 · July 19, 2020, 7:58pm

His variable names though LMFAO XD

shravan660 · July 19, 2020, 8:06pm

Thanks for the reply. What if the array consists of value 1 2 3 4 5 … 64 how does this work?

udayan14 · July 19, 2020, 8:08pm

Yeah he is known for doing that

anon21307805 · July 19, 2020, 8:18pm

Can anyone explain this python solution?

I’m really curious to know…
https://www.codechef.com/viewsolution/35815848

ssrivastava990 · July 19, 2020, 8:19pm

Same as gfg

anon21307805 · July 19, 2020, 8:23pm

Wooooaaahh… That’s bit too much of ‘same’

better_sleep · July 19, 2020, 8:28pm

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.

tanmayaaeron · July 19, 2020, 8:36pm

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.

sg_186 · July 19, 2020, 8:37pm

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

rishmeh · July 19, 2020, 8:38pm

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

hp21 · July 19, 2020, 9:05pm

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.

sadman2901 · July 19, 2020, 9:15pm

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.

anonym_chef · July 19, 2020, 9:19pm

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

mt6170078 · July 19, 2020, 9:21pm

It’s correct. I proved it during the contest. And then solved it.

tanmayaaeron · July 19, 2020, 9:36pm

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.