### I_love_penny's blog

By I_love_penny, history, 3 years ago,

How to solve this problem using binary search.
Problem Statement :
You are given an array A of N integers in nondecreasing order. Remove K integers such that the maximum difference between two consecutive elements is minimized.
solution using binary search (I am not getting its intuition). ​​

• +5

 » 3 years ago, # |   0 Auto comment: topic has been updated by codenote (previous revision, new revision, compare).
 » 3 years ago, # |   0 Binary search for the maximum difference, to find the minimum maximum difference we can achieve. If you won't allow differences bigger than mid, then you need to "cut" your array removing all differences from the left and right until you clear everything bigger than mid. That leaves, at best, a contiguous segment. So he's just looping to find the biggest contiguous segment that doesn't have any difference greater than mid.
•  » » 3 years ago, # ^ |   0 How we are ensuring that exactly k elements are removed from array.
•  » » 3 years ago, # ^ |   0 Okay I got it , if we can get subarray by removing <=k elements than we can get subarray by removing k elements also. Thanks :)
 » 3 years ago, # |   0 You binary search on the answer. For checking a particular value x, you find the longest subarray of length L that has adjacent difference less than x. So you remove (n-L) elements. If this is less than K, you can decrease hi, otherwise you need to go in the right part ie increase lo.
•  » » 3 years ago, # ^ |   0 But we need to remove exactly k elements.
•  » » 3 years ago, # ^ |   +3 Okay I got it , if we can get subarray by removing <=k elements than we can get subarray by removing k elements also. Thanks :)
 » 3 years ago, # |   +6 You can solve this without binary search too. You should remove k integers either from starting or ending because removing elements from the middle of the array only increases the consecutive difference and It doesn't make sense. We start by building segment tree on the consecutive differences. and then we iterate the array from left to right, at every index i we assume that we have removed i elements from starting and now, we need to remove k — i elements from the end. We now query for the maximum difference in this remaining segment and the final answer would be the minimum of these queries. Code#include using namespace std; typedef long long ll; #define eps 1e-9 #define all(a) a.begin(),a.end() #define mp make_pair #define F first #define S second #define pb push_back #define sz size() #define rd(inp) scanf("%lld",&inp) #define rd2(inp1, inp2) scanf("%lld %lld",&inp1, &inp2) #define rl(inp) scanf("%d",&inp) #define pf(out) printf("%lld\n", out); const long long linf = 1e18+5; const int mod = (int) 1e9 + 7; const int inf = 1e9; #define maxn 100100 ll a[maxn], nn, tree[maxn * 8]; vector d; void build(ll node, ll start, ll end){ if(start == end){ tree[node] = d[start]; } else{ ll mid = (start + end) / 2; build( 2* node + 1 , start, mid); build( 2* node + 2, mid + 1, end); tree[node] = max(tree[node*2 + 1], tree[node*2+2]); } } ll query(ll node, ll start, ll end, ll l, ll r){ if(r < start || end < l){ return 0; } if(l <= start && end <=r){ return tree[node]; } ll mid = (start + end) / 2; ll p1 = query(2 * node + 1, start, mid, l, r); ll p2 = query(2 * node + 2, mid + 1, end, l, r); return max(p1, p2); } int main(){ ll n, i, m = 0, k; cin >> n >> k; for ( i = 0 ; i < n ; i ++ ){ cin >> a[i]; } for ( i = 1 ; i < n ; i ++ ){ d.pb(abs(a[i] - a[i - 1])); m = max(m, abs(a[i] - a[i - 1])); } nn = n - 1; build(0, 0, nn - 1); ll ans = m; for ( i = 0 ; i <= k && i < n ; i ++ ){ ll rem = k - i; if ( rem + i == k ){ ll rg = n - 1 - rem; ans = min(ans, query(0, 0, nn - 1, i, rg - 1)); } } cout << ans << endl; return 0; } 
•  » » 3 years ago, # ^ |   0 You can solve this without using a segment tree. Simply retain the differences in a set. Code#include #define for1(i, n) for(int i = 1; i <= n; i++) #define mp make_pair #define FASTIO ios_base::sync_with_stdio(0) using namespace std; const int NMAX = 1e5 + 5; set > heap; int n, k; int v[NMAX]; int sol = INFINT; int main() { FASTIO; cin >> n >> k; for1(i, n) cin >> v[i]; for1(i, n - k - 1) heap.insert(mp(max(v[i + 1] - v[i], v[i] - v[i + 1]), i)); sol = (*heap.rbegin()).first; for(int i = n - k, er = 1; i <= n - 1; i++, er++) { pair temp; temp.first = max(v[er + 1] - v[er], v[er] - v[er + 1]); temp.second = er; heap.erase(temp); heap.insert(mp(max(v[i + 1] - v[i], v[i] - v[i + 1]), i)); sol = min(sol, (*heap.rbegin()).first); } cout << sol; return 0; } 
•  » » » 5 weeks ago, # ^ |   0 How do we solve this if first and last elements are fixed?
•  » » 5 months ago, # ^ |   0 How to make changew to your code, if the first and the last elements are fixed ?
•  » » » 5 months ago, # ^ |   0 How many problems did you solved? I only solved the one with 20 points
•  » » » 3 months ago, # ^ |   0 Where did you get the problem in which the first and last elements are fixed? I would like to solve it.
 » 12 months ago, # |   0 what if the first and last element is fixed
•  » » 12 days ago, # ^ |   0 did you get the solution?