Nhận diện bài toán và kiểm chứng lời giải

Lan cần đếm các đoạn liên tiếp có tổng bằng 3 trong dãy 1, -1, 3, 0. Bạn thử cộng từng đoạn nhưng lo mình bỏ sót. Khi dãy có 100 000 phần tử, cách thử từng đoạn có thể cần hàng tỷ lần cộng. Làm sao tìm cách nhanh hơn mà vẫn tin kết quả?

Đọc đề thành dữ kiện có thể kiểm tra

Trước khi viết code, hãy ghi dữ liệu vào, kết quả cần in, miền giá trị và giới hạn kích thước. Một ví dụ chỉ minh họa yêu cầu, không thay thế toàn bộ đề. Đặc biệt, từ “liên tiếp” yêu cầu các phần tử đứng cạnh nhau; chọn tập con tùy ý là một bài khác.

Xét đề sau: cho n số nguyên a, đếm các đoạn liên tiếp không rỗng có tổng bằng k. Các đoạn khác vị trí được tính riêng, kể cả khi giá trị giống nhau. Đề cho 1 ≤ n ≤ 100000 và -10^9 ≤ a[i], k ≤ 10^9.

Với a = [1, -1, 3, 0], k = 3, các đoạn hợp lệ là [1, -1, 3], [3], [3, 0] và [1, -1, 3, 0]. Dưới đây chương trình kiểm tra một đoạn cụ thể:

a = [1, -1, 3, 0]
print(sum(a[1:4]))

2

Kết quả là 2, nên đoạn này không được tính. Chỉ số Python bắt đầu từ 0 và đầu phải của lát cắt không được lấy.

Ước lượng số phép tính trước khi chọn kỹ thuật

Độ phức tạp thời gian (time complexity) mô tả số thao tác tăng theo kích thước đầu vào. Nó không trực tiếp đo số giây: máy chạy, ngôn ngữ và hằng số đều ảnh hưởng. Bài 2 giải thích chi tiết hơn.

Bảng chỉ là gợi ý, không phải công thức đoán đáp án. Chẳng hạn, từ “đoạn” không đủ để kết luận dùng cửa sổ trượt. Số âm có thể làm tổng giảm khi mở rộng cửa sổ, phá điều kiện thường dùng của kỹ thuật đó.

Với n = 100000, số đoạn không rỗng là n * (n + 1) // 2, hơn 5 tỷ. Một thuật toán kiểm tra từng đoạn cần O(n²) bước, thường quá lớn. Một lượt duyệt với tra cứu bảng băm có O(n) thời gian trung bình và O(n) bộ nhớ, phù hợp hơn, nhưng vẫn phải kiểm chứng cách đếm.

for n in (10, 1000, 100000):
    print(n, n * (n + 1) // 2)

10 55
1000 500500
100000 5000050000

Lời giải vét cạn cho biết đáp án của dữ liệu nhỏ

Vét cạn (brute force) là thử tất cả ứng viên theo định nghĩa bài toán. Với mỗi đầu trái, cộng lần lượt các phần tử đến từng đầu phải. Mỗi đoạn được xét đúng một lần vì nó có duy nhất một cặp đầu trái và đầu phải.

def brute(a, k):
    answer = 0
    for left in range(len(a)):
        total = 0
        for right in range(left, len(a)):
            total += a[right]
            if total == k:
                answer += 1
    return answer

print(brute([1, -1, 3, 0], 3))
print(brute([0, 0], 0))

4
3

Hai số 0 tạo ba đoạn khác vị trí: phần tử đầu, phần tử cuối và cả dãy. Code dùng tổng đang chạy nên mỗi đoạn thêm đúng một phép cộng. Với n = 100, có 5 050 đoạn; cách này thuận tiện làm đáp án tham chiếu. Với n = 100000, nó không phù hợp để nộp.

Hiệu hai tổng tiền tố biến đoạn thành một phép tra cứu

Gọi p[0] = 0 và p[i] là tổng i phần tử đầu. Tổng đoạn từ chỉ số l đến r - 1 là p[r] - p[l], như Bài 12. Đoạn có tổng k khi p[l] = p[r] - k, với l < r.

Mỗi lần đi đến một tiền tố mới p[r], ta cần đếm các tiền tố trước đó có giá trị p[r] - k. Một bảng tần suất (frequency table) lưu số lần mỗi giá trị đã xuất hiện. Với dãy trên và k = 3, hai tiền tố 0 trước p[3] tạo hai đoạn; hai tiền tố 0 trước p[4] tạo thêm hai đoạn. Kết quả là 4 đoạn.

Khởi tạo bảng bằng {0: 1} để tính các đoạn bắt đầu ở đầu dãy. Tra cứu trước khi thêm tiền tố hiện tại để không đếm đoạn rỗng khi k = 0.

def fast(a, k):
    freq = {0: 1}
    prefix = 0
    answer = 0
    for x in a:
        prefix += x
        answer += freq.get(prefix - k, 0)
        freq[prefix] = freq.get(prefix, 0) + 1
    return answer

print(fast([1, -1, 3, 0], 3))
print(fast([0, 0], 0))

4
3

Trước mỗi lần tra cứu, bảng chứa đúng các tiền tố có chỉ số nhỏ hơn r. Mỗi lần xuất hiện của p[r] - k ứng với một đầu trái hợp lệ, và không đầu trái nào khác hợp lệ. Sau đó thêm p[r], duy trì điều kiện này cho bước sau. Do đó mọi đoạn được tính đúng một lần, kể cả số âm và tiền tố trùng nhau.

Mỗi phần tử cần một lần tra cứu và một lần cập nhật dict: O(n) trung bình, bộ nhớ tối đa O(n). Với 100 000 phần tử, số lượt duyệt chính là 100 000. Đây là phân tích trung bình của bảng băm, không phải cam kết thời gian chạy cố định.

Giới hạn độ dài thay đổi tập tiền tố được phép

Đôi khi đề chỉ nhận đoạn có độ dài từ L đến R. Đoạn biểu diễn bằng p[r] - p[l] có độ dài r - l. Do đó, với một đầu phải r, tiền tố hợp lệ có chỉ số từ r - R đến r - L, giao với miền 0 đến r - 1.

Ví dụ r = 4, L = 2, R = 3: chỉ l = 1 hoặc l = 2 hợp lệ. Đầu trái l = 0 tạo đoạn dài 4; l = 3 tạo đoạn dài 1. Hai đầu mút đều được tính nếu đề ghi “từ 2 đến 3”.

Khi r tăng thêm một, chỉ số r - L vừa vào khoảng hợp lệ. Chỉ số r - R - 1 vừa rời khoảng. Thêm hoặc bớt tần suất của hai tiền tố đó, rồi tra số tiền tố có giá trị p[r] - k. Khi chỉ có giới hạn dài nhất R, dùng L = 1.

L, R = 2, 3
for r in range(1, 6):
    indices = list(range(max(0, r - R), r - L + 1))
    print(r, indices)

1 []
2 [0]
3 [0, 1]
4 [1, 2]
5 [2, 3]

Nếu cận trên nhỏ hơn cận dưới, range() tạo dãy rỗng. Mỗi tiền tố vào một lần và rời tối đa một lần. Vì vậy cách duy trì bảng cần O(n) thao tác bảng băm trung bình, thay vì duyệt lại đến R ứng viên ở mỗi đầu phải.

Số dư giúp nhận diện tổng chia hết

Giả sử m là số nguyên dương. Hai số nguyên có cùng số dư khi chia cho m thì hiệu của chúng chia hết cho m. Vì thế tổng đoạn p[r] - p[l] chia hết cho m khi hai tiền tố có cùng số dư.

Ví dụ p[l] = -2, p[r] = 4, m = 3. Cả hai có số dư 1 trong Python, còn hiệu là 6. Điều kiện vẫn đúng với tổng âm; không cần bỏ các số âm khỏi dữ liệu.

left, right, m = -2, 4, 3
print(left % m, right % m)
print((right - left) % m)

1 1
0

Để đếm các đoạn chia hết có độ dài giới hạn, thay khóa giá trị tiền tố trong bảng tần suất bằng p[i] % m. Tập chỉ số hợp lệ vẫn là khoảng từ r - R đến r - L. Mỗi đơn vị tần suất của một số dư ứng với đúng một tiền tố hợp lệ, nên nhiều tiền tố cùng số dư vẫn được đếm riêng.

Với n = 2000, cách xét mọi đoạn có khoảng hai triệu ứng viên. Nếu cần mở rộng lên dữ liệu lớn hơn, duy trì tần suất số dư theo cửa sổ chỉ số giảm số thao tác xuống O(n) trung bình. Bộ nhớ chứa tiền tố và bảng tần suất là O(n + m) trong giới hạn tổng quát này.

Đưa thuật toán vào chương trình có đầu vào rõ ràng

Giả sử đề quy định dòng đầu là n k, dòng sau chứa đúng n số. Chương trình sau chỉ in số đoạn, không in lời nhắc hay trạng thái gỡ lỗi.

4 3
1 -1 3 0

n, k = map(int, input().split())
a = list(map(int, input().split()))
freq = {0: 1}
prefix = 0
answer = 0
for x in a:
    prefix += x
    answer += freq.get(prefix - k, 0)
    freq[prefix] = freq.get(prefix, 0) + 1
print(answer)

4

Kết quả là 4. Biến n mô tả số phần tử theo hợp đồng đầu vào. Khi nộp, hãy kiểm tra đề có cho dãy trải trên nhiều dòng hay không; nếu có, chọn cách đọc phù hợp.

Thiết kế kiểm thử để phân biệt các lỗi có thể xảy ra

Trường hợp biên (boundary case) nằm ở giới hạn hoặc sát chỗ quyết định của thuật toán. Một bộ kiểm thử tốt còn chứa dữ liệu khiến lời giải sai cho kết quả khác. Ví dụ, [0] với k = 0 phát hiện cách thêm tiền tố trước khi tra cứu.

Chương trình dưới in kết quả của ba trường hợp để bạn tự kiểm lại theo định nghĩa:

def count(a, k):
    result = 0
    for left in range(len(a)):
        total = 0
        for right in range(left, len(a)):
            total += a[right]
            result += total == k
    return result

for a, k in [([3], 3), ([0, 0], 0), ([2, -1, 2], 3)]:
    print(a, k, count(a, k))

[3] 3 1
[0, 0] 0 3
[2, -1, 2] 3 1

Kiểm thử lớn có vai trò khác: đo xem chương trình có xử lý kịp và đủ bộ nhớ hay không. Dữ liệu lớn không thay thế lời giải thích tính đúng. Khi đo trên máy của bạn, thời gian chỉ phản ánh môi trường đó, không bảo đảm kết quả trên máy chấm.

Đối chiếu tự động tìm phản ví dụ nhỏ

Kiểm thử đối chiếu (differential testing) chạy hai cách độc lập trên cùng dữ liệu rồi so kết quả. Ở đây cách chậm làm đáp án tham chiếu cho dữ liệu nhỏ; cách nhanh là ứng viên. Không dùng chính công thức của ứng viên để viết lời giải tham chiếu, vì hai bên có thể cùng mắc một lỗi.

Đoạn sau dùng Random(45) để tạo 500 dãy nhỏ có số âm và số 0. Một hạt giống (seed) cố định giúp chạy lại cùng chuỗi trong cùng môi trường. Dữ liệu ngẫu nhiên không chứng minh chương trình đúng với mọi đầu vào.

from random import Random

def brute(a, k):
    count = 0
    for left in range(len(a)):
        total = 0
        for right in range(left, len(a)):
            total += a[right]
            count += total == k
    return count

def fast(a, k):
    freq = {0: 1}
    prefix = count = 0
    for x in a:
        prefix += x
        count += freq.get(prefix - k, 0)
        freq[prefix] = freq.get(prefix, 0) + 1
    return count

rng = Random(45)
for case in range(500):
    a = [rng.randint(-3, 3) for _ in range(rng.randint(1, 8))]
    k = rng.randint(-5, 5)
    expected = brute(a, k)
    actual = fast(a, k)
    if expected != actual:
        print("Sai", case, a, k, expected, actual)
        break
else:
    print("Khớp 500 trường hợp")

Khớp 500 trường hợp

Nếu có sai lệch, lưu cả dãy, k, kết quả hai bên và hạt giống. Không chỉ in “sai”: thông tin cụ thể cho phép tái hiện lỗi. Sau khi sửa, chạy lại trường hợp đó và toàn bộ bộ kiểm thử.

Thu nhỏ phản ví dụ để thấy sai ở bước nào

Giả sử một phiên bản thêm tiền tố trước khi tra cứu. Với k = 0, nó tự ghép tiền tố hiện tại với chính nó và đếm thêm đoạn rỗng. Dãy [0] đủ tái hiện lỗi, dễ theo dõi hơn một dãy dài 100 phần tử.

freq = {0: 1}
prefix = 0
freq[prefix] = freq.get(prefix, 0) + 1
print("Thêm trước:", freq.get(prefix, 0))
print("Đúng:", 1)

Thêm trước: 2
Đúng: 1

Bạn có thể thử xóa từng phần tử của một phản ví dụ lớn, nhưng chỉ giữ thay đổi nếu lỗi vẫn xảy ra và dữ liệu còn hợp lệ. Một phản ví dụ nhỏ chỉ ra lỗi; nó không tự chứng minh phần còn lại đã đúng. Hãy đối chiếu lại sau sửa, kể cả trên các trường hợp biên khác.

Không phải mọi kết quả khác nhau đều do lời giải nhanh sai. Kiểm tra lại lời giải chậm, giả thiết đầu vào và quy ước đoạn rỗng trước khi sửa. Một print() bổ sung có thể hỗ trợ dò biến tại máy của bạn, nhưng phải bỏ khỏi đầu ra nộp bài.

Đọc kết quả chấm để chọn bước điều tra

Nếu máy chấm trả Sai kết quả (wrong answer), trước hết hãy so định dạng và kiểm thử biên. Một chương trình chạy xong vẫn có thể bỏ sót đáp án, đếm thừa hoặc in thêm dòng. Dùng lời giải tham chiếu trên dữ liệu nhỏ để tách lỗi thuật toán khỏi lỗi trình bày.

Nếu nhận Quá thời gian (time limit exceeded), hãy đối chiếu giới hạn với số bước của thuật toán. Ví dụ, n = 100000 tạo hơn 5 tỷ đoạn, nên đổi tên biến hay bỏ một phép in khó giải quyết gốc rễ. Cần tìm cách tránh xét từng đoạn, rồi đo lại trên dữ liệu lớn hợp lệ.

Nếu chương trình gặp lỗi khi chạy, hãy đọc thông báo và tìm dòng gây lỗi trên dữ liệu tái hiện. Chỉ số vượt giới hạn, chia cho 0 và đọc thiếu dữ liệu là những nguyên nhân khác nhau. Sau khi sửa, chạy lại test gây lỗi cùng các test từng đúng để tránh tạo lỗi mới.

Lỗi thường gặp

Tóm tắt

Đọc hợp đồng vào, ra và giới hạn trước khi chọn kỹ thuật. Xây dựng lời giải nhỏ dễ kiểm tra, rồi chọn thuật toán nhanh có chứng minh và ước lượng chi phí. Với tổng đoạn, hiệu hai tiền tố và bảng tần suất cho phép đếm theo từng đầu phải. Kiểm thử biên, đối chiếu và thu nhỏ phản ví dụ giúp phát hiện lỗi triển khai.

Kiểm tra nhanh

Đọc thêm

• Tài liệu Python về random: bộ sinh giả ngẫu nhiên và khả năng tái lập.
• Tài liệu Python về dict: thao tác với bảng ánh xạ.