Hiểu bài toán

Bài toán yêu cầu đếm số cặp chỉ số (i, j) sao cho i < j và a[i] * 10 <= a[j] * 9. Nói cách khác, một cặp (i, j) được tính nếu a[j] >= (10/9) * a[i]. Dưới đây là ví dụ minh họa:

Ví dụ: Input: n = 5, mảng a = {1, 10, 100, 1000, 10000} Giải thích:

• i=0 (a[0]=1): Các j > 0 thỏa mãn a[j] >= (10/9)*1 ~ 1.11. Các số 10, 100, 1000, 10000 đều thỏa mãn. => 4 cặp.
• i=1 (a[1]=10): Các j > 1 thỏa mãn a[j] >= (10/9)*10 ~ 11.11. Các số 100, 1000, 10000 đều thỏa mãn. => 3 cặp.
• i=2 (a[2]=100): Các j > 2 thỏa mãn a[j] >= 111.11. Các số 1000, 10000 đều thỏa mãn. => 2 cặp.
• i=3 (a[3]=1000): Các j > 3 thỏa mãn a[j] >= 1111.11. Số 10000 thỏa mãn. => 1 cặp.
• i=4: Không có j > 4. => Tổng số cặp là 4+3+2+1 = 10.

Lưu ý: Điều kiện đề bài là a[i]10 <= a[j]9, hay a[i] <= (9/10)a[j]. Tuy nhiên, trong các giải pháp accepted, tác giả lại dùng điều kiện a[j] <= a[i]10/9 (đếm số j sao cho a[j] nhỏ hơn hoặc bằng ngưỡng). Nghịch lại, ta đang đếm các cặp (i, j) sao cho a[j] <= (10/9)*a[i]. Thực tế, đề bài gốc có thể bị viết sai hoặc các giải pháp accepted đang giải quyết một bài toán tương tự (ví dụ: đếm cặp (i, j) sao cho a[j] * 10 <= a[i] * 9, hoặc chỉ cần sort mảng và xử lý). Dựa trên code, ta sẽ phân tích bài toán mà code đang giải quyết: Đếm số cặp (i, j) với i < j và a[j] <= a[i] * 10 / 9.

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

Cách Brute Force (Vét cạn)

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (a[i] * 10 <= a[j] * 9) {
            count++;
        }
    }
}

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

Sử dụng hai vòng lặp lồng nhau để duyệt qua tất cả các cặp (i, j) thỏa mãn điều kiện i < j. Với mỗi cặp, kiểm tra điều kiện trực tiếp. Cách này chậm và chỉ phù hợp với n rất nhỏ (<= 1000).

Cách Binary Search (Tìm kiếm nhị phân)

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

int main() {
    int n; cin >> n;
    vector<long long> a(n);
    for(int i=0; i<n; i++) cin >> a[i];
    sort(a.begin(), a.end());

    long long ans = 0;
    for(int i=0; i<n; i++) {
        // Tìm vị trí đầu tiên mà a[j] > a[i] * 10 / 9
        long long limit = a[i] * 10 / 9;
        int pos = upper_bound(a.begin(), a.end(), limit) - a.begin();
        // Số lượng phần tử thỏa mãn a[j] <= limit trong đoạn (i, n)
        // là (pos - 1) - i
        // Tuy nhiên code gốc dùng: R - L, với R = pos, L = i+1
        // Nghĩa là đếm các chỉ số j từ i+1 đến pos-1.
        // Nếu a[i] * 10 / 9 là số thực, phép chia nguyên 10/9 = 1 sẽ sai.
        // Code dùng a[i]*10/9 với a[i] là long long => phép chia nguyên.
        // Ví dụ a[i]=9, limit = 10. a[i]=8, limit = 8.
        // Điều kiện thực tế trong code là tìm phần tử <= limit.
        // Với ví dụ bài toán (a[i]*10 <= a[j]*9) <=> a[j] >= a[i]*10/9.
        // Code lại tìm a[j] <= a[i]*10/9.
        // Có vẻ bài toán là "Đếm cặp (i, j) sao cho a[j] <= a[i]*10/9".
    }
    cout << ans;
}

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

Bước 1: Sắp xếp mảng a tăng dần. Bước 2: Duyệt qua từng phần tử a[i]. Vì mảng đã sort, ta chỉ cần quan tâm đến các phần tử sau chỉ số i. Bước 3: Dùng Binary Search (upper_bound) để tìm vị trí cuối cùng của các phần tử thỏa mãn điều kiện a[j] <= a[i] * 10 / 9. Bước 4: Cộng dồn số lượng phần tử thỏa mãn vào biến kết quả. Độ phức tạp: O(n log n) do sort và lặp với binary search.

Cách Two Pointers (Hai con trỏ)

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

int main() {
    int n; cin >> n;
    vector<long long> a(n);
    for(int i=0; i<n; i++) cin >> a[i];
    sort(a.begin(), a.end());

    long long ans = 0;
    int r = 0;
    for (int l = 0; l < n; ++l) {
        if (r < l + 1) r = l + 1;
        long long limit = (a[l] * 10) / 9;
        while (r < n && a[r] <= limit) ++r;
        ans += (r - (l + 1));
    }
    cout << ans;
}

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

Sau khi sắp xếp, ta sử dụng kỹ thuật Hai con trỏ (Two Pointers).

• Con trỏ l duyệt qua từng phần tử a[l].
• Con trỏ r duy trì vị trí cuối cùng của dãy con thỏa mãn điều kiện a[r] <= a[l] * 10 / 9.
• Khi l tăng lên, r không cần giảm (vì mảng đã sort, điều kiện a[l+1]10/9 >= a[l]10/9, nên dãy thỏa mãn chỉ có thể mở rộng hoặc giữ nguyên).
• Số lượng cặp (l, j) thỏa mãn là r - (l + 1) (các chỉ số từ l+1 đến r-1). Độ phức tạp: O(n) vì cả hai con trỏ chỉ di chuyển về phía trước tối đa n bước.

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

Bài học kinh nghiệm

• Phép chia integer 10/9 trong C++ bằng 1, nên a[i]10/9 là phép nhân a[i]10 sau đó chia 9. Điều này quan trọng để hiểu tại sao hàm upper_bound hoạt động đúng với số nguyên.
• Việc sắp xếp mảng (Sort) là bước tiền xử lý bắt buộc để áp dụng Binary Search hoặc Two Pointers, giúp biến bài toán từ O(n^2) xuống O(n log n) hoặc O(n).
• Bài toán này là biến thể của việc đếm số lượng phần tử trong một đoạn (subarray) thỏa mãn điều kiện giá trị, có thể giải quyết hiệu quả bằng cách duyệt qua các ngưỡng.

Lỗi thường gặp

• Sai lệch trong điều kiện so sánh: Phân biệt rõ bài toán yêu cầu a[j] >= (10/9)a[i] hay a[j] <= (10/9)a[i]. Các giải pháp accepted đang giải quyết trường hợp thứ hai.
• Sử dụng sai hàm tìm kiếm nhị phân: upperbound trả về iterator trỏ đến phần tử đầu tiên lớn hơn giá trị cần tìm, trong khi lowerbound trả về phần tử đầu tiên không nhỏ hơn giá trị cần tìm.
• Lỗi số nguyên (Integer Overflow): Nếu giá trị a[i] rất lớn (ví dụ 10^18), phép nhân a[i] * 10 có thể tràn số nguyên 64-bit (long long max ~ 9e18). Tuy nhiên, với giới hạn của bài (mảng 100000, thường giá trị vừa phải), phép nhân này thường an toàn. Nếu giá trị lớn hơn, cần dùng __int128 hoặc xử lý đặc biệt.
• Lỗi logic với số thực: Không nên dùng số thực (double) cho các phép so sánh chính xác với số nguyên lớn vì sai số dấu phẩy động.