Algoritmos e Estruturas de Dados

Binary Search the Answer - Sparsely Planting Trees

Dado n locais onde é possível plantar uma árvore, pretende-se distribui-las de forma a que fiquem o mais espaçadas possível, para que não interfiram umas com as outras ao longo dos anos. As coordenadas desses locais são fornecidas como inteiros .
O seu objetivo é determinar a distância mínima entre t árvores se as plantar de forma a maximizar o espaçamento entre elas.

Entrada

A primeira linha da entrada contém dois inteiros n (1 ≤ n ≤ 100 000), que é o número de locais, e t (2 ≤ t ≤ n), que é o número de árvores que precisam de ser plantadas.
A linha seguinte contém n inteiros distintos , separados por espaço, (0 ≤ ≤ ), que são as coordenadas dos locais onde se pode plantar uma árvore.

Saída

O programa deve imprimir a distância mínima d entre as árvores quando plantadas de forma a maximizar o espaçamento entre elas.

Exemplos

Entrada
Saída
5 3 1 2 8 4 9
3

Explicação

Podemos plantar as árvores nas coordenadas 1, 4 e 9 ⇒ a distância mínima é 4-1 = 3.
 

Tutorial

Podemos resolver este desafio realizando uma pesquisa binária (binary search) na resposta (ou seja, na distância mínima entre as árvores) e verificando em cada iteração se é possível plantar as árvores com uma determinada distância mínima. Existem várias condições importantes para que a pesquisa binária sobre a resposta seja viável:
  • Devemos conseguir verificar se a resposta candidata cumpre o enunciado do problema ou não (no nosso caso, precisamos de verificar, para uma dada distância mínima d, se conseguimos plantar as árvores de modo a manter pelo menos d unidades de distância entre elas).
  • A função de verificação def check(x): deve retornar True se for possível satisfazer o enunciado do problema com a resposta candidata x e False caso contrário.
  • Para valores crescentes das respostas candidatas (diferentes valores de x), o resultado da função de verificação deve ser:
    • 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).
 
- False False False True True (impossível para os primeiros valores e depois possível para valores maiores). Nesse caso, procura-se o primeiro True (o menor valor válido).
- True True True True False False (possível para valores pequenos e impossível para valores maiores). Nesse caso, procura-se o último True (o maior valor válido).
 
No nosso caso, queremos plantar as árvores de forma a que fiquem o mais espaçadas possível. Portanto, queremos que a distância mínima seja a maior possível. Se for possível plantar as árvores com uma distância mínima de x, é certamente possível plantá-las com uma distância menor que x. Logo, neste cenário, os valores da função de verificação vão seguir o padrão True True True True False False, e pretendemos encontrar o último True (ou seja, a maior distância mínima possível entre as árvores).
n, t = ...
x = sorted(x)

def check(d):
    """Verifica se conseguimos plantar t árvores, mantendo pelo menos d unidades de distância entre elas."""
    planted = 0               # Precisamos plantar t árvores (atualmente plantámos 0)
    prev = float('-inf')      # Coordenada da árvore anterior
    for xi in x:
        if xi - prev >= d:    # Se pudermos plantar outra árvore em xi
            planted += 1
            prev = xi
    return planted >= t
Depois de implementada a função de verificação, executamos a pesquisa binária para encontrar o valor ideal (ou seja, o maior valor possível para a distância mínima) caso queiramos plantar as árvores de forma mais espaçada:
l, r = 1, max(x)         # A resposta estará sempre no intervalo [l; r)
while r - l > 1:         # Ainda existe pelo menos um valor a considerar entre l e r
    mid = (l + r) // 2   # Obtemos o índice intermédio
    if check(mid):       # Se for possível com mid => l = mid
        l = mid
    else:                # Caso contrário, r = mid
        r = mid

print(l)
 

Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 1 MB

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