XORARRAY - Editorial


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

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




Binary search or 2-pointers


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?


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.


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


Setter's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define sp << ' ' <<
#define nl << '\n'
signed main() {
	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;
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;
#define debug(x);  
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=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++){
    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));
        ll till=0; 
        for(ll j=0;j<30;j++){
int main()                                                                           
    #ifndef ONLINE_JUDGE                 
    freopen("input.txt", "r", stdin);                                              
    freopen("output.txt", "w", stdout);  
    freopen("error.txt", "w", stderr);                        
    ll test_cases=1;               
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);

		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()) {
			mxlen = max(mxlen, R-L+2);
		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 :smiling_face_with_tear:

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.