LONGESTARRAY - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Authors: satyam_343
Testers: iceknight1093, mexomerf
Editorialist: iceknight1093

DIFFICULTY:

2267

PREREQUISITES:

Prefix sums

PROBLEM:

You are given an array A. Find the largest possible value of r-l+1 such that A_l \mid A_{l+1} \mid \ldots \mid A_r = A_1 \mid A_2 \mid \ldots \mid A_{l-1} \mid A_{r+1} \mid \ldots \mid A_N.

Here, \mid denotes bitwise OR.

EXPLANATION:

Let M = A_1 \mid \ldots \mid A_N be the bitwise OR of all the elements.

Let’s call subarray [l, r] valid if its bitwise OR equals the bitwise OR of the rest of the array.

Note that the bitwise OR of any valid subarray must be M.

Why?

Let the bitwise OR of the subarray be x. Then, the outside also has bitwise OR x, and together they make up the whole array.
So, x\mid x = M, but x\mid x = x so we have x = M.

To phrase this differently, a subarray is valid if and only if, for each bit b that occurs in M,

  • A[l, r] contains an element with the b-th bit set; and
  • A[1, l-1] \cup A[r+1, N] contains an element with the b-th bit set.

Let’s use this fact.
Suppose we fix a position l. Let’s try to find the largest r such that [l, r] is valid: if we can do this for every l, the answer is the maximum value of r-l+1 among them all.

Now that l is fixed, let’s look at a specific bit b that is present in M.

  • If b is present somewhere in the subarray [1, l-1], then the ‘outside’ is good with respect to this bit.
  • Otherwise, we need to ensure that b is present after r.
  • In particular, if last_b is the last position that contains b, then we must have r \lt last_b.

Each b that is not present in the prefix gives us one such constraint on r. Apply all of them to obtain the maximum possible r we can get if we start at l.

Now, the outside is taken care of, so we need to check the inside.
That is, for each b, we need to check whether it appears in the range [l, r] or not.

Putting everything together, we require the following:

  • Given l and b, check whether [0, l-1] contains b
  • Given l, r, b, check whether [l, r] contains b
  • Given b, find last_b, the last index at which b appears

The last array in the third part can be precomputed by iterating across the array and just looking at each bit.

The first and second parts can be solved with the help of prefix sums.
Let P(i, b) denote the number of times b appears in [1, i]. Note that if we knew every P(i, b), then:

  • Checking whether b lies in [0, i-1] is the same as checking whether P(i-1, b) \gt 0
  • Checking whether b lies in [l, r] is the same as checking whether P(r, b) - P(l-1, b) \gt 0

P(i, b) can be calculated as follows:

  • If A_i contains the bit b, then P(i, b) = P(i-1, b) + 1
  • Otherwise, P(i, b) = P(i-1, b)

This allows us to compute every P(i, b) in \mathcal{O}(30N) time, and with this the rest of the problem can also be solved in \mathcal{O}(30N) as described above.

TIME COMPLEXITY:

\mathcal{O}(30\cdot N) per testcase.

CODE:

Setter's code (C++)
// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast,unroll-loops")

