Problem Link:
Author: Shivam Jindal
Difficulty:
Medium
Prerequisites:
Binary Search, Fenwick Tree or Segment Tree, Inversion Count
Problem:
Given array of integers of island sizes (s_i) and corresponding island co-ordinates (X_i), find minimal value of d such that the total sum of difference of coordinates in each pair of islands i, j where i < j and s_i - s_j >= d is within the given budget value B.
Explanation:
We first observe that if the sum of coordinate differences for some value of d is ok (within budget B) then we can claim that value d+1 is also ok. But we can’t be sure of d-1. Reason behind this observation is:
as value of d increases corresponding sum can only decrease or remain same.
Hence we can binary search the value of d. How to check for any value of d whether this satisfies B…
Just like we do in problem INVCNT we calculate by traversing from right and for each i we query in BIT. For any index i we have to find \sum_{j} (X_j - X_i), if s_j <= s_i-d for all such j, i < j <= n
\sum_{j} (X_j - X_i) = \sum_{j} X_j - cnt*X_i, where cnt is the number of such indices j where s_j <= s_i-d holds.
Hence we maintain two BIT, one for calculating cnt at each index i and another for calculating \sum_{j} X_j.
Just like inversion count, we then update the X_i at index s_i in BIT.