USACO için En Verimli Çözüm: Üçgenler - Python

Oct 05 2020

Bu sorunu Python 3.8 ile çözmeye çalışıyorum . Kodumda, her noktayı kontrol etmek ve her nokta kümesiyle en büyük alanı depolamak için iç içe geçmiş 3 döngü kullandım. Bu program iyi çalışıyor, ancak \$ O(n^3) \$zaman karmaşıklığı ve daha zarif / verimli çözümler olup olmadığını merak ediyorum. Her noktadan geçmeyen daha verimli bir algoritma var mı yoksa bu gerekli mi?

Kodum:

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

Girdi dosyası triangles.in:

Problem özeti: Bir dizi \ verildiğinde$ n \$farklı noktalar \$ (X_1, Y_1) \$için \$ (X_n, Y_n) \$, üçgenin bir dik üçgen (üçgenin çizgilerinden biri x eksenine paralel, diğeri y eksenine paralel) olması koşuluyla, en büyük üçgenin alanını 2 ile çarparak bulun.

Yanıtlar

5 superbrain Oct 05 2020 at 18:43

Açık bir gelişme, dizeleri bölmemek ve parçaları int tekrar tekrar dönüştürmemek . Başlangıçta bir kez yapın:

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)

Ve O (n) ile çözülebilir. Dediğiniz her "köşe" için, tüm nokta çiftlerinden geçersiniz. Bunun yerine, aynı y koordinatında en uzak noktaya ve aynı x koordinatında en uzak noktaya bakın. Bu, O (n) cinsinden önceden hesaplanabilir:

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)

Çıkışı biraz farklı yaptığımı da unutmayın. closeKendinize gerek yok . Dosyayı senin için kapatman withilk etapta kullanmanın sebebi , hatırladın mı? Ve tercih printüzerinde writeben çıkış sadece bir çizgidir olarak, belki değil bir sorun burada (platformu için uygun olarak yapılması gereken ve görünüşe göre nasıl umurumda değil sonra dize ve güven satır sonları dönüştürmek gerekmez olarak, biter).

PS Bu lanet olası ... "Çalışma zamanı hatası veya bellek sınırı aşıldı" nedeniyle çözümümün başarısız olduğunu söylediler ve anlamam biraz zaman aldı: Bunun yerine tuple(map(...))tercih ettiğimi kullandım [*map(...)]. Ancak anlaşılmaz bir şekilde Python 3.4 kullanıyorlar ve o zamanlar mevcut değildi. Ancak bu bir sözdizimi hatası olmalıdır . Grrrr ...

3 SylvainD Oct 05 2020 at 20:37

Bu, süper yağmurun harika cevabına oldukça benzeyecek.

Yazma işlevleri

Yazma işlevleri, kodu korumak için daha kolay yazmanıza yardımcı olacaktır. Ayrıca, algoritmik zorluklar için, girdi / çıktıyla uğraşmak yerine algoritmanın kendisine odaklanmanıza yardımcı olacaktır.

Testleri yazın

Bir işleve sahip olduğunuzda, testler yazmak daha kolaydır. (Testleri fonksiyondan önce de yazabilirsiniz). Bu, çeşitli uygulamaları test etmeye, test etmeye, karşılaştırmaya (hem doğruluk hem de performans açısından) yardımcı olacaktır.

Optimizasyon önerileri

Mümkün olduğunca az hesaplayın, mümkün olan en kısa sürede durdurun.

Burada bu, lx == cxolabildiğince çabuk kontrol etmek ve abs(ly-cy)her tuple için yalnızca bir kez hesaplama yapmak anlamına gelebilir (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

Mümkün olduğunca ön hesaplama yapın

Dikkate alınan noktanın aynı çizgi veya sütunlardaki noktaları bulmak için tüm noktaları yinelemek zorunda kalmadan, geçerli noktanın aynı çizgideki (veya sütundaki) tüm noktaları hızlı bir şekilde bulabilmek için bazı ön hesaplamalar yapabiliriz.

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

Mümkün olduğunca az hesaplayın (tekrar)

Belirli bir nokta için, aynı çizgideki diğer tüm noktaları ve aynı sütundaki diğer tüm noktaları dikkate almak zorunda değiliz. Sadece dikey veya yatay olarak en uzak olanı düşünebiliriz.