Editorial for ptit036: Lũy thừa cơ số 2

Hiểu bài toán

Bài toán yêu cầu tính giá trị $\lfloor 2^X \rfloor$ với $X = (\sum{i=1}^{m} f(i)) \mod 30$. Trong đó, $f(i)$ là vị trí (chỉ số bắt đầu từ 1) của phần tử $bi$ trong mảng $a$ đã được sắp xếp không giảm. Nếu $bi$ không t tồn tại trong $a$, $f(i) = -1$. Nếu $bi$ xuất hiện nhiều lần, lấy vị trí nhỏ nhất (xuất hiện đầu tiên). Mảng $a$ có kích thước $n \le 10^5$, mảng $b$ có kích thước $m \le 10^5$. Do $X$ được lấy modulo 30 và $2^{30} = 1073741824$ nằm trong phạm vi 64-bit integer, ta có thể tính toán trực tiếp.

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

Cách Brute Force (Duyệt toàn bộ)

#include <stdio.h>

int main() {
    int n, m;
    scanf("%d", &n);
    int a[n];
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    scanf("%d", &m);
    int b[m];
    for (int i = 0; i < m; i++) scanf("%d", &b[i]);

    long long sum = 0;
    for (int i = 0; i < m; i++) {
        int found = -1;
        // Duyet qua mang a de tim b[i]
        for (int j = 0; j < n; j++) {
            if (a[j] == b[i]) {
                found = j + 1; // Vi tri bat dau tu 1
                break;
            }
        }
        sum += found;
    }

    int X = sum % 30;
    if (X < 0) printf("0");
    else {
        long long res = 1;
        for (int i = 0; i < X; i++) res *= 2;
        printf("%lld", res);
    }
    return 0;
}

• Time Complexity: O(n * m) ~ $10^5 \times 10^5 = 10^{10}$ operations (Quá chậm)
• Space Complexity: O(n + m)

Đây là cách tiếp cận đơn giản nhất. Với mỗi phần tử trong mảng $b$, ta duyệt qua mảng $a$ để tìm vị trí của nó. Do cả hai mảng đều có thể chứa tới $10^5$ phần tử, độ phức tạp thời gian là $O(nm)$, dẫn đến TLE (Time Limit Exceeded).

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

#include <stdio.h>

// Tra ve vi tri (1-based) dau tien cua x trong a[0...n-1]
int binary_search(int a[], int n, int x) {
    int l = 0, r = n - 1;
    int res = -1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (a[mid] == x) {
            res = mid + 1; // Cap nhat ket qua
            r = mid - 1;   // Tiep tuc tim ben trai de tim index nho nhat
        } else if (a[mid] < x) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return res;
}

int main() {
    int n, m;
    scanf("%d", &n);
    int a[n];
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    scanf("%d", &m);
    int b[m];
    for (int i = 0; i < m; i++) scanf("%d", &b[i]);

    long long sum = 0;
    for (int i = 0; i < m; i++) {
        sum += binary_search(a, n, b[i]);
    }

    int X = sum % 30;
    if (X < 0) printf("0");
    else {
        long long res = 1;
        for (int i = 0; i < X; i++) res *= 2;
        printf("%lld", res);
    }
    return 0;
}

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

Vì mảng $a$ đã được sắp xếp, ta có thể áp dụng thuật toán Tìm kiếm nhị phân (Binary Search) để tìm vị trí của các phần tử trong $b$. Độ phức tạp thời gian giảm xuống còn $O(m \log n)$, tương đương khoảng $1.7 \times 10^6$ thao tác, hoàn toàn nằm trong giới hạn cho phép (thường là $10^8$ thao tác/giây).

Cách Hash Map (Bản đồ băm)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    map<int, int> pos;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (pos.find(x) == pos.end()) {
            pos[x] = i;
        }
    }

    int m;
    cin >> m;
    long long sum = 0;
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        if (pos.count(x)) {
            sum += pos[x];
        } else {
            sum += -1;
        }
    }

    int X = sum % 30;
    if (X < 0) cout << 0;
    else {
        long long res = 1;
        for (int i = 0; i < X; i++) res *= 2;
        cout << res;
    }
    return 0;
}

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

Sử dụng cấu trúc dữ liệu Map (hoặc Hash Map) để lưu trữ vị trí của mỗi phần tử trong mảng $a$. Ta duyệt qua $a$ một lần để xây dựng map (chỉ lưu giá trị đầu tiên nếu bị trùng lặp). Sau đó, với mỗi phần tử trong $b$, ta chỉ mất $O(\log n)$ để tra cứu vị trí. Phương pháp này hiệu quả và dễ cài đặt trong C++.

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

Bài học kinh nghiệm

• Mảng $a$ được sắp xếp cho phép sử dụng Binary Search để tối ưu hóa việc tìm kiếm.
• Giá trị $X$ được tính modulo 30, nên $2^X$ không vượt quá $2^{29}$, có thể lưu trữ trong kiểu long long (64-bit integer) mà không cần thư viện big integer.
• Để xử lý trùng lặp và lấy vị trí nhỏ nhất, Binary Search cần được viết ở dạng 'tìm kiếm cực biên bên trái' (find leftmost).

Lỗi thường gặp

• Sử dụng thuật toán tìm kiếm tuyến tính (O(n*m)) dẫn đến quá thời gian.
• Không xử lý đúng trường hợp phần tử xuất hiện nhiều lần trong $a$ (lấy sai vị trí).
• Quên xử lý trường hợp $b_i$ không t tồn tại trong $a$ để gán giá trị -1.
• Sai sót khi tính toán số mũ lớn (nên dùng vòng lặp nhân đôi hoặc pow cẩn thận thay vì dịch bit nếu không chắc chắn về số âm).