VNU OLYMPIAD INFORMATICS 2022 - Post

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VNUOI 2022
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

In case the statement didn't load correctly, you can download the statement here: Statement


Comments

Please read the guidelines before commenting.



  • 18
    marvinthang   commented on March 19, 2022, 9:38 p.m. edited

    Thuật chuẩn:

    ~Binary Search~

    Check bằng quy hoạch động

    ~F_i~: có tồn tại trạng thái 1 người ở nhà thứ i không, nếu có tìm j lớn nhất thỏa mãn khoảng cách từ ~X_{i + 1}, .. X_j~ đến ~X_i \leq D~ thì ~ F_{i + 1}, .., F_j = true~.

    ĐPT: ~O(N^2 * \log_2 N~)

    Cải tiến:

    Sử dụng ~Sparse Table~ kết hợp ~Binary Search~ để tìm j, j thỏa mãn khi khoảng cách từ ~max(X_{i + 1}, .., X_j)~ và ~min(X_{i + 1}, .., X_j)~ đến ~X_i \leq D~.

    ĐPT ~O(N * log_2^2 N~)

    Code mẫu: Ideone