Editorial for ptit032: Độ dốc của mảng

Hiểu bài toán

Cho một mảng gồm n phần tử. Với mỗi phần tử tại vị trí i (0-indexed), ta cần xác định 'độ dốc' i_cost, được định nghĩa bởi một đoạn liên tục chứa i sao cho:

1. Chiều dài của đoạn là lớn nhất.
2. Các giá trị trong đoạn giảm dần(strictly decreasing) khi di chuyển từ trái sang phải. Điều này có nghĩa là:

• Về bên trái của i: ta mở rộng càng xa càng tốt sao cho mỗi phần tử bên trái đều lớn hơn phần tử ngay sau nó (A[k] > A[k+1]).
• Về bên phải của i: ta mở rộng càng xa càng tốt sao cho mỗi phần tử bên phải đều nhỏ hơn phần tử ngay trước nó (A[k] > A[k+1]).
• Đoạn kết quả sẽ là một 'đỉnh' nhọn (peak) hoặc một đoạn dốc đơn điệu giảm dần chứa i. Đề bài yêu cầu in ra độ dài của đoạn này cho tất cả các phần tử.

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

Cách Brute Force (Duyệt trực tiếp)

#include<stdio.h>

int main(){
    int n;
    scanf("%d", &n);
    int a[n];
    for(int i=0; i<n; i++){
        scanf("%d", &a[i]);
    }
    for(int i=0; i<n; i++){
        int dem = 1;
        // Mở rộng sang trái
        for(int j=i-1; j>=0; j--){
            if(a[j] > a[j+1]) // Chú ý: phần tử trước phải lớn hơn phần tử sau
                dem++;
            else
                break;
        }
        // Mở rộng sang phải
        for(int j=i+1; j<n; j++){
            if(a[j-1] > a[j]) // Chú ý: phần tử trước phải lớn hơn phần tử sau
                dem++;
            else
                break;
        }
        printf("%d ", dem);
    }
}

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

Đây là cách tiếp cận đơn giản nhất. Với mỗi vị trí i, ta duyệt ngược về bên trái và xuôi về bên phải để tìm giới hạn của đoạn giảm dần.

• Khởi tạo độ dài dem = 1 (chính nó).
• Vòng lặp j từ i-1 về 0: Nếu a[j] > a[j+1] thì tăng dem, ngược lại dừng.
• Vòng lặp j từ i+1 lên n-1: Nếu a[j-1] > a[j] thì tăng dem, ngược lại dừng. Vì với mỗi i ta có thể duyệt qua toàn bộ mảng trong trường hợp xấu nhất (mảng giảm dần hoàn toàn), độ phức tạp tổng thể là O(n^2). Với n <= 2*10^5, cách này chắc chắn bị TLE.

Cách Precomputation (Tính toán trước)

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    int *a = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    // left[i] là độ dài đoạn giảm dần kết thúc tại i (từ trái sang)
    // right[i] là độ dài đoạn giảm dần bắt đầu tại i (từ phải sang)
    int *left = (int*)calloc(n, sizeof(int));
    int *right = (int*)calloc(n, sizeof(int));

    // Tính mảng left
    left[0] = 1;
    for (int i = 1; i < n; i++) {
        if (a[i-1] > a[i]) {
            left[i] = left[i-1] + 1;
        } else {
            left[i] = 1;
        }
    }

    // Tính mảng right
    right[n-1] = 1;
    for (int i = n - 2; i >= 0; i--) {
        if (a[i] > a[i+1]) {
            right[i] = right[i+1] + 1;
        } else {
            right[i] = 1;
        }
    }

    // Kết quả tại i là tổng của đoạn giảm dần bên trái và bên phải, trừ đi 1 (vì i được tính 2 lần)
    for (int i = 0; i < n; i++) {
        printf("%d ", left[i] + right[i] - 1);
    }

    free(a);
    free(left);
    free(right);
    return 0;
}

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

Cách tiếp cận này tối ưu hóa bằng cách chia bài toán thành 2 phần:

1. Tính mảng left[i]: lưu độ dài đoạn giảm dần liên tục kết thúc tại i (tính từ trái sang phải).
   • Công thức: if (a[i-1] > a[i]) left[i] = left[i-1] + 1; else left[i] = 1;
2. Tính mảng right[i]: lưu độ dài đoạn giảm dần liên tục bắt đầu tại i (tính từ phải sang trái).
   • Công thức: if (a[i] > a[i+1]) right[i] = right[i+1] + 1; else right[i] = 1;

Đối với mỗi phần tử i, đoạn giảm dần lớn nhất chứa i sẽ là sự kết hợp của:

• Phần bên trái kéo dài về i (độ dài left[i]).
• Phần bên phải bắt đầu từ i (độ dài right[i]).

Độ dài total tại i là left[i] + right[i] - 1. Phép trừ 1 là do phần tử i được tính vào cả left[i] và right[i]. Độ phức tạp là O(n) vì duyệt qua mảng 3 lần (1 lần input, 1 lần left, 1 lần right), không gian O(n).

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

Bài học kinh nghiệm

• Bài toán có tính chất 'consecutive subsequence' (đoạn liên tục), nên có thể chia thành bài toán con tính từ trái sang phải và từ phải sang trái.
• Độ dốc tại vị trí i được xác định bởi 'đáy' của các đoạn dốc gặp nhau tại i.
• Cần phân biệt kỹ giữa 'giảm dần' (strictly decreasing: A[k] > A[k+1]) và 'không tăng' (non-increasing: A[k] >= A[k+1]).

Lỗi thường gặp

• Viết sai điều kiện so sánh: Phải là a[j] > a[j+1] (hoặc a[j-1] > a[j]), không được dùng >=.
• Trường hợp mảng toàn số bằng nhau: Chiều dài đoạn giảm dần tại mỗi phần tử phải là 1 (vì không có cặp nào giảm dần).
• Lỗi truy cập mảng ngoài biên: Cần kiểm tra điều kiện i > 0 hoặc i < n-1 trước khi truy cập a[i-1] hoặc a[i+1].