Solusi Paling Efisien untuk USACO: Segitiga - Python

Oct 05 2020

Saya mencoba menyelesaikan masalah ini dengan Python 3.8. Dalam kode saya, saya menggunakan 3 bersarang untuk loop untuk memeriksa setiap titik dan menyimpan area terbesar dengan setiap kumpulan titik. Program ini berfungsi dengan baik, tetapi \$ O(n^3) \$kompleksitas waktu, dan saya bertanya-tanya apakah ada solusi yang lebih elegan / efisien. Apakah ada algoritme yang lebih efisien yang tidak mengulang setiap titik, atau apakah itu perlu?

Kode saya:

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

File masukan triangles.in:

Sinopsis masalah: Diberikan satu set \$ n \$poin yang berbeda \$ (X_1, Y_1) \$ke \$ (X_n, Y_n) \$, cari luas segitiga terbesar dikalikan 2, mengingat segitiga tersebut adalah segitiga siku-siku (salah satu garis segitiga sejajar dengan sumbu x, dan satu lagi sejajar dengan sumbu y).

Jawaban

5 superbrain Oct 05 2020 at 18:43

Perbaikan yang jelas adalah tidak membagi string dan mengubah bagian-bagiannya menjadi int berulang kali . Lakukan sekali, di awal:

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)

Dan itu bisa diselesaikan dalam O (n). Untuk setiap "sudut" seperti yang Anda sebut, Anda melewati semua pasangan poin. Sebagai gantinya, lihat saja titik terjauh pada koordinat y yang sama dan titik terjauh pada koordinat x yang sama. Itu dapat dihitung sebelumnya dalam 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)

Perhatikan bahwa saya juga melakukan output sedikit berbeda. Tidak perlu untuk closedirimu sendiri. Mendapatkan file tersebut untuk Anda agak adalah alasan Anda menggunakan withdi tempat pertama, ingat? Dan saya lebih memilih printlebih write, karena saya tidak harus mengkonversi string kemudian dan akhir baris kepercayaan harus dilakukan sesuai untuk platform (mungkin tidak menjadi masalah di sini, sebagai output hanya satu baris dan tampaknya mereka tidak peduli bagaimana Ini berakhir).

PS Mereka sialan ... mereka terus mengatakan solusi saya gagal karena "Runtime error atau batas memori terlampaui" dan saya butuh beberapa saat untuk mencari tahu: Alih-alih tuple(map(...))saya telah menggunakan pilihan saya [*map(...)]. Tapi mereka secara misterius menggunakan Python 3.4 dan saat itu tidak ada. Tapi itu seharusnya kesalahan sintaks . Grrrr ....

3 SylvainD Oct 05 2020 at 20:37

Ini akan sangat mirip dengan jawaban bagus hujan lebat.

Tulis fungsi

Fungsi penulisan akan membantu Anda menulis kode lebih mudah. Juga, untuk tantangan algoritmik, ini akan membantu Anda untuk fokus pada algoritme itu sendiri daripada berurusan dengan input / output.

Tulis tes

Setelah Anda memiliki suatu fungsi, akan lebih mudah untuk menulis pengujian. (Anda juga bisa menulis tes sebelum fungsi). Ini akan membantu untuk menguji berbagai implementasi, mengujinya, membandingkannya (baik dalam kebenaran maupun dalam kinerja)

Saran pengoptimalan

Hitung sesedikit mungkin, hentikan secepat mungkin.

Di sini, itu bisa berarti memeriksa lx == cxsecepat Anda bisa dan menghitung abs(ly-cy)hanya sekali per tupel (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

Lakukan prakomputasi sebanyak mungkin

Alih-alih harus mengulangi semua titik untuk menemukan titik-titik pada garis atau kolom yang sama dengan titik yang sedang dipertimbangkan, kita dapat melakukan beberapa prakomputasi untuk dapat dengan cepat menemukan semua titik dalam garis (atau kolom) yang sama dengan titik saat ini.

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

Hitung sesedikit mungkin (lagi)

Untuk titik tertentu, kita tidak harus mempertimbangkan semua titik lain di baris yang sama dan semua titik lain di kolom yang sama. Kita bisa menganggap yang terjauh secara vertikal atau horizontal.