Editorial for Chơi game


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Chơi game

Sub 1: ~H_1~ ~<~ ~H_2~ ~<~ ... ~<~ ~H_n~
  • Gọi ~f[i] = 1~ nếu tòa tháp ~i~ thỏa mãn và ~f[i] = 0~ trong trường hợp còn lại. Ta có ~f[1] = 1~
  • Xét tòa tháp thứ ~i~, ta cần tìm xem có tòa tháp thứ ~j~ sao cho ~j < i~, ~|h[i] - h[j]| \le k~ và ~f[j] = 1~. Tuy nhiên vì ~h~ là dãy tăng dần, ta chỉ cần xét vị trí ~i - 1~ vì nếu vị trí ~i - 1~ thỏa mãn thì vị trí ~i~ sẽ thỏa mãn. Nếu không giả sử tồn tại vị trí ~t~ thỏa mãn ~f[t] = 1~ và ~t < i - 1~, lúc này ~|h[i] - h[i - 1]| < |h[i] - h[t]|~ nên nếu không thể cập nhật vị trí ~i~ từ ~i - 1~ thì càng không thể sử dụng ~t~ để cập nhật cho ~i~.
  • ĐPT: ~O(n)~
Sub 2: ~n \le 1000~
  • Xét vị trí thứ ~i~, ta duyêt qua các vị trí ~j < i~.
  • Nếu tồn tại vị trí ~j~ thỏa mãn ~f[j] = 1~ và ~|h[i] - h[j] \le k~ thì ~f[i] = 1~.
  • ĐPT: ~O(n ^ 2)~
Sub 3 : Không có ràng buộc gì thêm
  • Nhận xét rằng ~i~ độ cao có thể nhảy đến từ đỉnh ~1~ sẽ tạo thành 1 khoảng ~[l_i, r_i]~. Ta có ~l_1 = h[1] - k~ và ~r_1 = h[1] + k~.
  • Vậy với mỗi vị trí ~i + 1~, nếu ~l_i \le h[i + 1] \le r_i~ thì ~f[i + 1] = 1~.
  • Ta cập nhật khoảng ~[l_i, r_i]~ mỗi khi có độ cao thỏa mãn mới.
  • DDPT: ~O(n)~
Code tham khảo
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 2;

int n, k, h[N];

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    #define task "CHOIGAME"
    if(fopen(task ".INP", "r")) {
        freopen(task ".INP", "r", stdin);
        freopen(task ".ANS", "w", stdout);
    }
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }
    int l = h[0], r = h[0];
    cout << "1 ";
    for (int i = 1; i < n; ++i) {
        if (l - k <= h[i] && h[i] <= r + k) {
            cout << "1 ";
            l = min(l, h[i]);
            r = max(r, h[i]);
        } else cout << "0 ";
    }
    cout << "\n";
    return 0;
}