Editorial for seqmodk: Dãy con có tổng chia hết cho K

Hiểu bài toán

Cho một dãy gồm N số nguyên và một số nguyên K. Tìm dãy con (không nhất thiết liên tiếp) có nhiều phần tử nhất sao cho tổng của các phần tử trong dãy con đó chia hết cho K.

Dữ liệu:

• N ≤ 1000, K ≤ 100.
• |a_i| ≤ 10^9.

Ví dụ: N=10, K=3, dãy [3, 2, 5, 7, 9, 6, 12, 7, 11, 15]. Tổng các số là 73, chia 3 dư 1. Nếu ta loại bỏ số 2, tổng còn lại là 71, chia 3 dư 2. Nếu ta loại bỏ số 5, tổng còn lại là 68, chia 3 dư 2. Thực tế, tổng của 9 số còn lại (loại bỏ 2) là 71, không chia hết cho 3. Tuy nhiên, dãy con 9 phần tử [3, 5, 7, 9, 6, 12, 7, 11, 15] có tổng là 75, chia hết cho 3.

Vấn đề cốt lõi là tìm cách chọn tối đa số lượng phần tử sao cho tổng chia hết cho K.

Các cách tiếp cận

Cách Quy hoạch động (Knapsack-like)

#include <bits/stdc++.h>
using namespace std;

const int INF = -1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<int> dp(k, INF);
    dp[0] = 0;

    for (int i = 0; i < n; i++) {
        vector<int> new_dp = dp;
        int x = ((a[i] % k) + k) % k;

        for (int r = 0; r < k; r++) {
            if (dp[r] >= 0) {
                int nr = (r + x) % k;
                new_dp[nr] = max(new_dp[nr], dp[r] + 1);
            }
        }
        dp = new_dp;
    }

    cout << dp[0];
    return 0;
}

• Time Complexity: O(N * K)
• Space Complexity: O(K)

Đây là phương pháp tối ưu hóa bài toán quy hoạch động.

1. Ý tưởng: Dùng mảng dp[r] để lưu số lượng phần tử nhiều nhất có thể chọn sao cho tổng các phần tử được chọn có tổng chia hết cho K dư r. Ban đầu, dp[0] = 0 (chọn 0 phần tử, tổng 0, chia hết cho K) và các dp[r] khác là -vô cùng.

2. Quá trình: Duyệt qua từng phần tử a[i] của dãy. Với mỗi phần tử, ta có 2 lựa chọn: hoặc bỏ qua nó, hoặc thêm nó vào các dãy con đã xét trước đó.

   • new_dp được khởi tạo bằng dp hiện tại (tương ứng với việc bỏ qua a[i]).
   • Với mỗi trạng thái r hợp lệ (dp[r] >= 0), ta xem xét việc thêm a[i] vào dãy con có tổng dư r. Tổng mới sẽ có dư (r + a[i]) % k. Ta cập nhật new_dp cho trạng thái mới này.

3. Kết quả: dp[0] sau khi duyệt hết dãy chính là số lượng phần tử nhiều nhất có tổng chia hết cho K.

Phương pháp này đảm bảo tìm được đáp án tối ưu với độ phức tạp chấp nhận được.

Cách Giải thuật tham lam (Loại trừ)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k; 
    cin >> n >> k;

    long long a[1005], s = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        s += a[i];
    }

    if (s % k == 0) {
        cout << n;
        return 0;
    }

    for (int i = 0; i < n; i++) {
        if ((s - a[i]) % k == 0) {
            cout << n - 1;
            return 0;
        }
    }

    cout << 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Phương pháp này dựa trên quan sát đơn giản về tổng chia hết cho K.

1. Trường hợp 1: Nếu tổng S của toàn bộ dãy chia hết cho K (S % k == 0), thì dãy con dài nhất chính là toàn bộ dãy, đáp án là N.

2. Trường hợp 2: Nếu S không chia hết cho K, để tổng dãy con chia hết cho K, ta cần loại bỏ một số phần tử sao cho tổng còn lại chia hết cho K.

   • Xét tổng S % k = r (với r != 0).
   • Nếu ta loại bỏ một phần tử có giá trị a[i], tổng mới là S - a[i]. Để S - a[i] chia hết cho K, ta cần (S - a[i]) % k == 0, suy ra a[i] % k == r.
   • Nếu t tồn tại ít nhất một phần tử a[i] có a[i] % k == r, ta chỉ cần loại bỏ 1 phần tử này. Dãy con còn lại có độ dài N - 1.
   • Nếu không có phần tử nào thỏa mãn, ta không thể tạo được dãy con tổng chia hết K bằng cách chỉ loại bỏ 1 phần tử. Trong ngữ cảnh của bài giải này, nó trả về 0. Tuy nhiên, về mặt logic toán học, có thể cần loại bỏ nhiều phần tử hơn (ví dụ 2 phần tử tổng chia hết cho K). Nhưng với các test case của bài này, dường như dữ liệu được thiết kế để chỉ kiểm tra 2 trường hợp trên.

Phương pháp này chỉ đúng với các test case đơn giản (tổng chia hết hoặc chỉ cần loại bỏ 1 phần tử).

Cách Quy hoạch động (Bộ nhớ 1 chiều)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> dp(k, -1e9);
    dp[0] = 0;

    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        int mod = ((a % k) + k) % k;
        vector<int> next_dp = dp;
        for(int r = 0; r < k; r++) {
            if (dp[r] != -1e9) {
                int new_r = (r + mod) % k;
                next_dp[new_r] = max(next_dp[new_r], dp[r] + 1);
            }
        }
        dp = next_dp;
    }
    cout << max(0, dp[0]);
    return 0;
}

• Time Complexity: O(N * K)
• Space Complexity: O(K)

Đây là cách triển khai chuẩn của phương pháp quy hoạch động.

1. State: dp[r] là độ dài dãy con dài nhất có tổng chia hết cho K dư r.
2. Initialization: dp[0] = 0, các giá trị khác là -inf.
3. Transition: Duyệt từng số a[i]. Với mỗi a[i], ta có thể chọn hoặc không chọn. Để tránh dùng lại a[i] nhiều lần cho cùng một state, ta dùng next_dp.
   • next_dp khởi tạo bằng dp (không chọn a[i]).
   • Chọn a[i]: Duyệt qua các state r cũ, state mới (r + a[i]) % k được cập nhật độ dài.

So với Solution 2, code này rõ ràng hơn và đảm bảo logic.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán này là bài toán quy hoạch động kinh điển dựa trên tổng chia hết cho K.
• Có thể giải quyết bằng cách kiểm tra các trường hợp đặc biệt (tổng chia hết hoặc loại bỏ 1 phần tử) nếu dữ liệu cho phép, nhưng phương pháp DP là chuẩn và an toàn nhất.
• Chìa khóa là giảm không gian state từ tổng thực (có thể rất lớn) về số dư (chỉ từ 0 đến K-1).

Lỗi thường gặp

• Xử lý sai số âm trong phép chia lấy dư modulo.
• Lỗi logic trong các giải thuật tham lam không đầy đủ (ví dụ chỉ loại bỏ 1 phần tử).
• Quên cập nhật state 0 (tổng chia hết) khi khởi tạo DP.