Binary Search the Answer - Sparsely Planting Trees
nspots where you can plant a tree, you’d like to plant them as sparsely as possible to make sure they don’t disrupt each other in several years. The coordinates of the spots are given as integers
Your task is to find the minimum distance between
ttrees if you plant them as sparsely as possible.
The first line of the input contains two integers
n(1 ≤ n ≤ 100 000) the number of spots and
t(2 ≤ t ≤ n) the number of trees that need to be planted.
The next line contains
nspace-separated distinct integers
(0 ≤ ≤ ) the coordinates of spots where a tree can be planted.
The program should print the minimum distance
dbetween trees when planted as sparsely as possible.
5 3 1 2 8 4 9
We can plant the trees as coordinates 1, 4, and 9 ⇒ the minimum distance is 4-1 = 3.
We can solve this challenge by performing a binary search on the answer (the minimum distance between trees) and checking on each iteration if it would be possible to plan trees with a given minimum distance. There are several important conditions that need to hold in order for the binary search on the answer to be possible:
- We should be able to check if the given candidate answer satisfies the problem statement or not (in our case - we should be able to check for a given minimum distance
dif we can plant the trees so that they are at least
- The checking function
def check(x):should return
Trueif it’s possible to satisfy the problem statement with a candidate answer
- For increasing candidate answers (different values of
x), the value of the checking function should be :
False False False True True(impossible for the first several numbers and then possible for larger ones). In this case, we’re looking for the first
True(the smallest valid value).
True True True True False False(possible for small numbers and impossible for larger ones). In this case, we’re looking for the last
True(the largest valid value).
In our case, we would like to plant the trees as sparsely as possible. So, we would like the minimum distance to be as large as possible. If it’s possible to plant trees with a minimum distance of
x, then it’s definitely possible to plan them denser and get a smaller
x. Therefore, in our case, the values of the checking function will be
True True True True False Falseand we aim to find the last
Truein this list (the largest (most sparse) minimal distance between the planted trees).
A naive approach to solving this problem would be to sequentially iterate over the candidate answers
d- 1, 2, 3, etc., and check if we can plant the trees with distances of at least
Try to implement this approach first before moving forward.
With a binary search on the answer, there are 2 components - the checking part, and the binary search part:
n, t = ... x = sorted(x) def check(d): """ Check if we can plant `t` trees at least `d` units apart """ planted = 0 # We need to plant t trees (currently planted 0) prev = float('-inf') # The coordinate of the previous tree for xi in x: if xi - prev >= d: # If we can plant another tree at xi planted += 1 prev = xi return planted >= t
With the checking function implemented, we can perform a binary search on the answer to find the most optimal value for the minimum distance if we would like to plant the trees as sparsely as possible:
l, r = 1, max(x) # The answer is always in the range [l; r) while r - l > 1: # There is at least one element in between to consider mid = (l + r) // 2 # Take the middle index if check(mid): # If it's possible with mid => l = mid l = mid else: # Otherwise set r = mid r = mid print(l)
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB