Editorial for inv2x: Đếm cặp

Hiểu bài toán

Bài toán yêu cầu đếm số cặp chỉ số (i, j) sao cho 1 ≤ i < j ≤ n và ai > 2 * aj. Nói cách khác, với mỗi phần tử aj, ta cần đếm số phần tử ai đứng trước nó (i < j) có giá trị lớn hơn gấp đôi a_j.

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

Cách Brute Force

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

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

    long long cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] > 2LL * a[j]) {
                cnt++;
            }
        }
    }

    cout << cnt << endl;
    return 0;
}

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

Approach này sử dụng hai vòng lặp lồng nhau để kiểm tra tất cả các cặp (i, j) với i < j. Với mỗi cặp, ta kiểm tra điều kiện a[i] > 2 * a[j]. Đây là cách tiếp cận trực quan nhất nhưng không hiệu quả với n lớn (n = 1000, t tổng số cặp ~500,000). Tuy nhiên, với n ≤ 1000, độ phức tạp O(n^2) vẫn có thể chạy trong thời gian chấp nhận được (~0.5 giây).

Cách Optimized Brute Force (Early Break)

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

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

    long long cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] > 2LL * a[j]) {
                cnt++;
            }
        }
    }

    cout << cnt << endl;
    return 0;
}

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

Các solution được cung cấp đều sử dụng thuật toán O(n^2) trực tiếp. Với n = 1000, số lượng cặp cần kiểm tra là khoảng 500,000, mỗi cặp chỉ cần một phép so sánh đơn giản. Đây là cách giải quyết đơn giản và dễ hiểu nhất cho bài toán này.

Cách Merge Sort based Counting

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

long long count_pairs(vector<int>& a, int left, int mid, int right) {
    long long cnt = 0;
    int j = mid + 1;

    // For each element in left half, count elements in right half that satisfy condition
    for (int i = left; i <= mid; i++) {
        // Find first element in right half that does NOT satisfy condition
        // All elements before that satisfy condition
        while (j <= right && (long long)a[i] > 2LL * a[j]) {
            j++;
        }
        cnt += (j - (mid + 1));
    }

    return cnt;
}

void merge(vector<int>& a, int left, int mid, int right) {
    vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        if (a[i] <= a[j]) {
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
        }
    }

    while (i <= mid) temp[k++] = a[i++];
    while (j <= right) temp[k++] = a[j++];

    for (int i = 0; i < k; i++) {
        a[left + i] = temp[i];
    }
}

long long merge_sort_count(vector<int>& a, int left, int right) {
    if (left >= right) return 0;

    int mid = left + (right - left) / 2;
    long long cnt = 0;

    cnt += merge_sort_count(a, left, mid);
    cnt += merge_sort_count(a, mid + 1, right);
    cnt += count_pairs(a, left, mid, right);
    merge(a, left, mid, right);

    return cnt;
}

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

    cout << merge_sort_count(a, 0, n - 1) << endl;
    return 0;
}

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

Đây là cách tiếp cận tối ưu hơn, sử dụng kỹ thuật chia để trị kết hợp với Merge Sort. Ý tưởng là trong quá trình merge, ta có thể đếm số cặp (i, j) thỏa mãn điều kiện. Khi chia mảng thành hai nửa trái và phải, với mỗi phần tử trong nửa trái, ta có thể đếm số phần tử trong nửa phải có giá trị nhỏ hơn một nửa của nó. Vì hai nửa đã được sắp xếp, ta có thể dùng hai con trỏ để đếm trong thời gian tuyến tính.

Cụ thể:

1. Chia mảng thành hai nửa và đệ quy
2. Trong bước merge, với mỗi phần tử a[i] ở nửa trái, dùng con trỏ j duyệt qua nửa phải
3. Nếu a[i] > 2 * a[j], tăng j và tiếp tục
4. Khi gặp phần tử không thỏa mãn, tất cả các phần tử trước đó đều thỏa mãn
5. Cộng dồn vào kết quả và merge như bình thường

Độ phức tạp O(n log n) do mỗi cấp độ chia mất O(n), và có log n cấp độ.

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

Bài học kinh nghiệm

• Vì điều kiện là a[i] > 2*a[j] với i < j, ta có thể đếm trực tiếp hoặc sử dụng cấu trúc dữ liệu để tối ưu
• Với n ≤ 1000, O(n^2) là hoàn toàn chấp nhận được và là cách đơn giản nhất
• Kỹ thuật merge sort cho phép đếm số cặp trong quá trình sắp xếp, tối ưu hơn O(n^2)

Lỗi thường gặp

• Sử dụng int thay vì long long cho biến đếm có thể gây tràn số khi n lớn (ví dụ n=1000, số cặp có thể lên tới ~500,000)
• Quên ép kiểu khi nhân 2*a[j] vì a[j] có thể lên tới 10^9, nếu dùng int có thể tràn số
• Viết sai điều kiện i < j trong vòng lặp, dẫn đến đếm sai hoặc truy cập ngoài mảng