Trùm cuối DP hay Cú lừa thế kỷ? Rất khó... để không tự chửi mình sau khi đọc xong bài viết này.

Chào các tay to thuật toán! 👋

Chắc hẳn khi đọc đến bài "Mật khẩu", não bộ của các bạn đã tự động nảy số cực mạnh. Các bạn nhìn thấy giới hạn ~N, Q \le 2 \times 10^5~. Các bạn thấy mảng thời gian gợi ý ~t_i~ lên đến ~10^9~. Các bạn thấy những truy vấn đoạn ~[l, r]~.

Và thế là, một bữa tiệc cấu trúc dữ liệu bắt đầu. Có bạn code Quy hoạch động kết hợp Chặt nhị phân. Có bạn lôi cả Segment Tree ra để tìm chi phí mua gợi ý. Có bạn thì ngồi nháp mất 45 phút rồi nhận ra mình vừa TLE vừa WA. Cảm giác lúc đó thật tuyệt vọng đúng không?

Nhưng các bạn ơi, hãy dừng lại 3 giây và đọc lại CHÍNH XÁC từng chữ mà huyhau6a2 đã viết trong đề:

huyhau6a2 đã viết một chương trình giúp xác định nhanh thời gian tối thiểu để một người mò mật khẩu từ đầu có thể truy cập vào đề thi của mình.

Phân tích một chút về môn Tiếng Việt nhé:

1. Thời gian tối thiểu: Đề bài không hề yêu cầu tìm thời gian trong trường hợp xấu nhất (worst-case), cũng không yêu cầu đảm bảo 100% phải mò ra. Tối thiểu ở đây chính là ... trường hợp hên nhất (best-case).
2. Một người: Trong hàng vạn người đi mò mật khẩu, chắc chắn sẽ tồn tại một bậc thầy nhân phẩm, một người con của thần may mắn.
3. Kẻ may mắn đó sẽ làm gì? Họ bước đến hệ thống, nhắm mắt gõ bừa một phát... và bùm! Mật khẩu ĐÚNG NGAY LẦN ĐẦU TIÊN.

Theo dữ kiện đề bài: Hành động nhập mật khẩu và được hệ thống trả về kết quả mất đúng 1 đơn vị thời gian.

Vậy người đó có cần mua gợi ý ~t_i~ không? Không.

Người đó có quan tâm đoạn ~[l, r]~ dài bao nhiêu không? Không.

Thời gian tối thiểu để một người (cực kỳ may mắn) mò được mật khẩu luôn luôn là 1. Bất chấp ~N, Q, t_i~ to đến mức nào.

Và phần đau đớn nhất dành cho các bạn: Các bạn có nhớ phần Sample Output của đề bài in ra cái gì không? Đúng vậy, nó in ra 1 và 1 cho cả hai truy vấn! Tác giả đã ném thẳng cái đáp án trần trụi ấy vào mặt các bạn, nhưng vì cái tôi của một CPer quá lớn, các bạn đã tự dối lòng rằng: À, chắc tại test ví dụ này nó thế thôi, test thật chắc chắn phải dùng DP!. Không, tác giả không lừa bạn, do bạn tự lừa chính mình thôi! 🤡

Code mẫu:

#include <iostream>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    // Đọc cho vui chứ chả để làm gì
    for (int i = 1; i <= n; i++) {
        int t; cin >> t; 
    }
    while (q--) {
        int l, r; cin >> l >> r;
        // Nhân phẩm bùng nổ, 1 phát ăn ngay!
        cout << 1 << "\n";
    }
    return 0;
}

Độ phức tạp: ~O(Q)~ thời gian, ~O(1)~ bộ nhớ, và ~O(\infty)~ sự cay cú.