OPERATION2 - Editorial

PROBLEM LINK:

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

Author: wuhudsm
Testers: iceknight1093, yash_daga
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Familiarity with bitwise operations, (optional) segment trees/sparse tables

PROBLEM:

You have N integers in a circle. In one move, you can pick two adjacent integers and replace both of them with either their bitwise AND or their bitwise OR.

Find the maximum possible difference between the remaining two elements.

EXPLANATION:

Suppose that x and y are the last remaining elements, with x \geq y.
Note that since we merge adjacent elements, x and y are essentially obtained from two disjoint (circular) subarrays of C.

For convenience, let’s rotate C so that x is formed from a prefix of C and y from a suffix.
That is, there exists an integer k (1 \leq k \lt N) such that x is formed by a sequence of operations on C[1:k] and y is formed from a sequence of operations on C[k+1:N].

Our objective is to maximize x - y. To this end, we have the following observations once k is fixed:

  • It’s always optimal for x to be the bitwise OR of C[1:k]
  • It’s always optimal for y to be the bitwise AND of C[k+1:N]
Proof

Maximizing x - y means making x large and y small. Once k is fixed, these are essentially independent min-max problems, so they can be solved separately.

Clearly, x can be no larger than the bitwise OR of C[1:k], since both operations are bitwise operations.
Similarly, y can be no smaller than the bitwise AND of C[k+1:N].

Both limits are attainable, and hence optimal.

This already gives us a solution in \mathcal{O}(N^2).
We can fix the ‘first’ element of the array to convert the circle into a line, as above.
Then, we can fix a value of k from 1 to N-1; and that gives us x and y as some prefix OR/suffix AND.

We now have to do two things: properly deal with the fact that we’re on a circle (and not an array), and speed this solution up.

Converting the circle to an array is quite easy: let’s duplicate C and append it to itself, i.e, create the array [C_1, C_2, \ldots, C_N, C_1, C_2, \ldots, C_N].
Notice that in this new 2N-length array, any subarray of length N corresponds to a rotation of C.
So, converting the circle to a line is simple: fix a value of i, then consider the subarray of length N starting from index i.

For a fixed starting point, our current solution takes \mathcal{O}(N) time (we go through every value of k).
We’ll now improve this.

We’ll use the fact that once the first element is fixed, there can’t be too many different values of x. In fact, there are at most 1 + \log_2{2^{30}} = 31 distinct prefix ORs.

Why?

Let P_i denote the i-th prefix OR of the array.
For any i, either P_i = P_{i-1} or P_i \gt P_{i-1}.

When P_i \gt P_{i-1}, that means C_i has at least one new bit, that hasn’t appeared in the first i positions.
However, there are only 30 bits in total among the array values. This means that once the prefix OR has increased 30 times, it can no longer increase — all the bits will be set.

This gives us at most 31 distinct prefix ORs in total.

So, instead of fixing a value of k and computing x, let’s fix the value of x and compute k and y.
This gives us \mathcal{O}(30\cdot N) possible pairs of (x, y); so compute them all and take the maximum difference among them.

All that remains is actually computing k and y once x is fixed.

How do I do that?

We want to quickly find the positions where the prefix ORs change.
This can be done by finding, for each bit that’s not set in the current prefix OR, its next closest appearance in the array. The minimum of all such values is what we’re looking for.

This can be found if we do a bit of precomputation.
Let \text{next} be a 2-D array such that \text{next}(i, b) = j means j \geq i is the first position such that A_j has bit b set.
This can be computed by iterating over i in descending order, as:

  • If A_i has bit b set, then \text{next}(i, b) = i
  • Else, \text{next}(i, b) = \text{next}(i+1, b)

With this precomputed, we’re good to go!

Let’s say that we’re considering the rotation starting at i, i.e, the subarray [i, i+N-1].
Then, the prefix ORs can be computed as follows:

  • Let \text{cur} denote the current prefix OR, and \text{pos} denote the position of the prefix giving that OR. Initially, \text{cur} = C_i and \text{pos} = i.
  • Finding the next prefix OR is now easy: for each bit b that’s not set in \text{cur}, look at \text{next}(\text{pos}, b) and take the minimum of all such positions that you find.
  • This then tells you the new value of \text{pos}.
  • After updating \text{pos}, \text{cur} can be updated as \text{cur} \mid C_{pos}.
  • Finally, the AND of the remaining array is the AND of everything after \text{pos} (upto length N, of course)
    • Notice that this is just a subarray AND query, and can be quickly computed using a segment tree or sparse table.
  • Once \text{cur} and the subarray AND of the remaining part are known, maximize the answer with their difference.

It’s also possible to implement this without any such data structures, using only prefix and suffix ANDs and ORs of C — see the editorialist’s implementation for this.

TIME COMPLEXITY:

\mathcal{O}(N\log^2 {M}) per testcase, where M = 2^{30} here.

CODE:

Setter's code (C++, sparse table)
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n,ans;
int a[N],lg2[N];
int OR[N][LOGN],AND[N][LOGN];

