Editorial for Combo Hai Ly
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
demsau 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