Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation

  • Binary Search the Answer - Sparsely Planting Trees

    Given n spots 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 t trees if you plant them as sparsely as possible.

    Input

    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 n space-separated distinct integers (0 ≤ ) the coordinates of spots where a tree can be planted.

    Output

    The program should print the minimum distance d between trees when planted as sparsely as possible.

    Examples

    Input
    Output
    5 3 1 2 8 4 9
    3

    Explanation

    We can plant the trees as coordinates 1, 4, and 9 ⇒ the minimum distance is 4-1 = 3.
     

    Tutorial

    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 d if we can plant the trees so that they are at least d units apart).
    • The checking function def check(x): should return True if it’s possible to satisfy the problem statement with a candidate answer x and False otherwise.
    • 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 False and we aim to find the last True in 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 d.
    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)
     

    Constraints

    Time limit: 2 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue