ORTHODOX - Editorial

editorial
, , , ,
44

I used different logic(although I think it’s wrong but accepted :crazy_face:). What I did is I traverse the array and just calculate the OR of all elements till now and stored in a map. If any time I get the same value I simply return NO. Then I traverse the array from back and do the same procedure(calculating OR value till now and Check in the map)…This is O(n) solution. Can Anybody confirm me this logic is correct or not? I got Correct Answer verdict but still I think there is some problem. LInk to My Solution

4 Likes
45

Could be done in linear time as well

1 Like
46

could anyone plz explain where my code goes wrong?`

my solution

47

I can’t actually prove it but If N goes beyond 70 then then loop will break definitely because that OR value will occur again. In worse case you can take all the powers of 2 , i.e. that will be 264. So only 64 values are there for which these loop run completely.

4 Likes
48

same yrr 10^5 n is not supposed to run in n2

1 Like
49

Yeah, N is 1 and Ai is 0.

1 Like
50

Can anyone tell me why does my solution work? I have no idea.

I use following logic:
Let v[i] = A[0] or A[1] or ... A[i]
and w[i] = A[i] or A[i+1] ... A[n-1]
then check if v is strictly increasing and w is strictly decreasing or not.

void test_case() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    vector<int> v(n), w(n);
    bool distinct = true;
    v[0] = a[0];
    for (int i = 1; i < n; i++) {
        v[i] = v[i-1] | a[i];
        if (v[i] == v[i-1]) {
            distinct = false;
            break;
        }
    }
    w[n-1] = a[n-1];
    for (int i = n-2; i >= 0; i--) {
        w[i] = w[i+1] | a[i];
        if (w[i] == w[i+1]) {
            distinct = false;
            break;
        }
    }
    if (distinct) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
}

Submission: link

51

Anyone wanna understand why if array size > 60 answer is NO else check via brute force

2 Likes
52

I explained it here. :crazy_face:

1 Like
53

Guess what even N^3 solution is getting accepted

1 Like
54

Seems correct. I think this can also be prove by pigeonhole principal.

55

My Last Approach was Same as of yours and I got WA

56

This problem had a pigeon hole kind of reasoning. The key observation was that the answer is “NO” whenever N > 64. We can check using the quadratic complexity algorithm in other cases.

57

and what is N here , Link to solution ?

58

I think I’m only dumb person here. Who neither submitted bruteforce solution ( Though I coded it) nor searched on google for this problem (Solution was on gfg).

59

What was the intuition behind this approach?

60

I’ve seen such solutions too.

61

Yes please :pleading_face:

62

The idea behind this logic is simple …If two substring have same OR value then OR value from the start(or may be end) will become steady at second substring .

1 Like
63

Can someone please look into my code and explain where i was going wrong.
The method was: first i have built a prefix matrix whose i,j th element stores among elements in the range [0,…,j] total number of elements whose i th bit is set.

Then i have considered all possible ranges [1 <= l <=r <=n] and using the prefix matrix found out which of the 64 bits should be set in the answer for that particular range (the OR of all elements in the given range).

Like this OR values of all ranges are obtained. Then i just check if all of them are unique or not.

https://www.codechef.com/viewsolution/35813258