Editorial for asequence: Kiểm tra dãy số cấp số cộng

Hiểu bài toán

Bài toán yêu cầu kiểm tra xem một dãy số given có phải là một cấp số cộng (Arithmetic Progression) hay không. Một dãy số là cấp số cộng nếu hiệu số của hai phần tử liên tiếp là một hằng số không đổi (công sai). Với n phần tử, ta cần kiểm tra điều kiện: a[1] - a[0] = a[2] - a[1] = ... = a[n-1] - a[n-2]. Dữ liệu input có thể rất lớn (n lên tới 10^6, phần tử lên tới 10^18), do đó giải thuật cần phải chạy trong thời gian tuyến tính O(n) và xử lý số nguyên 64-bit.

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

Cách Đọc và Kiểm tra Trực tiếp (Dòng lệnh)

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

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

    int n;
    cin >> n;

    long long prev, cur;
    cin >> prev;

    if (n == 1) {
        cout << "YES";
        return 0;
    }

    cin >> cur;
    long long d = cur - prev;
    prev = cur;

    for (int i = 3; i <= n; i++) {
        cin >> cur;
        if (cur - prev != d) {
            cout << "NO";
            return 0;
        }
        prev = cur;
    }

    cout << "YES";
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Đây là cách tiếp cận tối ưu nhất về mặt bộ nhớ. Thay vì lưu toàn bộ dãy số vào mảng, ta chỉ cần lưu 2 số liên tiếp (số trước và số hiện tại). Khi đọc phần tử đầu tiên (a0), ta chưa thể xác định công sai. Khi đọc phần tử thứ hai (a1), ta tính ra công sai d = a1 - a0. Từ phần tử thứ 3 trở đi, với mỗi phần tử mới (cur), ta chỉ cần so sánh hiệu của nó với phần tử trước đó (prev) có bằng d hay không. Nếu không bằng, ta có thể ngay lập tức in ra "NO" và kết thúc chương trình (tối ưu hóa early exit). Nếu duyệt hết dãy mà không gặp lỗi, in "YES". Với n=1 hoặc n=2, mọi dãy đều là cấp số cộng nên trả về "YES".

Cách Lưu trữ Toàn bộ và Kiểm tra

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

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

    if (n <= 2) {
        cout << "YES";
        return 0;
    }

    int dem = 1; 
    long long tmp = a[1] - a[0]; 
    for(int i = 1; i < n - 1; i++) { 
        if(a[i+1] - a[i] == tmp){ 
            ++dem; 
        }
    } 
    if(dem == n - 1) { 
        cout << "YES"; 
    } else 
        cout << "NO"; 
}

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

Cách tiếp cận này lưu toàn bộ dãy số vào mảng a[n] trước. Sau đó, nó tính công sai tmp từ hai phần tử đầu tiên. Vòng lặp chạy từ i=1 đến n-2, kiểm tra xem hiệu số a[i+1] - a[i] có bằng tmp không. Biến đếm dem tăng lên nếu điều kiện đúng. Cuối cùng, so sánh dem với n-1 (số cặp liên tiếp cần kiểm tra) để kết luận. Nhược điểm là tốn bộ nhớ O(n) không cần thiết.

Cách Đọc và Kiểm tra (Phiên bản xử lý n=2)

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

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

    int n;
    cin >> n;

    if (n <= 2) {
        cout << "YES";
        return 0;
    }

    long long prev, curr;
    cin >> prev; 
    cin >> curr; 

    long long d = curr - prev; 
    prev = curr;

    for (int i = 3; i <= n; i++) {
        cin >> curr;
        if (curr - prev != d) {
            cout << "NO";
            return 0;
        }
        prev = curr;
    }

    cout << "YES";
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Đây là phiên bản tương tự Approach 1 nhưng logic xử lý số lượng phần tử (n) được viết gọn hơn một chút. Thay vì kiểm tra n==1 riêng, nó kiểm tra n <= 2 ở đầu. Nếu n=1 hoặc 2, kết quả luôn là YES. Với n>=3, nó đọc hai số đầu tiên để tính d, rồi lặp từ số thứ 3 để kiểm tra. Về bản chất, đây là cách tiếp cận tối ưu và phổ biến nhất.

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

Bài học kinh nghiệm

• Không cần lưu trữ toàn bộ dãy số: Chỉ cần quan tâm đến phần tử hiện tại và phần tử ngay trước nó để tính hiệu số và so sánh với công sai ban đầu.
• Xử lý trường hợp cơ bản: Với n=1 hoặc n=2, mọi dãy số đều hợp lệ là một cấp số cộng.
• Tối ưu hóa Early Exit: Ngay khi phát hiện một hiệu số sai lệch, chương trình có thể dừng lại và in kết quả ngay lập tức thay vì tiếp tục vòng lặp.

Lỗi thường gặp

• Lỗi tràn số (Integer Overflow): Nếu tính tổng dãy số thay vì hiệu số, hoặc nếu dùng int (32-bit) thay vì long long (64-bit) khi số đầu vào lên tới 10^18, sẽ gây ra lỗi tràn số sai kết quả. Phải dùng long long.
• Quên xử lý trường hợp n=1: Nếu không xử lý riêng, việc truy cập vào phần tử thứ 2 (index 1) sẽ gây lỗi truy cập bộ nhớ ngoài phạm vi (Segmentation Fault).
• So sánh số thực (Floating Point Comparison): Không được dùng số thực để lưu trữ số nguyên hoặc thực hiện phép chia lấy dư khi kiểm tra cấp số cộng, vì sai số làm tròn. Chỉ nên dùng số nguyên và phép trừ.