Hiểu bài toán

Bài toán yêu cầu tìm diễn đàn được Dũng truy cập nhiều lần nhất trong d ngày. Với mỗi ngày, Dũng bắt đầu từ diễn đàn s, sau đó truy cập các diễn đàn s + k, s + 2k, ... cho đến khi vượt quá n hoặc đã truy cập đủ p diễn đàn. Ta cần đếm số lần mỗi diễn đàn được truy cập, sau đó tìm diễn đàn có số lần truy cập lớn nhất. Nếu có nhiều diễn đàn cùng số lần, chọn diễn đàn có số thứ tự nhỏ nhất.

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

Cách Brute Force

void solve_brute_force() {
    int n, d;
    cin >> n >> d;
    vector<int> cnt(n + 1, 0);
    for (int day = 0; day < d; day++) {
        int s, k, p;
        cin >> s >> k >> p;
        int cur = s;
        for (int i = 0; i < p && cur <= n; i++) {
            cnt[cur]++;
            cur += k;
        }
    }
    int max_cnt = 0;
    int ans = 1;
    for (int i = 1; i <= n; i++) {
        if (cnt[i] > max_cnt) {
            max_cnt = cnt[i];
            ans = i;
        }
    }
    cout << "Dung can hack dien dan " << ans << ".";
}

• Time Complexity: O(d * p) ~ O(d * n)
• Space Complexity: O(n)

Cách tiếp cận trực quan nhất là mô phỏng chính xác quá trình truy cập của Dũng. Với mỗi ngày, ta bắt đầu từ s, lặp p lần, mỗi lần tăng chỉ số lên k và cập nhật biến đếm cho diễn đàn đó. Tuy nhiên, p có thể lên tới n (10^5) và d cũng lên tới 10^5, nên độ phức tạp O(d * p) có thể lên tới 10^10, gây quá thời gian. Giải pháp này chỉ khả thi khi p nhỏ.

Cách Difference Array (Optimized)

void solve_difference_array() {
    int n, d;
    cin >> n >> d;
    vector<int> cnt(n + 2, 0);
    for (int day = 0; day < d; day++) {
        int s, k, p;
        cin >> s >> k >> p;
        // Tăng số lần truy cập cho các vị trí s, s+k, s+2k, ...
        // Sử dụng difference array để xử lý các bước nhảy k
        // Tuy nhiên, cách này vẫn cần lặp p lần nếu k lớn
        // Ta cần tối ưu hóa bằng cách đếm số lượng theo nhóm residue
    }
    // ...

• Time Complexity: O(d * (n/k))
• Space Complexity: O(n)

Giả sử k nhỏ (ví dụ k <= 10), ta có thể tối ưu bằng cách nhận thấy các số truy cập tạo thành một dãy cộng. Với mỗi (s, k, p), các số truy cập là s, s+k, ..., s+(p-1)k. Nếu k nhỏ, số lượng phần tử trong mỗi nhóm residue theo modulo k là khoảng n/k. Tuy nhiên, do k rất nhỏ (<= 10), ta có thể tối ưu hơn bằng cách đếm trực tiếp cho mỗi nhóm residue. Phương pháp này vẫn chưa thực sự tối ưu nhất vì có thể có nhiều ngày có cùng k và residue.

Cách Prefix Sum per Residue (Optimal)

void solve_optimal() {
    int n, d;
    cin >> n >> d;
    vector<vector<int>> add(11, vector<int>(11, 0));
    vector<int> cnt(n + 1, 0);

    // Đọc input và lưu theo nhóm (k, residue)
    for (int i = 0; i < d; i++) {
        int s, k, p;
        cin >> s >> k >> p;
        int start = s;
        int end = s + p * k;
        // Với mỗi nhóm residue, ta cần đánh dấu mốc bắt đầu và kết thúc
        // Sử dụng difference array cho mỗi nhóm residue
    }

    // Giải pháp từ Solution 2:
    vector<pair<int, int>> v[11]; // v[k] chứa các cặp (s, p)
    for (int i = 0; i < d; i++) {
        int s, k, p;
        cin >> s >> k >> p;
        v[k].push_back({s, p});
    }

    for (int k = 2; k <= 10; k++) {
        if (v[k].empty()) continue;
        vector<int> add(n + 1, 0);
        vector<int> cur(k, 0); // Mảng hiện tại cho mỗi residue

        for (auto x : v[k]) {
            int s = x.first;
            int p = x.second;
            add[s]++;
            if (s + p * k <= n) add[s + p * k]--;
        }

        for (int j = 1; j <= n; j++) {
            cur[j % k] += add[j];
            cnt[j] += cur[j % k];
        }
    }

    int max_val = 0;
    int ans = 1;
    for (int i = 1; i <= n; i++) {
        if (cnt[i] > max_val) {
            max_val = cnt[i];
            ans = i;
        }
    }
    cout << "Dung can hack dien dan " << ans << ".";
}

• Time Complexity: O(d + n * 10)
• Space Complexity: O(n)

Đây là giải pháp tối ưu nhất. Ý tưởng là xử lý riêng cho mỗi giá trị k (từ 2 đến 10). Với mỗi k, các số được truy cập sẽ có cùng residue modulo k.

Ta sử dụng Difference Array để xử lý các đoạn [s, s + p*k) với bước nhảy k.

1. Với mỗi ngày (s, k, p), ta đánh dấu mốc bắt đầu tăng tại s (add[s]++), và mốc kết thúc tại s + pk (add[s + pk]--).
2. Duyệt từ 1 đến n, duy trì biến currentvalue cho mỗi residue j (0 <= j < k). Với mỗi chỉ số i, currentvalue[i % k] += add[i].
3. Giá trị current_value[i % k] tại thời điểm i chính là số lần diễn đàn i được truy cập.

Độ phức tạp: O(d + n * 10) do duyệt qua n phần tử và với mỗi phần tử cập nhật 10 giá trị (cho k từ 2 đến 10).

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

Bài học kinh nghiệm

• Bài toán có thể coi là bài toán đếm số lần xuất hiện của các số trong các dãy số học.
• Do k nhỏ (2 <= k <= 10), ta có thể tối ưu bằng cách nhóm các truy vấn theo giá trị k và residue modulo k.
• Sử dụng Difference Array kết hợp với duy trì trạng thái hiện tại (current state) cho phép xử lý các dãy số học hiệu quả trong O(1) cập nhật cho mỗi bước.

Lỗi thường gặp

• Làm sai quy luật truy cập: Quên điều kiện dừng khi vượt quá n hoặc sau p lần truy cập.
• Xử lý mảng trong C++: Sai chỉ số mảng (vượt quá n) hoặc quên khởi tạo mảng.
• Hiểu sai về độ phức tạp: Cho rằng O(d * p) là chấp nhận được trong khi d*p có thể lên tới 10^10.