ORTHODOX - Editorial

editorial
, , , ,
42

Another code that goes on to check for O(n^2) and gets AC: CodeChef: Practical coding for everyone

2 Likes
43

Why if n>62 answer is always no? Can someone explain please

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: