Editorial for marbles: Xếp bi

Hiểu bài toán

Cho N viên bi. Cần kiểm tra xem có thể xếp N viên bi này thành các hàng sao cho hàng thứ i chứa đúng i viên bi hay không. Nói cách khác, ta cần kiểm tra xem N có phải là tổng của một dãy số tự nhiên liên tiếp bắt đầu từ 1 hay không (ví dụ: 6 = 1 + 2 + 3, nhưng 5 không thể biểu diễn theo cách này).

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

Cách Vòng lặp cơ bản

#include <stdio.h>
int main(){
    int n, tong = 0;
    scanf("%d", &n);
    for(int i = 1; i < n; i++){
        tong += i;
        if(tong == n){
            printf("Yes.");
            return 0;
        }
    }
    printf("No.");
}

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

Hàm main() nhập N và khởi tạo biến tổng bằng 0. Vòng lặp for chạy từ i = 1 đến n-1, mỗi bước cộng dồn i vào biến tổng. Nếu tại bất kỳ bước nào tổng bằng N, in ra 'Yes.' và kết thúc. Nếu vòng lặp kết thúc mà không tìm thấy tổng bằng N, in ra 'No.'.

Cách Vòng lặp While

#include <stdio.h>
int main() {
    int n;
    scanf("%d", &n);
    int sum = 0;
    int i = 1;
    while(sum < n){
        sum += i;
        i++;
        if(sum == n){
            printf("Yes.");
            return 0;
        }
    }
    printf("No.");
    return 0;
}

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

Sử dụng vòng lặp while để cộng dồn các số tự nhiên (1, 2, 3, ...) vào biến tổng cho đến khi tổng vượt quá N. Nếu tại thời điểm nào đó tổng bằng N, in 'Yes.' và thoát. Nếu vòng lặp kết thúc (tức tổng đã vượt quá N) mà vẫn chưa bằng N thì in 'No.'.

Cách Đối sánh (Hashing)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<bool> isPossible(N + 1, false);
    int currentSum = 0;
    for (int i = 1; currentSum <= N; ++i) {
        currentSum += i;
        if (currentSum <= N) {
            isPossible[currentSum] = true;
        }
    }
    if (isPossible[N]) cout << "Yes.";
    else cout << "No.";
    return 0;
}

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

Phương pháp này预计算 tất cả các tổng có thể có nhỏ hơn hoặc bằng N. Tuy nhiên, trong ngữ cảnh này, nó chỉ đơn giản là một cách tiếp cận khác để kiểm tra. Tuy nhiên, cách tiếp cận tối ưu nhất về mặt lý thuyết là sử dụng công thức toán học: N là tổng của dãy số liên tiếp bắt đầu từ 1 khi và chỉ khi 2*N là tích của hai số nguyên dương.

Cách Toán học (Optimized)

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    long long N;
    cin >> N;
    long long twoN = 2 * N;
    long long k = sqrt(twoN);
    if (k * (k + 1) == twoN) {
        cout << "Yes.";
    } else {
        cout << "No.";
    }
    return 0;
}

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

Để N là tổng của 1 + 2 + ... + k, ta có công thức N = k(k+1)/2. Do đó, 2N = k(k+1). Ta chỉ cần tìm một số nguyên k sao cho k(k+1) = 2N. Ta có thể tìm k xấp xỉ bằng cách lấy căn bậc hai của 2N và kiểm tra hai số nguyên kề đó. Đây là phương pháp hiệu quả nhất với độ phức tạp hằng số.

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

Bài học kinh nghiệm

• Vấn đề này thực chất là kiểm tra xem N có phải là số triangular number (số hình tam giác) hay không.
• Công thức tổng quát: N = k(k+1)/2, suy ra 2N = k(k+1).

Lỗi thường gặp

• Sử dụng kiểu dữ liệu int cho N lớn (lên tới 10^6) có thể gây tràn số khi tính toán tổng hoặc bình phương, nên dùng long long.
• Vòng lặp chạy quá giới hạn (ví dụ chạy đến N thay vì sqrt(N)) gây ra TLE.