GO3-Editorial

Problem Link:

Practice

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.

Author’s solution

Code.

//