 # Editorial-Binary Search || ECPC10E

Author and Editorialist: Pankaj Sharma

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;
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 1 Like

here we applying binary search on K not on G(K),
so high = 1e7 instead n * (n + 1) / 2.

1
2 3
10 5
1 3

for this example actual output is 9 and editorial solutions output -1.
we can easily see that,
F(0, 0) = 9 <= 9
F(0, 1) = 9 <= 9
F(1, 1) = 2 <= 9
G(9) = 3

maybe test cases are weak.

1 Like

Yes you are correct high = 1e7 or max(A_1,..., A_N) - min(B_1,...B_N) as we are applying binary search on k.
I have fixed that in editorial.