Solução mais eficiente para USACO: Triângulos - Python

Oct 05 2020

Estou tentando resolver esse problema com Python 3.8. Em meu código, usei 3 loops for aninhados para verificar cada ponto e armazenar a maior área com cada conjunto de pontos. Este programa funciona bem, mas é \$ O(n^3) \$complexidade de tempo, e estou me perguntando se existem soluções mais elegantes / eficientes. Existe um algoritmo mais eficiente que não percorre todos os pontos ou isso é necessário?

Meu código:

with open("triangles.in", "r") as file_in:
  lines = [x.strip() for x in file_in.readlines()]
  n, points = lines[0], lines[1:]


def main(points):
  largest = 0

  for corner in points:
    cx, cy = corner.split()
    for leg in points:
      lx, ly = leg.split()
      for width in points:
        wx, wy = width.split()
        if lx == cx and wy == cy:
          area = abs(int(ly)-int(cy)) * abs(int(wx)-int(cx))
          
          if area > largest:
            largest = area

  return str(largest)

with open("triangles.out", "w+") as file_out:
  file_out.write(main(points))
  file_out.close()

O arquivo de entrada triangles.in:

Sinopse do problema: Dado um conjunto de \$ n \$pontos distintos \$ (X_1, Y_1) \$para \$ (X_n, Y_n) \$, encontre a maior área do triângulo multiplicada por 2, dado que o triângulo é um triângulo retângulo (uma das linhas do triângulo paralela ao eixo xe outra paralela ao eixo y).

Respostas

5 superbrain Oct 05 2020 at 18:43

Uma melhoria óbvia é não dividir as cordas e converter as partes int repetidamente . Faça uma vez, no início:

def main(points):
  points = [tuple(map(int, point.split())) for point in points]
  largest = 0

  for cx, cy in points:
    for lx, ly in points:
      for wx, wy in points:
        if lx == cx and wy == cy:
          area = abs(ly-cy) * abs(wx-cx)
          if area > largest:
            largest = area

  return str(largest)

E isso pode ser resolvido em O (n). Para cada "canto" como você o chama, você passa por todos os pares de pontos. Em vez disso, apenas procure o ponto mais distante na mesma coordenada y e o ponto mais distante na mesma coordenada x. Isso pode ser pré-calculado em O (n):

with open('triangles.in') as f:
    next(f)
    points = [tuple(map(int, line.split())) for line in f]

xmin, xmax, ymin, ymax = {}, {}, {}, {}
for x, y in points:
    xmin[y] = min(xmin.get(y, x), x)
    xmax[y] = max(xmax.get(y, x), x)
    ymin[x] = min(ymin.get(x, y), y)
    ymax[x] = max(ymax.get(x, y), y)

result = max(max(x - xmin[y], xmax[y] - x) * max(y - ymin[x], ymax[x] - y)
             for x, y in points)

with open('triangles.out', 'w') as f:
    print(result, file=f)

Observe que também fiz a saída de maneira um pouco diferente. Não há necessidade de closevocê. Fechar o arquivo para você é a razão pela qual você usou withem primeiro lugar, lembra? E eu prefiro printmais write, como eu não tem que converter a corda então e finais de linha de confiança para ser feito o mais apropriado para a plataforma (talvez não um problema aqui, como a saída é apenas uma linha e, aparentemente, eles não se importam quão termina).

PS Esses malditos ... eles ficavam dizendo que minha solução falhou devido a "Erro de tempo de execução ou limite de memória excedido" e demorei um pouco para descobrir: em vez de tuple(map(...))usar o meu preferido [*map(...)]. Mas eles estão inexplicavelmente usando Python 3.4 e ele não existia naquela época. Mas isso deve ser um erro de sintaxe . Grrrr ....

3 SylvainD Oct 05 2020 at 20:37

Isso será muito semelhante à grande resposta da chuva soberba.

Funções de escrita

As funções de escrita o ajudarão a escrever um código mais fácil de manter. Além disso, para os desafios do algoritmo, isso o ajudará a se concentrar no próprio algoritmo em vez de lidar com a entrada / saída.

Escreva testes

Depois de ter uma função, é mais fácil escrever testes. (Você também pode escrever os testes antes da função). Isso ajudará a testar várias implementações, para testá-las, para compará-las (tanto na correção quanto no desempenho)

Conselhos de otimização

Calcule o mínimo possível, pare o mais rápido possível.

Aqui, isso pode significar verificar o lx == cxmais rápido possível e calcular abs(ly-cy)apenas uma vez por tupla (ly, cy).

def get_solution_naive_on_smaller_range(points):
    largest = 0
    for cx, cy in points:
        for lx, ly in points:
            if lx == cx:
                dy = abs(ly-cy)
                for wx, wy in points:
                    if wy == cy:
                        dx = abs(wx-cx)
                        area = dy * dx
                        if area > largest:
                            largest = area
    return largest

Pré-calcule o máximo possível

Em vez de ter que iterar por todos os pontos para encontrar os pontos na mesma linha ou colunas que o ponto que está sendo considerado, poderíamos realizar alguma pré-computação para ser capaz de encontrar rapidamente todos os pontos na mesma linha (ou coluna) que o ponto atual.

def get_solution_using_dicts(points):
    largest = 0
    by_x = dict()
    by_y = dict()
    for x, y in points:
        by_x.setdefault(x, []).append(y)
        by_y.setdefault(y, []).append(x)
    for cx, cy in points:
        for ly in by_x[cx]:
            dy = abs(ly-cy)
            for wx in by_y[cy]:
                dx = abs(wx - cx)
                area = dy * dx
                if area > largest:
                    largest = area
    return largest

Calcule o mínimo possível (novamente)

Para um determinado ponto, não temos que considerar todos os outros pontos na mesma linha e todos os outros pontos na mesma coluna. Podemos apenas considerar aquele que está mais afastado verticalmente ou horizontalmente.