void init()
{
	for(int i=1;i<=n;i++) a[i+n]=a[i];
	n<<=1;
	for(int i=1;i<=n;i++) lg2[i]=(int)log2(i);
	for(int i=1;i<=n;i++) OR[i][0]=AND[i][0]=a[i];
	for(int i=1;i<LOGN;i++)
	{
		for(int j=1;j<=n;j++)
		{
			int p=j+(1<<(i-1));
			if(p>n) OR[j][i]=OR[j][i-1],AND[j][i]=AND[j][i-1];
			else    OR[j][i]=(OR[j][i-1]|OR[p][i-1]),AND[j][i]=(AND[j][i-1]&AND[p][i-1]);
		}
	}
	n>>=1;
}

int getOR(int L,int R)
{
	int t=lg2[R-L+1];
	return (OR[L][t]|OR[R-(1<<t)+1][t]);
}

int getAND(int L,int R)
{
	int t=lg2[R-L+1];
	return (AND[L][t]&AND[R-(1<<t)+1][t]);
} 

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		init();
		ans=0;
		for(int i=1;i<=n;i++)
		{
			int cur=i,L,R,M;
			while(1)
			{
				ans=max(ans,(int)abs(getOR(i,cur)-getAND(cur+1,i+n-1)));
				L=cur;R=i+n-1;
				while(L+1!=R)
				{
					M=(L+R)>>1;
					if(getOR(i,cur)==getOR(i,M)) L=M;
					else R=M;
				}
				if(R==i+n-1) break;
				cur=R;
			}
		}
		printf("%d\n",ans);
	}
	
	return 0;
}
Tester's code (C++, segment tree)
//clear adj and visited vector declared globally after each test case
//check for long long overflow   
//Mod wale question mein last mein if dalo ie. Ans<0 then ans+=mod;
//Incase of close mle change language to c++17 or c++14  
//Check ans for n=1 
#pragma GCC target ("avx2")    
#pragma GCC optimize ("O3")  
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>                   
#include <ext/pb_ds/assoc_container.hpp>  
// #define int long long     
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);cout.precision(dbl::max_digits10);
#define pb push_back 
#define mod 1000000007ll //998244353ll
#define lld long double
#define mii map<int, int> 
#define pii pair<int, int>
#define ll long long 
#define ff first
#define ss second 
#define all(x) (x).begin(), (x).end()
#define rep(i,x,y) for(int i=x; i<y; i++)    
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>
#define setbits(x) __builtin_popcountll(x)
#define print2d(dp,n,m) for(int i=0;i<=n;i++){for(int j=0;j<=m;j++)cout<<dp[i][j]<<" ";cout<<"\n";}
typedef std::numeric_limits< double > dbl;
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
const long long N=400005, INF=2000000000000000000;
const int inf=2e9 + 5;
lld pi=3.1415926535897932;
int lcm(int a, int b)
{
    int g=__gcd(a, b);
    return a/g*b;
}
int power(int a, int b, int p)
    {
        if(a==0)
        return 0;
        int res=1;
        a%=p;
        while(b>0)
        {
            if(b&1)
            res=(1ll*res*a)%p;
            b>>=1;
            a=(1ll*a*a)%p;
        }
        return res;
    }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int getRand(int l, int r)
{
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}
int all_set=((1 << 30) - 1);
int ar[N], st[4*N];

void build(int v, int l, int r)
{
    if(l==r)
    {
        st[v]=ar[l];
        return;
    }
    int m=(l+r)/2;
    build(v*2, l, m);
    build((v*2)+1, m+1, r);
    st[v]=(st[v*2]&st[(v*2)+1]);
}
int query(int v, int tl, int tr, int l, int r)
{
    if(l>r)
    return all_set;
    if(tl==l&&tr==r)
    return st[v];
    int tm=(tl+tr)/2;
    return (query((2*v), tl, tm, l, min(tm, r))&query((2*v)+1, tm+1, tr, max(tm+1, l), r));
}

