Spoiler Alert

Hint 1

Xét một bài toán con: Cho mảng a[] gồm n phần tử. Tìm đoạn con a[l]..a[r] thỏa a[l] + k ≥ a[r]

Hint 2

Xài two-pointer, ta dễ dàng giải quyết vấn đề trên với độ phức tạp nhỏ hơn

Reference bài toán con | \(O(n)\) time | \(O(1)\) auxiliary space | Two-pointers

int n = readInt();
vector<int> a(n);
for (int &x : a) cin >> x;

int max_size = 0;
for (int l = 0, r = 0; l < n; ++l) /// O(n)
{
    while (r + 1 < n && a[l] + k > a[r + 1]) r++; /// Two-pointer
    int cur_size = r - l + 1;
    max_size = max(max_size , cur_size);
}
cout << max_size ;

Hint 3

Xét bài toán đề yêu cầu. Với các bài toán con có n - 1 phần tử, ta tính toán.

Kết quả sẽ là result = min{ giá trị các bài toán con }

Ngoài việc thử tạo từng mảng con mà bị loại đi phần tử p. Ta có thể duyệt p qua và thực hiện swap(a[0], a[p + 1]) thì a[1]..a[n - 1] là một mảng con mới đã loại phần tử p + 1. Từ đó giảm độ phức tạp không gian

Reference thuật trâu | 50 điểm + TLE | \(O(n ^ 2)\) time | \(O(1)\) auxiliary space | Brute-forces, Two-pointers

int n = readInt();
vector<int> a(n);
for (int &x : a) cin >> x;

int result = n;
for (int p = 0; p + 1 < n; swap(a[0], a[p + 1]), ++p) /// O(n ^ 2)
{
    int max_size = 0;
    for (int l = 0, r = 0; l < n; ++l) /// O(n)
    {
        while (r + 1 < n && a[l] + k > a[r + 1]) r++; /// Two-pointer
        int cur_size = r - l + 1;
        max_size = max(max_size, cur_size);
        if (max_size > result) break; /// Can
    }
    result = min(result, max_size);
}
cout << result;

Hint 4

Để bỏ vòng lặp ngoài, ta có nhận xét như sau: Ta chỉ cần tìm 2 đoạn con dài nhất ai..aj thỏa ai + k ≥ aj

Gọi độ dài đoạn dài nhất là max_size1, độ dài đoạn dài nhì là max_size2, ta có:

Xét 2 trường hợp

• max_size1 ≠ max_size2 thì result = max_size1 - 1

  (loại bỏ đi một phần tử)

• max_size1 = max_size2 thì result = max_size1

  (loại bỏ đi một phần tử của đoạn dài max_size1, nhưng vẫn còn đoạn dài max_size2 = max_size1)

Reference Thuật tham lam | 81 điểm + WA | \(O(n)\) time | \(O(1)\) auxiliary space | Greedy, Two-pointers

int n = readInt();
vector<int> a(n);
for (int &x : a) cin >> x;

int max_size1 = 0, max_size2 = 0;
for (int l = 0, r = 0; l < n; ++l) /// O(n)
{
    while (r + 1 < n && a[l] + k > a[r + 1]) r++; /// Two-pointer
    int cur_size = r - l + 1;

         if (cur_size > max_size1) max_size2 = max_size1, max_size1 = cur_size;
    else if (cur_size > max_size2) max_size2 = cur_size;
}
cout << max_size1 - (max_size2 != max_size1);

Hint 5

Spot lỗi sai trong thuật trên nào: Đó là chưa xét trường hợp khi 2 đoạn con lồng vào nhau, dẫn tới việc khi xóa một phần tử chung của 2 đoạn con max_size1, max_size2 thì độ dài 2 đoạn con còn lại max_size1 - 1, max_size2 - 1 => res = max_size1 - 1

Để sửa vấn đề này. Ta thêm 2 biến là:

• pos_1 lưu vị trí cuối cùng của đoạn con đầu tiên dài max_size1

• pos_2 lưu vị trí đầu tiên của đoạn con cuối cùng dài max_size2

Xét các trường hợp

• (max_size1 ≠ max_size2) thì result = max_size1 - 1

  (loại bỏ đi một phần tử)

• (max_size1 = max_size2) và (pos_2 <= pos_1) thì result = max_size1 - 1

  (loại bỏ đi một phần tử chung của 2 đoạn con max_size1, max_size2)

• (max_size1 = max_size2) và (pos_2 > pos_1) thì result = max_size1

  (loại bỏ đi một phần tử của đoạn con max_size1 nhưng vẫn còn đoạn con max_size2)

Reference Thuật Two-pointer | 100 điểm = AC | \(O(n)\) time | \(O(1)\) query | O(1) auxiliary space | Online Solving, Two-pointers

int n = readInt();
vector<int> a(n);
for (int &x : a) cin >> x;

int max_size1 = 0, max_size2 = 0;
int  pos_1 = 0,  pos_2 = 0;
    for (int l = 0, r = 0; l < n; ++l) /// O(n)
    {
        while (r + 1 < n && a[l] + k > a[r + 1]) r++; /// Two-pointer
        int cur_size = r - l + 1;

         if (cur_size == max_size1) pos_2 = l, max_size2 = cur_size;
    else if (cur_size  > max_size1) pos_1 = r, max_size1 = cur_size;
}
cout << max_size1 - ((max_size1 != max_size2) || ((max_size1 == max_size2) && (pos_2 <= pos_1)));