XORARRAY - Editorial

PROBLEM LINK:

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

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

DIFFICULTY:

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?

Answer

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;
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=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 :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.

:joy:

image

image