Hiểu bài toán

Cho một mảng A gồm n phần tử. Nhiệm vụ là chia mảng thành exactly k dãy con liên tiếp (không rỗng, giữ nguyên thứ tự) để giá trị sức mạnh của cách chia là lớn nhất. Sức mạnh của một dãy con được tính bằng phép toán OR của các phần tử trong dãy đó. Sức mạnh cuối cùng của cách chia là phép toán AND giữa sức mạnh của tất cả k dãy con. Ta cần tìm giá trị lớn nhất có thể đạt được.

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

Cách Tối ưu hóa bit greed (Bitwise Greedy)

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

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

    int n, k;
    cin >> n >> k;
    vector<ll> A(n);
    for(int i = 0; i < n; i++) cin >> A[i];

    ll res = 0;
    // xét từ bit cao xuống thấp
    for(int b = 62; b >= 0; b--){
        ll tryMask = res | (1LL << b);
        int cnt = 0;
        ll cur = 0;
        for(int i = 0; i < n; i++){
            cur |= A[i];
            if ((cur & tryMask) == tryMask){
                cnt++;
                cur = 0;
            }
        }
        if (cnt >= k){
            res = tryMask;
        }
    }

    cout << res;
    return 0;
}

• Time Complexity: O(N * log(max(A))) ~ O(N * 60)
• Space Complexity: O(N)

Đây là cách tiếp cận tối ưu nhất dựa trên tính chất của phép toán AND và OR.

1. Chiến lược: Ta xây dựng kết quả tối ưu từ bit cao xuống bit thấp. Giả sử ta đang xét bit thứ b, và ta đã biết các bit cao hơn (từ b+1 trở lên) của kết quả tối ưu là res.
2. Thử nghiệm: Ta thử thêm bit b vào kết quả bằng cách tạo mask tryMask = res | (1 << b).
3. Kiểm tra: Ta cần kiểm tra xem có thể chia mảng thành ít nhất k đoạn sao cho mỗi đoạn thỏa mãn điều kiện: OR của đoạn chứa tất cả các bit đang xét trong tryMask hay không.
   • Duyệt qua mảng, duy trì biến cur là OR của các phần tử trong đoạn đang xét hiện tại.
   • Nếu (cur & tryMask) == tryMask, tức là đoạn hiện tại đã chứa đủ các bit cần thiết, ta kết thúc đoạn đó (tăng biến đếm cnt, reset cur = 0) và bắt đầu đoạn mới.
4. Quyết định: Nếu sau khi duyệt hết mảng, ta được ít nhất k đoạn (cnt >= k), thì tryMask là khả thi, ta cập nhật res = tryMask. Ngược lại, ta giữ nguyên res (không thêm bit b).

Lý do phương pháp này hiệu quả: Vì ta xét các bit từ cao xuống thấp, nên ta ưu tiên các bit có giá trị lớn nhất. Nếu một bit có thể được bật trong kết quả cuối cùng, ta sẽ bật nó.

Cách Đặt tên (Binary Search on Answer)

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

int n, k;
vector<int> A;

bool can(int x) {
    int cnt = 0;
    int cur_or = 0;
    for (int i = 0; i < n; ++i) {
        cur_or |= A[i];
        if ((cur_or & x) == x) {
            cnt++;
            cur_or = 0;
        }
    }
    return cnt >= k;
}

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

    cin >> n >> k;
    A.resize(n);
    for (int i = 0; i < n; ++i) cin >> A[i];

    int res = 0;
    for (int bit = 30; bit >= 0; --bit) {
        int try_res = res | (1 << bit);
        if (can(try_res)) {
            res = try_res;
        }
    }

    cout << res << '\n';
    return 0;
}

• Time Complexity: O(N * log(max(A)))
• Space Complexity: O(N)

Đây là biến thể của giải thuật tham lam bit, về cơ bản giống Solution 1 nhưng được cấu trúc hóa rõ ràng hơn với hàm check.

