Editorial for candy: Chia kẹo 1

Hiểu bài toán

Bài toán yêu cầu chia một dãy gồm N gói kẹo (với số lượng viên kẹo trong mỗi gói là A[i]) thành hai phần liên tiếp dựa trên một chỉ số k (1 ≤ k ≤ N-1). Phần An gồm các gói từ 1 đến k, phần Bình gồm các gói từ k+1 đến N. Mục tiêu là tìm giá trị k sao cho chênh lệch giữa tổng số kẹo của An và Bình là nhỏ nhất. Nói cách khác, cần tìm min(|Sum(1..k) - Sum(k+1..N)|) với k chạy từ 1 đến N-1.

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

Cách Brute Force (Tính lại tổng từ đầu)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main() {
    int N;
    scanf("%d", &N);
    long long *A = (long long*)malloc(N * sizeof(long long));
    for (int i = 0; i < N; i++) {
        scanf("%lld", &A[i]);
    }

    long long total = 0;
    for (int i = 0; i < N; i++) total += A[i];

    long long min_diff = total; // Khởi tạo giá trị lớn

    // Duyệt qua tất cả các vị trí k
    for (int k = 1; k < N; k++) {
        long long sum_an = 0;
        for (int i = 0; i < k; i++) {
            sum_an += A[i];
        }
        long long sum_binh = total - sum_an;
        long long diff = llabs(sum_an - sum_binh);
        if (diff < min_diff) min_diff = diff;
    }

    printf("%lld\n", min_diff);
    free(A);
    return 0;
}

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

Cách tiếp cận này sử dụng hai vòng lặp lồng nhau. Vòng lặp ngoài duyệt qua tất cả các vị trí k có thể (từ 1 đến N-1). Với mỗi k, vòng lặp trong tính tổng số kẹo của An bằng cách cộng dồn các phần tử từ A[0] đến A[k-1]. Sau đó tính tổng của Bình và chênh lệch. Phương pháp này chậm chạp và chỉ phù hợp với N nhỏ (Subtask 1).

Cách Prefix Sum (Tính tổng tiền tố)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main() {
    int N;
    scanf("%d", &N);
    long long *A = (long long*)malloc(N * sizeof(long long));
    for (int i = 0; i < N; i++) {
        scanf("%lld", &A[i]);
    }

    long long total = 0;
    for (int i = 0; i < N; i++) total += A[i];

    long long prefix = 0;
    long long min_diff = 9223372036854775807LL; // Giá trị LLONG_MAX

    for (int i = 0; i < N - 1; i++) {
        prefix += A[i]; // prefix là tổng của An (từ 0 đến i)
        long long sum_binh = total - prefix;
        long long diff = llabs(prefix - sum_binh);
        if (diff < min_diff) {
            min_diff = diff;
        }
    }

    printf("%lld\n", min_diff);
    free(A);
    return 0;
}

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

Đây là cách tiếp cận tối ưu. Thay vì tính lại tổng từ đầu mỗi lần, ta sử dụng biến prefix để lưu tổng tiền tố. Khi duyệt từ i = 0 đến N-2:

1. Cộng dồn A[i] vào biến prefix. Biến này lúc này đại diện cho tổng kẹo của An (từ gói 1 đến k, với k = i+1).
2. Tổng kẹo của Bình là total - prefix.
3. Tính chênh lệch và cập nhật kết quả. Cách này chỉ cần duyệt qua mảng một lần duy nhất, giảm độ phức tạp thời gian từ O(N^2) xuống O(N).

Cách Tối ưu hóa công thức toán học

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main() {
    int N;
    scanf("%d", &N);
    long long *A = (long long*)malloc(N * sizeof(long long));
    for (int i = 0; i < N; i++) {
        scanf("%lld", &A[i]);
    }

    long long total = 0;
    for (int i = 0; i < N; i++) total += A[i];

    long long prefix = 0;
    long long min_diff = llabs(2 * A[0] - total); // Khởi tạo cho k=1

    for (int i = 0; i < N - 1; i++) {
        prefix += A[i];
        // Chênh lệch = |prefix - (total - prefix)| = |2*prefix - total|
        long long diff = llabs(2 * prefix - total);
        if (diff < min_diff) {
            min_diff = diff;
        }
    }

    printf("%lld\n", min_diff);
    free(A);
    return 0;
}

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

Cách tiếp cận này về mặt bản chất tương tự như Prefix Sum, nhưng tối ưu hóa ở bước tính toán chênh lệch. Thay vì tính sum_binh rồi trừ, ta nhận thấy: |SumAn - SumBinh| = |SumAn - (Total - SumAn)| = |2 * Sum_An - Total| Công thức này giúp giảm số phép toán trong vòng lặp. Tuy nhiên, độ phức tạp Big-O vẫn là O(N).

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

Bài học kinh nghiệm

• Bài toán có thể quy về việc tìm giá trị nhỏ nhất của biểu thức |2 * PrefixSum(k) - TotalSum| với k chạy từ 1 đến N-1.
• Cần lưu ý rằng chỉ số k chỉ được phép chạy đến N-1, vì nếu k = N thì Bình không nhận được gói kẹo nào (theo đề bài là từ k+1 đến N), điều này không hợp lệ.
• Kiểu dữ liệu cần sử dụng là long long (hoặc int64) vì tổng số kẹo có thể lên tới 200,000 * 10^9 = 2*10^14, vượt quá giới hạn của int (32-bit).

Lỗi thường gặp

• Sử dụng kiểu dữ liệu int gây tràn số (overflow) khi tính tổng.
• Lặp sai giới hạn chỉ số k: Vòng lặp phải chạy từ 0 đến N-2 (tương đương k từ 1 đến N-1), nếu chạy đến N-1 sẽ gây lỗi logic hoặc lỗi truy cập mảng.
• Khởi tạo biến min_diff sai giá trị ban đầu (ví dụ 0)导致 sai kết quả.