La soluzione più efficiente per USACO: Triangles - Python

Oct 05 2020

Sto cercando di risolvere questo problema con Python 3.8. Nel mio codice, ho usato 3 cicli for nidificati per controllare ogni singolo punto e memorizzare l'area più grande con ogni set di punti. Questo programma funziona bene, ma \$ O(n^3) \$complessità temporale, e mi chiedo se ci siano soluzioni più eleganti / efficienti. Esiste un algoritmo più efficiente che non passa in rassegna ogni singolo punto o è necessario?

Il mio codice:

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()

Il file di input triangles.in:

Sinossi del problema: dato un insieme di \$ n \$punti distinti \$ (X_1, Y_1) \$a \$ (X_n, Y_n) \$, trova l'area del triangolo più grande moltiplicata per 2, dato che il triangolo è un triangolo rettangolo (una delle linee del triangolo parallela all'asse xe un'altra parallela all'asse y).

Risposte

5 superbrain Oct 05 2020 at 18:43

Un ovvio miglioramento consiste nel non dividere le corde e convertire le parti int più e più volte . Fallo una volta, all'inizio:

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 può essere risolto in O (n). Per ogni "angolo" come lo chiami, passi attraverso tutte le coppie di punti. Invece, cerca semplicemente il punto più lontano sulla stessa coordinata y e il punto più lontano sulla stessa coordinata x. Che può essere precalcolato in 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)

Nota che ho anche eseguito l'output in modo leggermente diverso. Non c'è bisogno di closete stesso. Ottenere il file chiuso per te è il motivo per cui l'hai usato within primo luogo, ricordi? E io preferisco printsopra write, come io non devo convertire in stringa e poi fine riga di fiducia di essere fatto come appropriato per la piattaforma (forse non è un problema qui, come l'uscita è solo una riga e apparentemente loro non importa come finisce).

PS Quei maledetti ... continuavano a dire che la mia soluzione non era riuscita a causa di "Errore di runtime o limite di memoria superato" e mi ci è voluto un po 'per capire: invece di tuple(map(...))aver usato il mio preferito [*map(...)]. Ma inspiegabilmente usano Python 3.4 e allora non esisteva. Ma dovrebbe essere un errore di sintassi . Grrrr ....

3 SylvainD Oct 05 2020 at 20:37

Questo sarà abbastanza simile alla grande risposta della pioggia superba.

Scrivi funzioni

Le funzioni di scrittura ti aiuteranno a scrivere codice più facile da mantenere. Inoltre, per le sfide algoritmiche, ti aiuterà a concentrarti sull'algoritmo stesso invece di occuparti di input / output.

Scrivi test

Una volta che hai una funzione, è più facile scrivere test. (Puoi anche scrivere i test prima della funzione). Ciò aiuterà a testare varie implementazioni, a testarle, a confrontarle (sia nella correttezza che nelle prestazioni)

Consigli di ottimizzazione

Calcola il meno possibile, fermati il prima possibile.

In questo caso, ciò potrebbe significare controllare lx == cxil prima possibile e calcolare abs(ly-cy)solo una volta per 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

Precalcola il più possibile

Invece di dover iterare su tutti i punti per trovare i punti sulla stessa riga o colonne del punto considerato, potremmo eseguire alcuni precalcoli per poter trovare rapidamente tutti i punti nella stessa riga (o colonna) del punto corrente.

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

Calcola il meno possibile (di nuovo)

Per un dato punto, non dobbiamo considerare tutti gli altri punti nella stessa linea e tutti gli altri punti nella stessa colonna. Possiamo solo considerare quello più lontano in verticale o in orizzontale.