ORTHODOX - Editorial

PROBLEM LINK:

Contest

Author: Shahjalal Shohag
Tester: Ildar Gainullin
Editorialist: Rajarshi Basu

DIFFICULTY:

Easy

PREREQUISITES:

Observation

PROBLEM:

You are given an integer sequence A_1, A_2, \ldots, A_N. For any pair of integers (l, r) such that 1 \le l \le r \le N, let’s define \mathrm{OR}(l, r) as A_l \lor A_{l+1} \lor \ldots \lor A_r. Here, \lor is the bitwise OR operator.

In total, there are \frac{N(N+1)}{2} possible pairs (l, r), i.e. \frac{N(N+1)}{2} possible values of \mathrm{OR}(l, r). Determine if all these values are pairwise distinct.

  • N \leq 10^5
  • 0 \leq A_i \leq 10^{18}

EXPLANATION:

Brief Explanation
  • If number of elements is more than \log_2 10^{18} \approx 62 then answer is NO.
  • Else just bruteforce all possible ranges.


Some initial thoughts

The question involves bitwise operators. When you see bitwise operators involved, it’s safe to say there might be something to do with … well… bits. Further, it feels like the number of possible different values of subarray OR cannot be too many, and seems to be much lesser than O(n^2) in any case. Maybe this can be explored further?

What makes a number important

Let us say we have some range of numbers A[L \dots R]. Let us say we add another number, in particular A[R+1] (so our final range is A[L \dots R+1]). When will the OR value of this range be different than the previous A[L \dots R] range? When A[R+1] adds some ”new information” right?

What is this new information?

Well, this new information is basically some bit i that was not set in V_1 = A[L] \vee A[L+1] \vee \dots \vee A[R]. Is this true? What does this mean for the problem? Does it hint towards a solution? Think!

Main Observation
Part 1

Let there be two indices i and j such that A[i] \vee A[j] = max(A[i],A[j]). You can think of this meaning that all of the bits set in A[j] is also set in A[i], or vice versa, for some i,j. In such a scenario, the solution is not possible. Here’s why.

  • Let’s assume that i < j.
  • Now consider V_1 = (A[i] \vee A[i+1\ \vee A[i+2] \vee \dots \vee A[j-1]).
  • Now consider V_2 = V_1 \vee A[j]
  • We know that each bit k set in A[j] is also set in A[i], and therefore in V_1. Thus, from there we get that V_2 = V_1.

How do we utilise this to simplify the problem? Move on to Part 2 if you can’t figure it out.

Part 2

There are only 62 bits for a number till 10^{18} !!


Full Solution
  • If number of elements is more than \log_2 10^{18} \approx 62 then answer is NO.
  • Else just bruteforce all possible ranges.

SOLUTIONS:

Setter’s Code
#include<bits/stdc++.h>
using namespace std;
 
const int N = 1e5 + 9;
const long long M = 1e18;
 
long long a[N];
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    assert(1 <= t && t <= 300);
    int sum = 0;
    while (t--) {
        int n; cin >> n;
        assert(1 <= n && n <= 100000);
        sum += n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            assert(0 <= a[i] && a[i] <= M);
        }
        if (n > 60) {
            cout << "NO\n";
            continue;
        }
        set<long long> se;
        bool ok = true;
        for (int i = 1; i <= n; i++) {
            long long cur = 0;
            for (int j = i; j <= n; j++) {
                cur |= a[j];
                if (se.find(cur) != se.end()) {
                    ok = false;
                    break;
                }
                se.insert(cur);
            }
            if (!ok) break;
        }
        if (ok) cout << "YES\n";
        else cout << "NO\n";
    }
    assert(1 <= sum && sum <= 300000);
    return 0;
} 
Tester’s Code
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
 
using namespace std;
 
typedef long long ll;
 
#ifdef iq
  mt19937 rnd(228);
#else
  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
 
int main() {
#ifdef iq
  freopen("a.in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector <ll> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    if (n >= 100) {
      cout << "NO\n";
    } else {
      set <ll> q;
      for (int i = 0; i < n; i++) {
        ll x = 0;
        for (int j = i; j < n; j++) {
          x |= a[j];
          q.insert(x);
        }
      }
      if (q.size() == n * (n + 1) / 2) {
        cout << "YES\n";
      } else {
        cout << "NO\n";
      }
    }
  }
}
25 Likes

I have seen many code that fail for the test case
1
3
12 2 7
Why are there always weak test case in codechef?
Please work hard on test cases

16 Likes

Hey, Mine logic is also a bit similar. I counted all the bits in two vectors bits and bits1. Then from 0 to N, I checked for each i if we exclude the elements from 0 to I then will the OR value change. If the OR value doesn’t change then we know that answer will be NO and break the loop. I had done same for N-1 to 0.

