# XORARRAY - Editorial

Author: Ritul Kumar Singh
Testers: Nishank Suresh, Satyam
Editorialist: Nishank Suresh

2897

# PREREQUISITES:

Binary search or 2-pointers

# PROBLEM:

You have an array A of distinct elements. You can choose an integer X and set A_i \gets A_i \oplus X for every 1 \leq i \leq N.

If X is chosen optimally, what is the maximum possible length of the longest increasing subarray of the final array?

# EXPLANATION:

We want the longest increasing subarray, so let’s look at some specific subarray and see where that gets us.
Suppose we want to make the subarray [A_L, A_{L+1}, \ldots, A_R] increasing. Then, it’s enough to choose X so that A_L \lt A_{L+1}, A_{L+1} \lt A_{L+2}, \ldots, A_{R-1} \lt A_R.
That is, we only really care about adjacent elements: making them increasing automatically makes the subarray as a whole increasing.

So, let’s look at adjacent elements A_i and A_{i+1}. Suppose we make A_i \lt A_{i+1} after xor-ing with X. What sort of restrictions would this put on X?

Note that only the highest differing bit between A_i and A_{i+1} matters, since this is what determines when one binary number is larger than another.
So, let k be the highest differing bit between A_i and A_{i+1} (for example, the highest differing bit between 4 = 100_2 and 5 = 101_2 is 0 (2^0 = 1), and the highest differing bit between 4 = 100_2 and 7 = 111_2 is 1 (2^1 = 2)).

• If A_i \lt A_{i+1} originally, then the k-th bit is set in A_{i+1} and not in A_i. Any X we choose must have the k-th bit unset to preserve this inequality.
• If A_i \gt A_{i+1} originally, then the k-th bit is set in A_{i} and not in A_{i+1}. Any X we choose must have the k-th bit set to reverse this inequality.

The other bits in X can be anything, only this bit has a restriction.

So, let’s compute an array B of length N-1, where B_i denotes the type of restriction on X needed for A_i \lt A_{i+1} to hold. Computing B is easy to do: simply iterate across bits in descending order and find out when A_i and A_{i+1} differ.

Now, note that making an array [L, R] increasing is equivalent to saying that we consider all the restrictions B_L, B_{L+1}, \ldots, B_R, and there are no conflicts between them. A conflict here is a situation where, for some bit k, the restrictions tell us that it must be both on and off: this is clearly impossible.

So, let’s fix the left endpoint L. Then, let’s find the largest possible R such that there is no conflict between relations B_L, \ldots, B_{R-1}. The largest possible increasing subarray starting at L is then [L, R], with length R-L+1.
Doing this for every L and taking the maximum length across all of them will give us our answer.
However, this is an \mathcal{O}(N^2) algorithm: how do we improve it?

To speed this up, we notice that the optimal right endpoints form a non-decreasing function.
That is, if R_1 and R_2 are the optimal endpoints for L_1 and L_2 respectively, and L_1 \leq L_2, then R_1 \leq R_2.
This is easy to prove: simply note that if [L, R] has no conflicts, then [L+1, R] also has no conflicts.

This tells us that our algorithm can be optimized using a 2-pointer approach, as follows:

• Start at L = 1 and R = 1.
• Maintain a set S of the currently active restrictions.
• Then, repeat the following process:
• While [L, R+1] has no conflicts, increase R by 1.
• This is done by checking if the opposite restriction of B_R is currently in S or not.
• If R is increased, add B_R to S.
• Now we have the optimal R for this L. Set ans = \max(ans, R-L+1).
• Now, increase L by 1 but don’t change R. This is done by simply removing B_L from S.

S can be easily maintained using std::multiset or a similar data structure; it’s even possible to just use an array since the restrictions themselves are of small values.

# TIME COMPLEXITY

\mathcal{O}(N\log N) per test case.

# CODE:

Setter's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define sp << ' ' <<
#define nl << '\n'

signed main() {
cin.tie(0)->sync_with_stdio(0);

int T; cin >> T;
while(T--) {
int N; cin >> N;

int A[N];
for(int &i : A) cin >> i;

for(int i = N; --i; )
A[i] = (A[i] < A[i-1] ? -1 : 1) * (64 - __builtin_clzll(A[i] ^ A[i-1]));

int ans = 1, _cnt[61] {}, *cnt = _cnt + 30, j = 1;

for(int i = 1; i < N; --cnt[A[i++]]) {
for(; j < N && !cnt[-A[j]]; ++cnt[A[j++]]);

ans = max(ans, j - i + 1);
}

cout << ans nl;
}
}

Tester'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;
#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;}
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=1e9+7;
const ll MAX=1000100;
void solve(){
ll n; cin>>n;
vector<ll> a(n+5,0);
ll ans=1;
for(ll i=1;i<=n;i++){
cin>>a[i];
}
vector<vector<ll>> dp(30,vector<ll>(2,0));
for(ll i=2;i<=n;i++){
for(ll j=29;j>=0;j--){
ll l=min(1LL,a[i-1]&(1<<j));
ll r=min(1LL,a[i]&(1<<j));
if(l==r){
continue;
}
dp[j][r]=i-1;
break;
}
ll till=0;
for(ll j=0;j<30;j++){
till=max(till,min(dp[j][0],dp[j][1]));
}
ans=max(ans,i-till);
}
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 (C++)
#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 &x : a) cin >> x;
vector<int> changes;
for (int i = 0; i+1 < n; ++i) {
int k = a[i] ^ a[i+1];
for (int b = 30; b >= 0; --b) {
if (k & (1 << b)) {
if (a[i] < a[i+1]) changes.push_back(-b-1);
else changes.push_back(b+1);
break;
}
}
}

int mxlen = 1, R = -1;
multiset<int> active;
for (int L = 0; L+1 < n; ++L) {
while (R+2 < n and active.find(-changes[R+1]) == active.end()) {
++R;
active.insert(changes[R]);
}
mxlen = max(mxlen, R-L+2);
active.erase(active.find(changes[L]));
}
cout << mxlen << '\n';
}
}


Good problem.The key point is:if you choose both A_i and A_{i+1},then one bit of X will be determined.

My method is to fix L=1,2,...,n-1, do binary serarch for R, and judge whether there is bit conflict of X in the interval [L, R].

This method is also valid when the same A_i exists,I don’t know why A_i must be distinct.

TL seems a bit tight.I guess my O(n log^2n) method costs about 1.5-3 s

O(n log^2n)code

Did code chef problem difficulty scale changed ? like [0-2000] to [0-4000] or is it because of number of people participating are less, in code chef these days ? There seems to be something off about problem difficulty rating. I think problem difficulty rating should not exceed 6* max level.