#include <bits/stdc++.h>   
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;   
using namespace std;  
#define ll long long  
const ll INF_MUL=1e13;
const ll INF_ADD=1e18;    
#define pb push_back                 
#define mp make_pair          
#define nline "\n"                           
#define f first                                          
#define s second                                             
#define pll pair<ll,ll> 
#define all(x) x.begin(),x.end()     
#define vl vector<ll>           
#define vvl vector<vector<ll>>    
#define vvvl vector<vector<vector<ll>>>          
#ifndef ONLINE_JUDGE    
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);  
#endif       
void _print(ll x){cerr<<x;}  
void _print(char x){cerr<<x;}   
void _print(string x){cerr<<x;}    
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());   
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";} 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=998244353;     
const ll MAX=500500;
ll freq[35][MAX];
void solve(){     
    ll n; cin>>n;
    vector<ll> till(35,n+1); 
    vector<ll> a(n+5,0);
    ll total=0;
    for(ll i=0;i<30;i++){
        freq[i][0]=0;
    }
    for(ll i=1;i<=n;i++){
        ll x; cin>>x;
        a[i]=x;
        total|=x; 
        for(ll j=0;j<30;j++){  
            freq[j][i]=freq[j][i-1]+min(1LL,x&(1<<j));
            if(x&(1<<j)){
                till[j]=i; 
            } 
        }
    }
    ll ans=-1,cur=0;
    for(ll i=1;i<=n;i++){
        ll l=n+1;
        for(ll j=0;j<30;j++){
            if(!(total&(1<<j))){  
                continue;   
            }  
            if(cur&(1<<j)){  
                ;
            }   
            else{
                l=min(l,till[j]);   
            }
        }  
        ll check=l>i;
        for(ll j=0;j<30;j++){
            if(!(total&(1<<j))){
                continue; 
            }
            if(freq[j][i-1] >= freq[j][l-1]){
                check=0;
            }
        }
        if(check){
            ans=max(ans,l-i);
        }
        cur|=a[i]; 
    }
    cout<<ans<<nline; 
    return;                                
}                                                     
int main()                                                                                             
{      
    ios_base::sync_with_stdio(false);                         
    cin.tie(NULL);    
    #ifndef ONLINE_JUDGE                   
    freopen("input.txt", "r", stdin);                                              
    freopen("output.txt", "w", stdout);  
    freopen("error.txt", "w", stderr);                        
    #endif                          
    ll test_cases=1;               
    cin>>test_cases; 
    while(test_cases--){
        solve();
    } 
    cout<<fixed<<setprecision(10);
    cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
}  
Editorialist's code (Python)
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	first, last = [-1]*31, [-1]*31
	ct = [[0 for _ in range(31)] for _ in range(n+1)]
	for i in range(n):
		for b in range(30):
			ct[i+1][b] = ct[i][b]
			if (a[i] >> b) & 1:
				last[b] = i
				ct[i+1][b] += 1
				if first[b] == -1: first[b] = i
	ans = -1
	for i in range(n):
		r = n-1
		for b in range(30):
			if first[b] < i: continue
			r = min(r, last[b]-1)
		if r < i: continue
		len = r-i+1
		for b in range(30):
			if first[b] == -1: continue
			have = ct[r+1][b] - ct[i][b]
			if have == 0: len = -1
		ans = max(ans, len)
	print(ans)
4 Likes

interesting problem

i do it in nlogn

Can anyone please tell, what I am doing wrong here (Only one test case is not passing).

Code Link

Thanks.

My two pointer approach :
https://www.codechef.com/viewsolution/82542097

Same for me as well!

Consider a case like

1
6
1 1 2 2 4 4

Oh yes. Thanks.
Taking mx as -1 gives an AC.

I am so noob so that after reading this problem I was not able to figure it out that it can be done using ( Binary search or two pointer) + sliding window

Solution given editorial of python Give TLE. Please do check
https://www.codechef.com/viewsolution/82582099

Pypy is a lot faster than Python, and is what should be used 99% of the time for competitive programming.

https://www.codechef.com/viewsolution/82588497 here’s the exact same code submitted in Pypy taking 0.78s, as you can see Python is (at least) 6-7 times slower

can someone explain me the implementation of binary search in this problem ?

Can anyone explain me, what I am doing wrong here (Only one test case is not passing).
click here

my without prefix sum approach here is my submission

Can anyone tell whats wrong in this code. giving TLE.
https://www.codechef.com/viewsolution/82604276

