Editorial for Combo Hai Ly


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Nghaiz

Lời giải: Combo Hai Ly

Chủ đề: từ điển (dict) để đếm

Tóm tắt đề

Cho dãy \(a_1, \dots, a_n\) và số \(K\). Đếm số cặp chỉ số \(i < j\) sao cho \(a_i + a_j = K\).

Cách ngây thơ: hai vòng lặp

for i in range(n):
    for j in range(i + 1, n):
        if a[i] + a[j] == K: dem += 1

Đúng, nhưng có tới \(\dfrac{n(n-1)}{2} \approx 2 \cdot 10^{10}\) cặp khi \(n = 2 \times 10^5\). Python chỉ chạy được khoảng \(10^7\) phép tính mỗi giây → TLE.

Ý tưởng: "nhìn lại phía sau" bằng dict

Duyệt các ly từ trái sang phải. Khi đứng ở ly giá \(x\), ly này ghép được với mọi ly giá \(K - x\) đã gặp trước đó. Nếu ta biết có bao nhiêu ly giá \(K - x\) đứng trước, ta cộng ngay số đó vào đáp án.

Để biết "có bao nhiêu ly giá \(v\) đã gặp", ta dùng một dict tên dem, với dem[v] là số lượng ly giá \(v\) đã duyệt qua:

for x in gia:
    so_cap += dem.get(K - x, 0)     # ghép với các ly đứng TRƯỚC
    dem[x] = dem.get(x, 0) + 1      # rồi mới đưa ly hiện tại vào

Vì sao cách này đúng?

  • Mỗi cặp \((i, j)\) với \(i < j\) được đếm đúng một lần, tại thời điểm duyệt tới \(j\).
  • Ly hiện tại được đưa vào dem sau khi đã đếm, nên nó không bao giờ tự ghép với chính nó. Ví dụ \(K = 8\) và chỉ có một ly giá \(4\) thì đáp án là \(0\) (Sample 2).
  • Nhiều ly cùng giá được đếm đầy đủ, ví dụ bốn ly giá \(5\) với \(K = 10\) cho \(0 + 1 + 2 + 3 = 6\) cặp.

Mỗi thao tác với dict chỉ mất thời gian trung bình \(O(1)\), nên cả thuật toán chạy \(O(n)\).

Độ phức tạp

\(O(n)\) thời gian, \(O(n)\) bộ nhớ.

Code mẫu

n, k = map(int, input().split())
gia = list(map(int, input().split()))

dem = {}
so_cap = 0
for x in gia:
    so_cap += dem.get(k - x, 0)
    dem[x] = dem.get(x, 0) + 1

print(so_cap)

Comments

There are no comments at the moment.