Nó dựa trên ý tưởng Greedy trên từng bit:

• Ta bắt đầu với kết quả res = 0.
• Duyệt bit từ cao xuống thấp (ví dụ từ 30 hoặc 60).
• Với mỗi bit, ta thử bật nó lên: try_res = res | (1 << bit).
• gọi hàm can(try_res) để kiểm tra xem try_res có phải là một tiền đề tốt cho kết quả cuối cùng hay không.
  • Hàm can(x) kiểm tra xem có thể chia mảng thành >= k đoạn sao cho OR của mỗi đoạn chứa tất cả các bit trong x hay không.
• Nếu can(try_res) trả về true, nghĩa là ta có thể đạt được ít nhất try_res, nên ta cập nhật res = try_res. Nếu không, ta bỏ qua bit đó.

Cách này tách biệt logic kiểm tra (hàm can) khỏi logic tạo ra kết quả.

Cách Brute Force (Không khả thi)

// Pseudo-code for Brute Force
// Khả thi chỉ với n rất nhỏ (<= 20)
long long solve_brute(int idx, int segments_left, long long current_and) {
    if (segments_left == 1) {
        // Đoạn cuối cùng lấy hết phần còn lại
        long long or_val = 0;
        for(int i=idx; i<n; i++) or_val |= A[i];
        return current_and & or_val;
    }

    long long max_val = 0;
    long long or_val = 0;
    // Thử các điểm kết thúc đoạn hiện tại
    for(int i=idx; i <= n - segments_left; i++) {
        or_val |= A[i];
        long long next_and = current_and & or_val;
        max_val = max(max_val, solve_brute(i+1, segments_left - 1, next_and));
    }
    return max_val;
}

// Gọi: solve_brute(0, k, (1LL<<60)-1 (hoặc OR toàn bộ array))

• Time Complexity: O(n^k) hoặc O(n * 2^n)
• Space Complexity: O(n)

Sử dụng đệ quy/quay lui để thử tất cả các cách chia mảng thành k đoạn.

• Thử tất cả các vị trí để chia đoạn đầu tiên.
• Sau đó đệ quy cho phần còn lại của mảng với k-1 đoạn.
• Tính toán giá trị AND của các đoạn.

Phương pháp này chỉ phù hợp với n rất nhỏ (ví dụ n <= 20). Với n lên tới 200,000, phương pháp này chắc chắn bị TLE (Time Limit Exceeded).

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

Bài học kinh nghiệm

• Tính chất của AND và OR: Để A & B lớn, cả A và B đều phải có các bit cao. Do đó, ta ưu tiên các bit cao trước.
• Greedy trên bit: Nếu ta có thể chia mảng thành >= k đoạn sao cho mỗi đoạn chứa các bit X, thì X là một ứng viên hợp lệ cho kết quả. Ta có thể xây dựng X bằng cách thêm các bit từ cao đến thấp.
• Độc lập tính chất: Việc kiểm tra xem một mask M có thể là kết quả hay không không phụ thuộc vào cách chia các bit khác, nên ta có thể kiểm tra từng bit một cách độc lập.

Lỗi thường gặp

• Kiểu dữ liệu: Nên dùng long long (64-bit) vì A_i có thể lớn và ta cần xử lý bit cao.
• Logic kiểm tra điều kiện: Sai lầm phổ biến là viết điều kiện kiểm tra segment như if (cur == target). Sai, vì OR của một đoạn có thể chứa nhiều bit hơn target. Điều kiện đúng phải là (cur & target) == target (tức cur chứa đủ các bit trong target).
• Xử lý k đoạn: Phải chia đúng exactly k đoạn. Trong vòng lặp kiểm tra, nếu chia được >= k đoạn là OK (vì ta có thể gộp các đoạn nhỏ ở cuối lại mà không làm giảm giá trị AND nếu ta chỉ quan tâm đến >= k).