int32_t main()
{
    IOS;
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        rep(i,0,n)
        cin>>ar[i];
        rep(i,n,2*n)
        ar[i]=ar[i-n];
        int N=(2*n);
        build(1, 0, N-1);
        stack <int> q[30];
        for(int i=N-1;i>=0;i--)
        {
            for(int j=0;j<30;j++)
            {
                if(ar[i]&(1 << j))
                q[j].push(i);
            }
        }
        int ans=0;
        for(int i=0;i<n;i++)
        {
            int cur=ar[i];
            vector <int> bits;
            for(int j=0;j<30;j++)
            {
                if(cur&(1 << j))
                    q[j].pop();
                else if(q[j].size())
                    bits.pb(q[j].top());
            }
            sort(all(bits));
            ans=max(ans, abs(cur-query(1, 0, N-1, i+1, i+n-1)));
            // cout<<cur<<" "<<query(1, 0, N-1, i+1, i+n)<<"\n";
            for(int p:bits)
            {
                cur|=ar[p];
                if(p<i+n-1)
                {
                    // cout<<p.ff<<" "<<p.ss<<" "<<i+n-1<<" "<<query(1, 0, N-1, p.ff+1, i+n-1)<<"\n";
                    ans=max(ans, abs(cur-query(1, 0, N-1, p+1, i+n-1)));
                }
                if(p>i+100000)
                break;
            }
        }
        // ans=min(ans, (int)1e9+5);
        cout<<ans<<"\n";
    }
}
Editorialist's code (C++, prefix AND/OR)
#include "bits/stdc++.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	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<int> pref_and(n), suf_and(n);
		vector<int> pref_or(n), suf_or(n);
		for (int i = 0; i < n; ++i) {
			pref_and[i] = pref_or[i] = a[i];
			if (i) {
				pref_and[i] &= pref_and[i-1];
				pref_or[i] |= pref_or[i-1];
			}
		}
		for (int i = n-1; i >= 0; --i) {
			suf_and[i] = suf_or[i] = a[i];
			if (i+1 < n) {
				suf_and[i] &= suf_and[i+1];
				suf_or[i] |= suf_or[i+1];
			}
		}
		auto get_and = [&] (int L, int R) {
			int ret = INT_MAX;
			if (L) ret &= pref_and[L-1];
			if (R+1 < n) ret &= suf_and[R+1];
			return ret;
		};
		auto get_or = [&] (int L, int R) {
			int ret = 0;
			if (L) ret |= pref_or[L-1];
			if (R+1 < n) ret |= suf_or[R+1];
			return ret;
		};

		array<int, 30> next_one, next_zero;
		for (int i = 0; i < 30; ++i) next_one[i] = next_zero[i] = n;

		int ans = 0;
		array<int, 31> jumps; jumps[30] = n;
		for (int i = n-1; i >= 0; --i) {
			for (int b = 0; b < 30; ++b) {
				if (a[i] & (1 << b)) next_one[b] = i;
				else next_zero[b] = i;
			}
			
			// subarray or
			int cur = a[i];
			for (int b = 0; b < 30; ++b) {
				if (a[i] & (1 << b)) jumps[b] = n;
				else jumps[b] = next_one[b];
			}
			sort(begin(jumps), end(jumps));
			for (int b = 0; b < 30; ++b) {
				if (jumps[b] != jumps[b+1]) {
					if (i > 0 or jumps[b] < n) ans = max(ans, abs(cur - get_and(i, jumps[b]-1)));
					if (jumps[b] < n) cur |= a[jumps[b]];
				}
			}

			// subarray and
			for (int b = 0; b < 30; ++b) {
				if (~a[i] & (1 << b)) jumps[b] = n;
				else jumps[b] = next_zero[b];
			}
			sort(begin(jumps), end(jumps));
			cur = a[i];
			ans = max(ans, abs(cur - get_or(i, i)));
			for (int b = 0; b < 30; ++b) {
				if (jumps[b] != jumps[b+1]) {
					cur &= a[jumps[b]];
					ans = max(ans, abs(cur - get_or(i, jumps[b])));
				}
			}
		}
		cout << ans << '\n';
	}
}
1 Like

Hello, can someone please tell me how this solution passed 14/15 test cases. I dont have any knowledge of segment trees.

Was it dumb luck or was it really close ??

#include <bits/stdc++.h>

#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define sp ' '
#define nl '\n'
#define ll long long
#define ull unsigned long long
#define all(v) v.begin(),v.end()
#define vi vector<int>
#define range(a , min , max) a >= min and a <= max

using namespace std;

void solve() {
    int n;
    cin >> n;
    
    vector<int> v(n);
    for(int i = 0; i < n; i ++) {
        cin >> v[i];
    }
    sort(all(v), greater<int>());
    
    int and_res = v[n - 1];
    int or_res = v[0];
    
    int maxm = 0;
    
    int i = 1, j = n - 2;
    for(int i = 1; i <= n - 2; i ++) {
        and_res &= v[i];
        or_res |= v[j];
        
        maxm = max(maxm , or_res - and_res);
        
        j --;
    }
    
    cout << maxm << nl;
}

int main() {
    int tc;
    cin >> tc;
    while(tc--) {
        solve();
	}

    return 0;
}

solution link : CodeChef: Practical coding for everyone

@iceknight1093 could you please look into this submission of mine? I think it’s a hack. I only find one value for each fixed first element, but do it in both the forward and the backward orders.

Update: missing test case:

1
3
3 5 6 

Expected: 5 (6 - 3 & 5 = 6 - 1 = 5). Output: 4.

Unfortunately it seems like the tests were indeed weak. afair we tested for finding a small number of jumps (and in a similar vein, small subarray size) from each element forward, but not backward.

Pure luck, the fact that the array is being sorted is already wrong (the answer depends on subarrays of the original array, sorting it breaks subarray structure completely)

Is it possible to use ternary search in this problem? for each i (1<=i<=n) find max difference in segment [i, i+n-1] using ternary search…

Ans: No.
Logic: Ternary search only works for strictly increasing and strictly decreasing function. Here this property is not followed.