Here is my code inside testcase loop :

        int n; cin >> n; 
        unordered_set<int>s;
        vector<int>bits(100); 
        vector<int>bits1(100); 
        vector<int>v(n);
        bool ok =true;
        for(int i = 0;i<n;++i){
            int x; cin >> x; 
            v[i] = x;
            if(x == 0){ok = false;}
            if(!ok)continue;
            if(s.find(x)!=s.end()){
                ok = false;
            }
            s.insert(x);
            for(int j=0;j<=64;++j){
                if(x&(1ll<<j)){
                    bits[j]++;
                    bits1[j]++;
                }
            }
        }
        if(ok){
            bool changed = false; 
            for(int i = 0;i<n;++i){
                for(int j=0;j<=64;++j){
                    if(v[i]&(1ll<<j)){
                        bits[j]--;
                        if(bits[j] == 0){
                            changed = true;
                        }
                    }
                }
                if(!changed){
                    ok = false;
                    break;
                }
            }
        }
        if(ok){
            bool changed = false; 
            for(int i = n-1;i>=0;--i){
                for(int j=0;j<=64;++j){
                    if(v[i]&(1ll<<j)){
                        bits1[j]--;
                        if(bits1[j] == 0){
                            changed = true;
                        }
                    }
                }
                if(!changed){
                    ok = false;
                    break;
                }
            }
        }
        if(!ok){
            cout <<"NO" << '\n';
        }else{
            cout << "YES" << '\n';
        }
    }
2 Likes

Next time please take care man :

https://leetcode.com/problems/bitwise-ors-of-subarrays/
https://www.geeksforgeeks.org/count-distinct-bitwise-or-of-all-subarrays/

21 Likes

You people always destroy a good problem by making weak test cases

14 Likes

Is answer “NO” for this testcase ?

bhai mera solution wrong hai, koi idea kidhar mistake hai ?

yaa most of the submissions of this problem are in python which is the direct given code on gfg…

5 Likes

Ya you are correct

There’s an easier argument:
If two subarrays need to have same OR value, that means the two subarray’s diff elements should OR to the same or less value (bitwise) of the common elements of the two subarray.
What this means, is that, A[0…n] and A[0…n+1] can have same OR value only if A[n] and A[n+1] are overlapping => A[n]|A[n+1] = max(A[n],A[n+1])
And A[0…n+2] can have same OR value as A[0…n] only if A[0…n+1] have the same OR value.
This implies that we need to check from 0…n-1 with each array value OR’d to the OR value, if for two elements side by side, the values are same => answer is no.
We need to check from n-1…0 as well as it can occur from both sides of the array

6 Likes

Please link submissions that fail this test-case

Your code gives No if input is just one element - 0.

3 Likes

Didn’t expected that this will be done in O(n^2) … wasted 2 hours over thinking about optimized solution …
RIP ratings

18 Likes

no bro, i just checked, total pages of submission are 83, and pages for python submission are 4, so, rest 79 pages are for c++ or java or any other language.

Answer was just a google search away…
Please take case of this…

Link 1: https://www.geeksforgeeks.org/count-distinct-bitwise-or-of-all-subarrays/
Link 2: https://leetcode.com/articles/bitwise-ors-of-subarrays/

anyone can just find the total distinct OR values of that array by this code:
https://www.tutorialspoint.com/bitwise-ors-of-subarrays-in-cplusplus
and simply check if ((n*(n+1))/2) is equal to the above result or not. If its equal print yes. else no.

check out the soultion:
https://www.codechef.com/viewsolution/35817176

10 Likes

Tester code is superb , same like THIS

Link
There are many.

I have do this with another logic & this also accepted.

#include <stdio.h>
#include<math.h>

typedef long long int ll;

int cmpfunc(const void a,const void b){
if(
(ll
)a==(ll)b) return 0;
else if((ll)a>(ll)b) return 1;
else return -1;
}

int main()
{
int t,n,flag,l;
scanf("%d",&t);
while(t–)
{
scanf("%d",&n);
l=2*(n-1);
ll a[n],b[n],c[l],total=0,left=0,right=0;flag=1;
for(int i=0;i<n;i++)
{
scanf("%lld",&a[i]);
b[i]=a[i];
total|=a[i];
}
qsort(a,n,sizeof(ll),cmpfunc);
for(int i=1;i<n;i++)
{
if(a[i]==a[i-1])
{
printf(“NO\n”);
flag=0;
break;
}
}
if(flag)
{
for(int i=0;i<n-1;i++)c[(2i)]=(left|=b[i]);
for(int i=n-1;i>0;i–)c[(2
(i-1))+1]=(right|=b[i]);
qsort(c,l,sizeof(ll),cmpfunc);
for(int i=0;i<l;i++)
{
if((i!=0)&(c[i]==c[i-1])){flag=0;break;}
if(c[i]==total){flag=0;break;}
}
if(!flag)printf(“NO\n”);
else printf(“YES\n”);
}
}
}

Weak Test Case for ORTHODOX

Input:

1 
3
1 50 99

Output:

NO

I have seen Solutions where the Output is YES.
@admin

2 Likes

Bhai koi plz mujhe ye answer smjha dega, meko bilkul smjh nhi aaya ye answer.

Please bhaiyo.