#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define neginf INT_MIN
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fo(i,a,b) for(int i=a;i<b;i++)
#define sorted(v) sort(all(v))
#define sorteda(v,n) sort(v,v+n)
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vint;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll mod = 1e9 + 7;
bool same(vector<ll> curr,vector<ll> all)
{
    for(int i=0;i<curr.size();i++)
    {
        if((curr[i]==0 and all[i]!=0) or (curr[i]!=0 and all[i]==0))
        {
            return false;
        }
    }
    return true;
}
bool help(vector<ll> a,vector<ll> all2,ll k,ll n)
{
   
    
    
    vector<ll> curr(32,0);
    for(int i=0;i<k;i++)
    {
        for(int j=0;j<32;j++)
        {
            if((a[i]&(1ll<<j)))
            {
                all2[j]--;
                curr[j]++;
            }
        }
    }
    if(same(curr,all2))return true;
    
    for(int i=k;i<n;i++)
    {
        for(int j=0;j<32;j++)
        {
            if((a[i]&(1ll<<j)))
            {
                all2[j]--;
                curr[j]++;
            }
        }
        
        for(int j=0;j<32;j++)
        {
            if((a[i-k]&(1ll<<j)))
            {
                all2[j]++;
                curr[j]--;
            }
        }
        if(same(curr,all2))return true;
    }
    return false;
}
void solve()
{
    ll n;
       cin>>n;

       vector<ll> a(n);
       
      
    
    vector<ll> v(32,0);
    
    for(int i=0;i<n;i++)
    { cin>>a[i];
         for(int j=0;j<32;j++)
        {
            if((a[i]&(1ll<<j)))
            {
                v[j]++;
            }
        }
    }
    ll low=1,high=n,mid,ans=-1;
    
    while(low<=high)
    {
     mid=low+(high-low)/2;
     if(help(a,v,mid,n))
     {
         ans=mid;
         low=mid+1;
     }
     else
     {
         high=mid-1;
     }
     
    }
     cout<<ans<<"\n"; 
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
       solve(); 
    }

}

https://www.codechef.com/viewsolution/82610435
why my code is tle plz help

code link: CodeChef | Competitive Programming | Participate & Learn
I followed the same approach discussed in the video editorial but my code gives TLE.
Please help me to resolve this.

1 Like

In the binary search solution if we do not get an answer for a window of size mid how to prove that there is no solution for window of size greater than mid ?

1 Like

I am really confused… I was trying binary search + sliding window during the contest. But after some time, I realised that binary search can’t be used here as the function used for applying binary search is not predicate. ( It might be possible that for length 1 and 3 there is no such subarray but the answer can be of length 2 ).

I am so noob that I am not able to convince myself even after trying for an hour. It would be great if someone can help me out. Thanks.

1 Like

Getting TLE for the exactly SAME OFFICIAL EDITORIAL CODE in tasks 4 and 5.

#include<bits/stdc++.h>
using namespace std;
#define nl    '\n'
#define int   long long


bool isSame(vector<int>& remOr, vector<int>& curOr){
    for(int i = 0; i < 31; i++){
        if((remOr[i] and !curOr[i]) or (!remOr[i] and curOr[i]))
            return 0;
    }
    return 1;
}

bool checkOr(vector<int>& ara, vector<int> remOr, int len){
    vector<int> curOr(32, 0);
    for(int i = 0; i < len; i++){
        for(int j = 30; j >= 0; j--){
            if(ara[i]&(1LL<<j)){
                curOr[j]++;
                remOr[j]--;
            }
        }
    }
    if(isSame(remOr, curOr)) return 1;

    for(int i = len; i < ara.size(); i++){
        for(int j = 30; j >=0; j--){
            if(ara[i-len]&(1LL<<j)){
                remOr[j]++;
                curOr[j]--;
            }
        }
        for(int j = 30; j >=0; j--){
            if(ara[i]&(1LL<<j)){
                curOr[j]++;
                remOr[j]--;
            }
        }
        if(isSame(remOr, curOr)) return 1;
    }
    return 0;
}

int32_t main(){
    int T; scanf("%lld", &T);
    for(int tc = 1; tc <= T; tc++){
        int n; scanf("%lld", &n);
        vector<int> ara(n), bitOr(32, 0);
        for(int i = 0; i < n; i++) {
            scanf("%lld", &ara[i]);
            for(int j = 30; j >= 0; j--){
                if(ara[i]&(1LL<<j)){
                    bitOr[j]++;
                }
            }
        }

        int lo = 1, hi = n, res = -1;
        while(lo <= hi){
            int mid = lo + ((hi - lo)>>1);
            if(checkOr(ara, bitOr, mid)){
                res = mid;
                lo = mid + 1;
            }
            else hi = mid - 1;
        }
        printf("%lld\n", res);
    }
}