PROBLEM LINK:
Author and Editorialist: Pankaj Sharma
DIFFICULTY:
MEDIUM .
PREREQUISITES:
Binary Search , Two- pointers , sliding window
PROBLEM:
You have given two array of integers A and B.
F(L,R) = max(A_L,A_{L+1},... , A_R) - min(B_L,B_{L+1}, ... B_R)
G(k) = Total count of (L,R) such that F(L,R) <= k
Find min k such that G(k) = U
QUICK EXPLANATION:
Check
Calculate F(L,R) using sliding window + Two pointers.
For each r calculate leftmost valid l then calculate G(k) in O(N)
Then Apply binary on k
EXPLANATION:
Observation 1
If F(L,R) <=k then F(L+1,R) <=k ,…F(R,R)<=k because B_i \eq A_i and If we are at index R and move to left side then difference increases as we are taking max from A and min from B
Observation 2
G(k) is monotonic on k i.e G(k) increases as k increases.
Observation 3
min value of G(k) = 0 when none of (L,R) are valid
Max value of G(k) = n*(n+1)/2 when all (L,R) are valid
How to approach
Using obervation 1 we can calculate F(L,R) in O(N)
How ?
Maintain two windows one is max(A[L…R]) and other is min(A[L…R)
This technique is known as Sliding Window
We will use two deque one for A and other for B for maintaining window.
Then for each R we will calculate leftmost valid L. This can be done by maintaining two pointers L and R.
max(A[L…R]) - min(A[L…R) >k then we will increment L by 1 as all L less that current L will also give F(L,R) i.e max(A[L…R]) - min(A[L…R) >k .
So We can calculate G(k) in O(N).
Then Using observation 2 and 3 we will apply binary on k from 0 to 1e9 to find first smallest k which will give G(k) = U.
You can learn it from Find first position of an element in a sorted array
Time Complexity:
The time complexity is O(N*log(1e9)) per test case.
where N=total number of elements in array .
SOLUTIONS:
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll max(ll a, ll b) {return (a > b ? a : b);}
ll min(ll a, ll b) {return (a < b ? a : b);}
ll n, U;
vector<ll> a, b;
ll G(ll k) {
ll l = 1;
ll ans = 0, r;
deque<ll> max_A, min_B;
for ( r = 1; r <= n; r++) {
// Maintaining minimum in B
while ((!min_B.empty()) and b[min_B.back()] >= b[r])
min_B.pop_back();
// Maintaining max in A
while ((!max_A.empty()) and a[max_A.back()] <= a[r])
max_A.pop_back();
max_A.push_back(r);
min_B.push_back(r);
// Check if current window (l,r) have F(L,R)<=k or not
while ( a[max_A.front()] - b[min_B.front()] > k) {
l++;
if (min_B.front() < l)
min_B.pop_front();
if (max_A.front() < l)
max_A.pop_front();
if (l > n) {
break;
}
if ((max_A.empty()) or (min_B.empty())) break;
}
if (l > r) continue;
// Add all pair (l,r) to the answer
ans += (r - l + 1);
}
return ans;
}
void test_case() {
ll ans = -1;
ll l, r;
cin >> n >> U;
a = b = vector<ll>(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
cin >> b[i];
ll mid, low = 0, high = 1e9 ;
// Binary search
while (low <= high) {
mid = (low + high) / 2;
ll now = G(mid);
if (now == U) {
ans = mid;
high = mid - 1;
}
else if (now > U) high = mid - 1;
else low = mid + 1;
}
cout << ans << "\n";
}
int main()
{
cin.sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
test_case();
return 0;
}
Please give me suggestions if anything is unclear so that I can improve. Thanks 