VOJ - KPLANK

Source: KPLANK
Tags: Data Structures

Problem:
Pirate có N miếng ván chiều rộng 1 đơn vị và chiều dài A[i] đơn vị ghép lại với nhau, Pirate muốn cưa tấm ván lớn đó theo cạnh của mấy miếng ván (vì không có thước đo với cả êke :<), và Pirate muốn cưa thành một hình vuông có cạnh lớn nhất có thể. Xác định độ dài cạnh lớn nhất có thể của hình vuông mà Pirate cưa được.
1 ≤ N ≤ 1e6.
1 ≤ A[i] ≤ 1e9.

Ví dụ:
Input
7
5
2
4
3
3
1
4

Output:
3

Explanation:

Tấm ván được ghép từ những miếng ván theo input

Phần màu xanh là hình vuông có cạnh lớn nhất có thể cưa được

Solution:
Đây chỉ là một bài cơ bản thôi nhưng vì đề tricky quá nên mình sẽ thêm bài này vô blog cho có một bài cơ bản :v
Đầu tiên, vì ta muốn hình vuông có cạnh lớn nhất, do đó ta sẽ chọn một miếng ván i, rồi tìm đoạn những miếng ván liên tiếp có chứa miếng ván i và tất cả đều có độ dài không nhỏ hơn miếng ván i đó.
Ví dụ test đề bài, nếu ta chọn miếng ván 1 thì đoạn tương ứng ta tìm được là (1, 1), nếu chọn miếng ván 2 thì đoạn tương ứng tìm được là (1, 5), nếu chọn miếng ván 3 thì đoạn tương ứng tìm được là (3, 3)...
Để tìm được đoạn này nhanh chóng, ta tìm vị trí miếng ván có độ dài nhỏ hơn miếng ván i gần nhất bên trái và gần nhất bên phải, vậy đoạn ở giữa là đoạn cần tìm. Để tìm được miếng ván thỏa như trên, ta cần một cấu trúc dữ liệu để lưu lại, ở đây sử dụng stack là có độ phức tạp phù hợp nhất cũng như dễ code nhất, nhưng nếu ai muốn try hard code heap hay IT cũng không sao :>
Cách sử dụng deque ở bài này như sau: (giả sử đang xét tại vị trí i)
while a[i] <= stack top do
    pop stack
push a[i] into stack
Trước khi push A[i] vào stack thì stack top hiện tại chính là vị trí cần tìm (nếu stack rỗng thì từ 1 đến i đều thỏa vì không có vị trí nào có độ dài nhỏ hơn i). Stack top này đảm bảo 2 điều kiện sau:
1. Stack top < A[i]: Vì tất cả những vị trí có độ dài >= A[i] đã bị pop ra khỏi stack, do đó stack top chắc chắn sẽ nhỏ hơn A[i].
2. Stack top gần A[i] nhất: Vì ở những vị trí j trước đó khi push luôn để A[j] lên đầu, do đó trong stack đảm bảo < A[j], trước khi push A[i] đã push A[i - 1] nên nếu A[i - 1] thỏa thì rõ ràng i - 1 là đứa gần nhất, nếu A[i - 1] không thỏa thì đứa tiếp sẽ là đứa thỏa gần nhất và cứ như vậy.
Thực hiện stack theo 2 chiều 1 → N và N → 1 sẽ tìm được vị trí trái gần nhất và phải gần nhất.
Gọi 2 vị trí vừa tìm được đó là L[i] và R[i], những bạn nào để ý sẽ thấy rằng có thể R[i] - L[i] + 1 (độ dài đoạn) sẽ nhỏ hơn A[i]. Tức là, đoạn này không đủ để tạo hình vuông cạnh A[i]. Những bạn nào có tư duy toán học nhạy bén, khả năng vận dụng logic cao sẽ nhanh trí nghĩ ra rằng, đáp án chính là max(min(A[i], R[i] - L[i] + 1)) với i = 1 .. N vì nếu không làm được hình vuông cạnh A[i] thì hình vuông cạnh R[i] - L[i] + 1 cũng sẽ được. Nhưng không :) đây là thời khắc của những đứa không não lên ngôi :) Đề bài có cho dữ kiện rằng: "vì không có thước đo cũng như êke nên Pirate phải cưa theo các cạnh của những miếng ván" và boom, nếu R[i] - L[i] + 1 < A[i] ta sẽ không có cách để đo đoạn R[i] - L[i] + 1 trên các miếng ván để mà cưa =]] do đó nếu R[i] - L[i] + 1 >= A[i] thì ta mới được lấy max A[i].
Độ phức tạp stack là O(2 * N) vì với mỗi miếng ván ta chỉ push và pop tối đa 1 lần.

Code: (code mình là cách vận dụng mảng để tìm luôn nhưng nó thật chất cũng chỉ là cách stack được code một cách có não thôi :>)
#include <iostream>

using namespace std;

int n, a[1000015], l[1000015], r[1000015], res;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++) {
        l[i] = i;
        while (l[i] > 1 && a[i] <= a[l[i] - 1])
            l[i] = l[l[i] - 1];
    }
    for (int i = n; i >= 1; i--) {
        r[i] = i;
        while (r[i] < n && a[i] <= a[r[i] + 1])
            r[i] = r[r[i] + 1];
    }
    for (int i = 1; i <= n; i++)
        if (r[i] - l[i] + 1 >= a[i])
            res = max(res, a[i]);
    cout << res;

}