ORTHODOX - Editorial

editorial
, , , ,
129

It is not O(n^2) if n > 62, because then it is O(1) because we just check whether n > 62. It becomes O(62^2) otherwise. So a total of O(Tx62x62) operations are required where T is the number of test cases. :slightly_smiling_face:

1 Like
130

By the way, I am still trying to understand the proof of why the answer is “NO” if n is greater than 62. :thinking:

131

Can anybody explain it more intuitively?

132

Can anyone help me find out that why am I getting a WA with the following code?

t = int(input())
for _ in range(t):
    n = int(input())
    arr = list(map(int, input().split()))
    if n > 62:
        print("NO")
    else:
        isThere = []
        flag = False
        for i in range(n):
            for j in range(i,n):
                val = (arr[i]|arr[j])
                if val in isThere:
                    flag = True
                    break
                isThere.append(val)
            if flag: break
        if flag: print("NO")
        else: print("YES")
133

Why for n>=100 Answer is Zero ?

134

Why for n>=100, Answer is zero bro ?

135

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");			
		}
	}
}
136

Very Nice Editiorial…
please post all the editiorials in such fashion.

1 Like
137

This question was a waste of time. 2 hours and no solution. :expressionless:

138

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 :pleading_face: :pleading_face:

submission:link

139

U r not able to solve that doesn’t means it’s waste of time .

1 Like
140

Many peoples copied from net , and due to this relative increment in rating is less .

141

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?

143

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
144

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 :pleading_face: :pleading_face: :pleading_face:

submission:link

145

yeah ,I tried standard brute force knowing it would fetch me TLE but that n>62 was nowhere near my head xp

146

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
147

The case you mentioned is right

148

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

149

You can refer to my explanation I have commented below. It may help