Hiểu bài toán

Bài toán yêu cầu tìm số lớn nhất có thể đạt được trong một dãy số sau khi thực hiện nhiều lần thao tác gộp hai số kề nhau bằng nhau thành một số lớn hơn chúng 1 đơn vị. Dãy số ban đầu có độ dài N (2 ≤ N ≤ 262144) và mỗi số nằm trong khoảng [1, 40]. Điểm số cuối cùng là giá trị lớn nhất còn lại trong dãy sau khi không thể thực hiện thêm thao tác nào.

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

Cách Giả lập bằng Stack

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

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

    int n;
    cin >> n;
    stack<int> st;
    while(n --){
        int x; cin >> x;
        while(!st.empty() && st.top() == x){
            x ++ ;
            st.pop();
        }
        st.push(x);
    }
    int res = 0;
    while(!st.empty()){
        res = max(res, st.top());
        st.pop();
    }
    cout << res << endl;
    return 0;
}

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

Cách tiếp cận này mô phỏng quá trình chơi game trực tiếp bằng cách sử dụng một stack. Với mỗi số đọc vào từ input, ta so sánh nó với số ở đỉnh stack (nếu có). Nếu chúng bằng nhau, ta gộp chúng lại (tăng giá trị lên 1) và loại bỏ số ở đỉnh stack. Quá trình này lặp lại cho đến khi đỉnh stack khác giá trị hiện tại hoặc stack rỗng, sau đó đẩy giá trị mới vào stack. Stack ở đây đóng vai trò là dãy số hiện tại. Độ复杂度 là O(N) vì mỗi phần tử được đẩy vào và lấy ra từ stack tối đa một lần.

Cách Dynamic Programming (Quy hoạch động)

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

const int MAXN = 262144 + 5;
const int MAX_VAL = 64; // 40 + max merge steps
int dp[MAX_VAL][MAXN];
int A[MAXN];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    int result = 0;
    // dp[v][i] là chỉ số của phần tử đầu tiên sau đoạn liên tiếp có thể tạo ra giá trị v bắt đầu tại i
    // Hoặc hiểu nôm na: để tạo thành giá trị v tại vị trí i, đoạn kết thúc ở đâu.
    // Logic trong code mẫu gốc hơi khác một chút: dp[v][i] lưu index của phần tử tiếp theo sau đoạn tạo được giá trị v.

    for (int i = 0; i < N; i++) {
        if (A[i] == 1) dp[1][i] = i + 1; // Tạo giá trị 1 từ chính nó
        else dp[1][i] = -1;
    }

    for (int v = 2; v < MAX_VAL; v++) {
        for (int i = 0; i < N; i++) {
            // Để tạo ra giá trị v tại i, ta cần 2 đoạn liên tiếp tạo ra giá trị v-1
            int next_idx = dp[v-1][i];
            if (next_idx != -1 && dp[v-1][next_idx] != -1) {
                dp[v][i] = dp[v-1][next_idx];
                result = max(result, v);
            } else {
                dp[v][i] = -1;
            }
        }
    }
    cout << result;
    return 0;
}

• Time Complexity: O(N * log(MaxVal))
• Space Complexity: O(N * log(MaxVal))

Phương pháp này dựa trên ý tưởng quy hoạch động. Ta định nghĩa dp[v][i] là chỉ số kết thúc của đoạn liên tiếp bắt đầu tại i có thể tạo ra giá trị v. Để tạo ra giá trị v tại vị trí i, ta cần tìm một đoạn liên tiếp bắt đầu tại i tạo ra giá trị v-1, và ngay sau đó là một đoạn liên tiếp khác cũng tạo ra giá trị v-1. Nếu tìm được, ta cập nhật dp[v][i]. Giá trị lớn nhất tìm được trong quá trình này là đáp án. Do các giá trị số ban đầu nhỏ (≤ 40) và mỗi lần gộp tăng 1 đơn vị, giá trị lớn nhất có thể đạt được không vượt quá 64 (thực tế là 262144 nhưng trong DP ta chỉ cần quan tâm đến các bước Merge). Tuy nhiên, với N lớn, DP mảng 2 chiều có thể tốn bộ nhớ, nhưng do Max Value nhỏ nên khá hiệu quả.

Cách Tối ưu hóa Logic Stack (Giải pháp tối ưu)

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

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

    int n;
    cin >> n;
    vector<int> st;
    st.reserve(n); // Tránh reallocate

    int max_val = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        // Gộp các số giống nhau ở đỉnh stack
        while (!st.empty() && st.back() == x) {
            x++; // Tăng giá trị lên 1
            st.pop_back();
        }
        st.push_back(x);
        if (x > max_val) max_val = x;
    }

    cout << max_val << endl;
    return 0;
}

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

Đây là phiên bản tối ưu và trực quan nhất của phương pháp Stack. Sử dụng vector như một stack để tránh tràn stack do đệ quy. Logic xử lý giống hệt giải pháp stack cơ bản: đọc từng số, so sánh với phần tử cuối cùng của vector. Nếu bằng nhau, gộp lại (x++) và xóa phần tử cuối, lặp lại cho đến khi khác. Cuối cùng đẩy x vào. Ta có thể cập nhật giá trị lớn nhất (max_val) ngay tại thời điểm đẩy vào stack để chỉ cần duyệt một lần. Đây là giải pháp được chấp nhận rộng rãi nhất cho bài này.

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

Bài học kinh nghiệm

• Bài toán có tính chất cục bộ (local): một thao tác gộp chỉ ảnh hưởng trực tiếp đến 2 số kề nhau, gợi ý sử dụng cấu trúc dữ liệu dạng stack.
• Mặc dù giá trị đầu vào nhỏ (1-40), nhưng giá trị đầu ra có thể rất lớn (lên tới 262144), do đó cần chú ý kiểu dữ liệu (int 32-bit là đủ cho giá trị đầu ra, nhưng cẩn thận với các phép tính trung gian).
• Bài toán tương tự với việc giảm trừ chuỗi ký tự hoặc số, tương tự vấn đề 'Crush' trong competitive programming.

Lỗi thường gặp

• Sử dụng đệ quy quá sâu: Nếu mô phỏng đệ quy mà không kiểm soát, có thể gây tràn bộ nhớ stack (Stack Overflow) với N lớn.
• Lỗi logic trong DP: Xác định sai trạng thái dp, ví dụ không xử lý đúng trường hợp các đoạn giá trị v-1 bị ngắt quãng.
• Bỏ qua trường hợp đặc biệt: Input có thể chứa các số không thể gộp ngay lập tức nhưng có thể gộp sau khi các số khác được gộp và loại bỏ.