LONGESTARRAY - Editorial

editorial
, ,
23 
bool possible(vector<int> &bits, vector<int> &cur)
{
  for (int i = 0; i < 30; i++)
  {
    if ((cur[i] > 0) != (bits[i] > 0))
      return 0;
  }
  return 1;
}
bool reset(long long num, long long add, vector<int> &bits, vector<int> &cur)
{
  bool f = 1;
  for (int i = 0; i < 30; i++)
  {
    if (num & (1ll << i))
    {
      bits[i]++;
      cur[i]--;
    }
    if (add & (1ll << i))
      bits[i]--, cur[i]++;
    if ((cur[i] > 0) != (bits[i] > 0))
      f = 0;
  }
  return f;
}
bool check(int mid, vector<long long> &a, vector<int> bits)
{
  int n = a.size();
  vector<int> cur(30, 0);
  for (int i = 0; i < mid; i++)
  {
    for (int j = 0; j < 30; j++)
    {
      if (a[i] & (1ll << j))
        bits[j]--, cur[j]++;
    }
  }

  if (possible(bits, cur))
    return 1;
  for (int i = mid; i < n; i++)
  {
    if (reset(a[i - mid], a[i], bits, cur))
      return 1;
  }
  return 0;
}
void solve()
{
  int n;
  cin >> n;
  vector<long long> a(n);
  vector<int> bits(30, 0);
  for (int i = 0; i < n; i++)
  {
    cin >> a[i];
    for (int j = 0; j < 30; j++)
    {
      if (a[i] & (1ll << j))
        bits[j]++;
    }
  }
  // for (int j = 0; j < 3; j++)
  //   cout << bits[j] << ' ';
  // cout << endl;
  int ans = -1;
  int low = 1, high = n;
  while (low <= high)
  {
    int mid = (low + high) / 2;
    if (check(mid, a, bits))
    {
      ans = mid;
      low = mid + 1;
    }
    else
      high = mid - 1;
  }
  cout << ans << endl;
}

giving tle for last 2 test files , So tight constraints

24

My submission using

  1. PrefixSum
  2. Segment Tree
  3. pointers
    approach

Solution : CodeChef: Practical coding for everyone

25

I am using binary search + prefix sum method but getting WA for once case only
I read through this thread and saw the testcase:
1
6
1 1 2 2 4 4
But my code gives -1 for this which I think is correct , so thats not the problem.
Can someone please help me find the error in my code. Thank you.

#include <bits/stdc++.h>
using namespace std;

int rangeOr (vector<vector<int>> &ora,int l,int r){
    int ans=0;
    for(int j=0;j<32;j++){
        if(l==0){
            if(ora[r][j]>0)
                ans |= (1<<j);
        }
        else{
            if(ora[r][j]-ora[l-1][j] > 0)
                ans |= (1<<j);
        }
    }
    return ans;
}

bool check(vector<vector<int> > &ora,int len){
    int n = ora.size();

    for(int i=0;i+len-1<n;i++){
        if(i==0){
            int lor = rangeOr(ora,0,len-1);
            int ror = rangeOr(ora,len,n-1);
            if(lor == ror) return 1;
        }
        else if (i+len==n){
            int lor = rangeOr(ora,0,i-1);
            int ror = rangeOr(ora,i,n-1);
            if(lor == ror) return 1;
        }
        else{
            int left = rangeOr(ora,0,i-1);
            int mid = rangeOr(ora,i,i+len-1);
            int right = rangeOr(ora,i+len,n-1);
            if(mid == (left | right)) return 1;
        }
    }
   return 0;
}

int main(){
    int t;cin>>t;
    while(t--){
        int n; cin>>n;
        vector<int> a(n);
        for(int i=0;i<n;i++) cin>>a[i];
        vector<vector<int> > ora(n,vector<int>(32,0));
        
        for(int j=0;j<32;j++){
            for(int i=0;i<n;i++){
                if(a[i] & (1<<j)){
                    ora[i][j]=1;
                }
            }
        }

        for(int i=1;i<n;i++){
            for(int j=0;j<32;j++){
                ora[i][j] += ora[i-1][j];
            }
        }

        int ans=-1;
        int lo=1,hi=n-1;
        while(lo<=hi){
            int mid = lo + (hi-lo)/2;
            if(check(ora,mid)){
                ans = mid;
                lo = mid+1;
            }
            else
                hi = mid-1;
        }
        cout<<ans<<endl;
    }
    return 0;
}
1 Like
26

Why my code is giving is giving WA on 1 t.c → 

class segement{
public:
	vector<int> tree;
	int n ;

	segement(){}
	segement(vector<int>&arr){build(arr);}

	void build(vector<int>&arr){
		n = arr.size();
		tree.resize(2*n, 0);

		for(int i=0; i<n; i++){tree[n+i]=arr[i];}

		for(int i=(n-1); i>0; --i){
			tree[i] = tree[i<<1] | tree[i<<1 | 1];	
		}
	}

	// 0 based indexing.
	int query(int l, int r){  // both inclusive
		r++;
		if(l==r){return tree[r+n-1];}
		int res = 0;
		for(l += n, r += n; l < r; l >>= 1, r >>= 1){
			if(l&1){res = tree[l++] | res;}
			if(r&1){res = tree[--r] | res;}
		}
		return res;
	}

};

vi prefix, suffix;

int getOut(int L, int R){
    int left = 0, right = 0;

    if((L-1)>=0){left=prefix[L-1];}
    if((R+1)<suffix.size()){right=suffix[R+1];}

    return left | right;
}

bool isPossible(int sz, vi&v, segement&tree){
    if(sz==0){return 1;}

    for(int L=0; L<=(v.size()-sz); L++){
        int R = L+sz-1;
        int in_orr = tree.query(L, R);
        int out_orr = getOut(L,R);
        if(in_orr==out_orr){return 1;}
    }

    return 0;
}

int32_t main()
{
    RISHI
    int T; cin>>T;
    while(T--)
    {
        int n; cin>>n;
        vi v(n);
        F(0,n,i){cin>>v[i];}

        segement tree(v);

        prefix.resize(n);
        suffix.resize(n);

        prefix[0] = v[0];
        suffix[n-1] = v[n-1];

        F(1,n,i){
            prefix[i] = v[i] | prefix[i-1];
        }
        Rev(n-2, 0, i){
            suffix[i] = v[i] | suffix[i+1];
        }

        int low = 0, high = n;
        
        while(low<=high){
            int mid = (low+high)/2;

            bool can = isPossible(mid, v, tree);
            if(can){
                low = mid+1;
            }
            else{
                high = mid-1;
            }
        }

        if(high==0){high--;}
        cout<<high<<"\n";
    }

}
27

Same problem here, have you debugged it ?