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.
- While [L, R+1] has no conflicts, increase R by 1.
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';
}
}
